Problem Description

Qin Mei and Frez have a toy shop in City C. The shop sells $n$ kinds of toys, numbered $1,2,\ldots,n$. The unit price of the $i$-th toy is $c_i$ yuan, and buying one such toy provides happiness $v_i$.

One day, $m$ children came to City C. According to reliable information, during the next $Q$ days, these children will come to the shop every day to buy things. The $i$-th child brings $i$ yuan every day ($1\le i\le m$).

Since some toys are not very good, each day different toys will be banned from being sold to children. Specifically, on day $i$, toys with indices in the interval $[l_i,r_i]$ cannot be bought by children.

In addition, to prevent the children from being too happy, each toy has a purchase limit $t_i$. That is, for the $i$-th kind of toy, each child can buy a non-negative integer number of items per day, and this number must not exceed $t_i$.

Now, for each day, you want to know:

• The sum of the maximum happiness that all children can obtain (modulo $10^8+7$).
• The xor of the maximum happiness that all children can obtain (the xor operation is $\operatorname{xor}$, i.e. the ^ operator in C++/Java/Python).

This problem is forced online, and the specific rules are reflected in the input description.

Input Format

Read from standard input.

The input contains multiple test cases. The first line contains an integer $T$, 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.

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

The third line contains $n$ non-negative integers, describing the happiness values $v_1,v_2,\ldots,v_n$.

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

Lines $5$ to $Q+4$ each contain two integers $x,y$ describing an interval. The $i$-th line and the previous day's answer together determine the forbidden index interval on day $i$. Suppose the previous day's sum of maximum happiness is $\operatorname{lastans}$. Then $l_i,r_i$ satisfy:

$$l_i=\min((x+\operatorname{lastans}-1)\bmod n+1,(y+\operatorname{lastans}-1)\bmod n+1)$$$$r_i=\max((x+\operatorname{lastans}-1)\bmod n+1,(y+\operatorname{lastans}-1)\bmod n+1)$$

On the first day, we define $\operatorname{lastans}=0$. It is guaranteed that $1\le x,y\le n$.

Output Format

Write to standard output.

For each test case, output $Q$ lines. Each line contains two integers, in order:

• The sum of the maximum happiness that all children can obtain (modulo $10^8+7$).
• The xor of the maximum happiness that all children can obtain.

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

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

Hint

Constraints: For all testdata, $1\le n,m,Q,c_i,t_i\le 10^3$, $1\le v_i\le 2.5\times 10^5$, $\sum n,\sum m,\sum Q\le 10^4$.

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2017.

Translated by ChatGPT 5