Qinmei and Fretz own a toy store in City C. There are $n$ types of toys in the store, numbered $1, 2, \dots, n$. The unit price of the $i$-th toy is $c_i$, and the pleasure provided by one such toy is $v_i$.

Suddenly, $m$ children arrive in City C. According to reliable information, these children will come to the store to buy things every day for the next $Q$ days. The $i$-th child brings $i$ yuan every day ($1 \leq i \leq m$).

Since some toys are not very good, different toys are prohibited from being sold to children each day. Specifically, on day $i$, children cannot purchase toys with indices in the range $[l_i, r_i]$.

In addition, to prevent the children from being too happy, each toy has a purchase limit $t_i$. That is, for the $i$-th toy, the number of items each child buys each day must be a non-negative integer not exceeding $t_i$.

For each day, you need to find: the sum of the maximum pleasure all children can obtain (modulo $10^8+7$), and the XOR sum of the maximum pleasure all children can obtain (the XOR operation is the $\text{xor}$ operation, i.e., the ^ operator in C++/Java/Python).

This problem is forced online; the specific rules are described in the input format.

Input

The input contains multiple test cases. The first line contains an integer $T$, representing the number of test cases. For each test case:

The first line contains three integers $n, m, Q$, representing the number of toys, the number of children, and the number of days, respectively.

The second line contains $n$ non-negative integers, describing the unit prices $c_1, c_2, \dots, c_n$ of each toy.

The third line contains $n$ non-negative integers, describing the pleasure $v_1, v_2, \dots, v_n$ of each toy.

The fourth line contains $n$ non-negative integers, describing the purchase limits $t_1, t_2, \dots, t_n$ of each toy.

From the fifth line to the $(Q+4)$-th line, each line contains two parameters $x, y$ describing the range. The $i+4$-th line and the answer from the previous day describe the range of prohibited toy indices for day $i$. Assuming the sum of maximum pleasure from the previous day is $\mathrm{lastans}$, then $l_i$ and $r_i$ for the current day satisfy: $$ l_i = \min((x + \mathrm{lastans} − 1) \bmod n + 1 , (y + \mathrm{lastans} − 1) \bmod n + 1) $$ $$ r_i = \max((x + \mathrm{lastans} −1) \bmod n + 1 , (y + \mathrm{lastans} − 1) \bmod n + 1) $$

On the first day, we assume $\mathrm{lastans}=0$. It is guaranteed that $1 \leq x, y \leq n$.

Output

For each test case, output $Q$ lines. Each line contains two integers, representing the sum of the maximum pleasure all children can obtain (modulo $10^8+7$) and the XOR sum, respectively.

Examples

Input 1

2
3 10 3
2 3 3
20 50 24
3 1 10
1 1
2 2
3 3
2 7 3
6 7
1 2
1 1
1 1
2 2
1 2

Output 1

568 120
660 20
660 20
2 2
2 0
0 0

Subtasks

$1 \leq n, m, Q \leq 10^3$, $1 \leq t_i, c_i \leq 10^3$, $1 \leq v_i \leq 2.5 \times 10^5$.

It is guaranteed that for all data, $\sum n, \sum m, \sum Q \leq 10^4$.