题目描述

钦妹和弗雷兹在 C 市有一个玩具店，店里有 $n$ 种玩具，编号依次为 $1,2,\dots, n$，第 $i$ 件玩具的单价为 $c_i$ 元，一个该玩具提供的愉♂悦度为 $v_i$ 。

突然有一天，C 市来了 $m$ 个小朋友。据可靠消息，接下来 $Q$ 天，这些小朋友每天都会来店里买东西，其中第 $i$ 个小朋友每天都会带 $i$ 元 $(1\leq i\leq m)$ 。

由于某些玩具不是很优秀，所以每天都会有不同的玩具被禁止出售给小朋友。具体来说，在第 $i$ 天，编号在区间 $\left[l_i,r_i\right]$ 内的物品小朋友是不能购买的。

除此之外，为了防止小朋友们太愉悦，每件玩具都有一个限购件数 $t_i$ 。也就是说，对于第 $i$ 种玩具，每个小朋友在每一天的购买件数都必须为不超过 $t_i$ 的非负整数。

现在，对于每一天，你想知道：所有小朋友所能获得的最大愉悦度之和（对 $10^8+7$ 取模）；所有小朋友所能获得的最大愉悦度的异或和（异或运算是 $\text{xor}$ 运算，即 C++/Java/Python 中的 ^ 运算）。

本题强制在线，具体规则在输入描述中体现。

输入格式

从标准输入读入数据。

输入包含多组数据。第一行有一个整数 $T$ ，表示测试数据的组数，对于每组数据：

第一行输入三个整数 $n,m,Q$ 分别表示玩具数目、小朋友的数目以及天数。

第二行 $n$ 个非负整数，分别描述每件玩具的单价 $c_1,c_2,\dots, c_n$ 。

第三行 $n$ 个非负整数，分别描述每件玩具的愉悦度 $v_1,v_2,\dots ,v_n$ 。

第四行 $n$ 个非负整数，分别描述每件玩具的限购次数 $t_1,t_2,\dots ,t_n$ 。

第五行到第 $Q+4$ 行，每行两个描述区间的参数 $x,y$ 。第 $i+4$ 行和前一天的答案共同描述了第 $i$ 天禁止购买的编号区间，假设前一天的最大愉悦度之和为 $\mathrm{lastans}$ ，那么当天的 $l_i,r_i$ 满足下式： $$ 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) $$

在第一天时，我们认为 $\mathrm{lastans}=0$ 。保证 $1\leq x,y\leq n$ 。

输出格式

输出到标准输出。

对于每一组数据，输出 $Q$ 行，每行 $i$ 个整数，依次表示所有小朋友能够获得的最大愉悦度之和（对 $10^8+7$ 取模）以及异或和。

样例

input

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

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

数据范围与提示

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

保证对于所有的数据， $\sum n,\sum m,\sum Q\leq 10^4$。