กำหนดเส้นตรงแนวตั้ง $n$ เส้น โดยที่เส้นที่ $i$ คือ $x = a_i$ และเส้นตรงแนวนอน $m$ เส้น โดยที่เส้นที่ $i$ คือ $y = b_i$ การเคลื่อนที่เป็นระยะทาง $1$ หน่วยตามเส้นตรงแนวตั้งเส้นที่ $i$ ใช้เวลา $t_i$ หน่วย และการเคลื่อนที่เป็นระยะทาง $1$ หน่วยตามเส้นตรงแนวนอนใดๆ ใช้เวลา $t_0$ หน่วย

ให้ $f(i, j)$ เป็นเวลาที่น้อยที่สุดที่ต้องใช้ในการเดินทางจาก $(0, 0)$ ไปยัง $(a_i, b_j)$ โดยการเคลื่อนที่ไปตามเส้นตรงแนวตั้งและแนวนอนเท่านั้น คุณต้องตอบคำถาม $q$ ข้อ โดยแต่ละคำถามแทนด้วยจำนวนเต็มสี่ตัว $l, r, d, u$ และคุณต้องคำนวณ

$$\sum_{i=l}^{r} \sum_{j=d}^{u} f(i, j)$$

เนื่องจากคำตอบอาจมีค่ามาก ให้แสดงผลลัพธ์มอดูโล $998\,244\,353$

ข้อมูลนำเข้า

มีหลายชุดทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^4$) แสดงจำนวนชุดทดสอบ สำหรับแต่ละชุดทดสอบ:

บรรทัดแรกประกอบด้วยจำนวนเต็มสามตัว $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$) แสดงจำนวนเส้นตรงแนวตั้ง เส้นตรงแนวนอน และจำนวนคำถาม

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ ตัว $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$) แสดงพิกัด $x$ ของเส้นตรงแนวตั้ง

บรรทัดที่สามประกอบด้วยจำนวนเต็ม $m$ ตัว $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$) แสดงพิกัด $y$ ของเส้นตรงแนวนอน

บรรทัดที่สี่ประกอบด้วยจำนวนเต็ม $n$ ตัว $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$) โดยที่ $t_i$ แสดงเวลาที่ต้องใช้ในการเคลื่อนที่เป็นระยะทาง $1$ หน่วยตามเส้นตรงแนวตั้งเส้นที่ $i$

บรรทัดที่ห้าประกอบด้วยจำนวนเต็มหนึ่งตัว $t_0$ ($1 \le t_0 \le 10^9$) แสดงเวลาที่ต้องใช้ในการเคลื่อนที่เป็นระยะทาง $1$ หน่วยตามเส้นตรงแนวนอนใดๆ

สำหรับ $q$ บรรทัดถัดไป บรรทัดที่ $i$ ประกอบด้วยจำนวนเต็มสี่ตัว $l_i, r_i, d_i, u_i$ ($1 \le l_i \le r_i \le n, 1 \le d_i \le u_i \le m$) แสดงคำถามข้อที่ $i$

รับประกันว่าผลรวมของ $n$ ผลรวมของ $m$ และผลรวมของ $q$ ในทุกชุดทดสอบไม่เกิน $2 \times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดทดสอบ ให้ส่งออกหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็ม $q$ ตัว โดยที่จำนวนเต็มตัวที่ $i$ คือคำตอบของคำถามข้อที่ $i$ มอดูโล $998\,244\,353$

ตัวอย่าง

ข้อมูลนำเข้า 1

1
3 2 3
0 2 10
0 3
100 2 1
1
1 3 1 2
2 3 2 2
1 1 1 1

ข้อมูลส่งออก 1

43 21 0