Toy Shop Delight

In city C, Kinmei and Frez run a toy shop that offers n types of toys numbered from 1 to n. The i-th toy has a price of $c_i$ yuan and provides a pleasure value of $v_i$. Moreover, each toy i can be bought at most $t_i$ times per child per day.

Suddenly, m children arrive in city C. Reliable sources tell us that for the next Q days, these children will visit the shop daily; specifically, on each day, the i-th child (for $1 \le i \le m$) brings exactly $i$ yuan.

However, on each day d the shop restricts the sale of certain toys. In particular, on day d the toys with indices in the interval $[l_d, r_d]$ are banned and cannot be purchased.

For each day, every child will choose a set of available toys (subject to the purchase limits) such that the total cost does not exceed the money he/she has. Define the maximum pleasure obtainable for a given budget as the maximum total pleasure value that can be achieved using the available toys.

Your task is to compute for each day:

• The sum of the maximum pleasure values for all children (children are numbered 1 to m), modulo $10^8+7$.
• The bitwise XOR (using the \( \operatorname{xor} \) operator) of the maximum pleasure values for these children.

Note: This is an online problem. The queries for each day must be answered as they are received.

inputFormat

The first line contains three integers n, m, and Q, representing the number of toy types, the number of children, and the number of days (queries) respectively.

The second line contains n integers $c_1,c_2,\ldots,c_n$, where $c_i$ is the price of the i-th toy.

The third line contains n integers $v_1,v_2,\ldots,v_n$, where $v_i$ is the pleasure value provided by the i-th toy.

The fourth line contains n integers $t_1,t_2,\ldots,t_n$, where $t_i$ is the maximum number of copies of the i-th toy that any child can buy in a single day.

Then Q lines follow. Each line contains two integers $l_d$ and $r_d$, indicating that on day d the toys with indices in the range $[l_d, r_d]$ are banned.

Online Requirement: Each query (day) should be processed in the order it is given.

outputFormat

For each day, output a line containing two integers separated by a space:

• The sum of the maximum pleasure values for each child (modulo $10^8+7$).
• The bitwise XOR of the maximum pleasure values for all children.

sample

3 3 2
1 2 3
2 4 6
1 1 1
1 2
2 3

6 6

</p>