Diberikan $n$ garis vertikal, di mana garis ke-$i$ adalah $x = a_i$, serta $m$ garis horizontal, di mana garis ke-$i$ adalah $y = b_i$. Dibutuhkan $t_i$ satuan waktu untuk berpindah sejauh $1$ satuan jarak di sepanjang garis vertikal ke-$i$, dan dibutuhkan $t_0$ satuan waktu untuk berpindah sejauh $1$ satuan jarak di sepanjang garis horizontal mana pun.

Misalkan $f(i, j)$ adalah waktu minimum yang dibutuhkan untuk pergi dari $(0, 0)$ ke $(a_i, b_j)$ dengan hanya bergerak di sepanjang garis vertikal dan horizontal. Anda perlu menjawab $q$ kueri, di mana setiap kueri direpresentasikan sebagai empat bilangan bulat $l, r, d, u$, dan Anda perlu menghitung

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

Karena jawabannya bisa sangat besar, keluarkan hasilnya modulo $998\,244\,353$.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi tiga bilangan bulat $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$), yang menyatakan banyaknya garis vertikal, garis horizontal, dan kueri.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($0 = a_1 < a_2 < \dots < a_n \le 10^9$), yang menyatakan koordinat-$x$ dari garis-garis vertikal.

Baris ketiga berisi $m$ bilangan bulat $b_1, b_2, \dots, b_m$ ($0 = b_1 < b_2 < \dots < b_m \le 10^9$), yang menyatakan koordinat-$y$ dari garis-garis horizontal.

Baris keempat berisi $n$ bilangan bulat $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9$), di mana $t_i$ menyatakan waktu yang dibutuhkan untuk berpindah sejauh $1$ satuan jarak di sepanjang garis vertikal ke-$i$.

Baris kelima berisi satu bilangan bulat $t_0$ ($1 \le t_0 \le 10^9$), yang menyatakan waktu yang dibutuhkan untuk berpindah sejauh $1$ satuan jarak di sepanjang garis horizontal mana pun.

Untuk $q$ baris berikutnya, baris ke-$i$ berisi empat bilangan bulat $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$), yang menyatakan kueri ke-$i$.

Dijamin bahwa jumlah dari $n$, jumlah dari $m$, dan jumlah dari $q$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $q$ bilangan bulat, di mana bilangan bulat ke-$i$ adalah jawaban untuk kueri ke-$i$ modulo $998\,244\,353$.

Contoh

Contoh Masukan 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

Contoh Keluaran 1

43 21 0