#2410. 「THUPC 2017」钦妹的玩具商店 / Toyshop

内存限制:64 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: sqc

题目描述

钦妹和弗雷兹在 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 取模)以及异或和。

样例

样例输入

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\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