$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