נתונים $n$ קווים אנכיים, כאשר הקו ה-$i$ הוא $x = a_i$, וכן $m$ קווים אופקיים, כאשר הקו ה-$i$ הוא $y = b_i$. נדרשות $t_i$ יחידות זמן כדי לנוע מרחק של יחידה $1$ לאורך הקו האנכי ה-$i$, ונדרשות $t_0$ יחידות זמן כדי לנוע מרחק של יחידה $1$ לאורך כל קו אופקי.

יהי $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