$n$ вертикаль түзу берілген, мұндағы $i$-ші түзу $x = a_i$, сондай-ақ $m$ горизонталь түзу берілген, мұндағы $i$-ші түзу $y = b_i$. $i$-ші вертикаль түзудің бойымен $1$ бірлік қашықтыққа жылжу үшін $t_i$ уақыт бірлігі кетеді, ал кез келген горизонталь түзудің бойымен $1$ бірлік қашықтыққа жылжу үшін $t_0$ уақыт бірлігі кетеді.

Тек вертикаль және горизонталь түзулердің бойымен қозғала отырып, $(0, 0)$ нүктесінен $(a_i, b_j)$ нүктесіне жету үшін қажетті ең аз уақытты $f(i, 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$) берілген.

Екінші жолда вертикаль түзулердің $x$-координаталарын білдіретін $n$ бүтін сан $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$) берілген.

Үшінші жолда горизонталь түзулердің $y$-координаталарын білдіретін $m$ бүтін сан $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$) берілген.

Төртінші жолда $n$ бүтін сан $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$) берілген, мұндағы $t_i$ саны $i$-ші вертикаль түзудің бойымен $1$ бірлік қашықтыққа жылжуға қажетті уақытты білдіреді.

Бесінші жолда кез келген горизонталь түзудің бойымен $1$ бірлік қашықтыққа жылжуға қажетті уақытты білдіретін бір бүтін сан $t_0$ ($1 \le t_0 \le 10^9$) берілген.

Келесі $q$ жолда, $i$-ші жолда $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$) берілген.

Барлық тест жиынтықтары бойынша $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