题目描述

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

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

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

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

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

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

输入格式

从标准输入读入数据。

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

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

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

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

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

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

$$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)) $$

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

输出格式

输出到标准输出。

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

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

提示

对于所有的数据，$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$。

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。