تُعطى $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