题目描述
钦妹和弗雷兹在 C 市有一个玩具店,店里有 n 种玩具,编号依次为 1,2,…,n,第 i 件玩具的单价为 ci 元,一个该玩具提供的愉♂悦度为 vi 。
突然有一天,C 市来了 m 个小朋友。据可靠消息,接下来 Q 天,这些小朋友每天都会来店里买东西,其中第 i 个小朋友每天都会带 i 元 (1≤i≤m) 。
由于某些玩具不是很优秀,所以每天都会有不同的玩具被禁止出售给小朋友。具体来说,在第 i 天,编号在区间 [li,ri] 内的物品小朋友是不能购买的。
除此之外,为了防止小朋友们太愉悦,每件玩具都有一个限购件数 ti 。也就是说,对于第 i 种玩具,每个小朋友在每一天的购买件数都必须为不超过 ti 的非负整数。
现在,对于每一天,你想知道:所有小朋友所能获得的最大愉悦度之和(对 108+7 取模);所有小朋友所能获得的最大愉悦度的异或和(异或运算是 xor 运算,即 C++/Java/Python 中的 ^
运算)。
本题强制在线,具体规则在输入描述中体现。
输入格式
从标准输入读入数据。
输入包含多组数据。第一行有一个整数 T ,表示测试数据的组数,对于每组数据:
第一行输入三个整数 n,m,Q 分别表示玩具数目、小朋友的数目以及天数。
第二行 n 个非负整数,分别描述每件玩具的单价 c1,c2,…,cn 。
第三行 n 个非负整数,分别描述每件玩具的愉悦度 v1,v2,…,vn 。
第四行 n 个非负整数,分别描述每件玩具的限购次数 t1,t2,…,tn 。
第五行到第 Q+4 行,每行两个描述区间的参数 x,y 。第 i+4 行和前一天的答案共同描述了第 i 天禁止购买的编号区间,假设前一天的最大愉悦度之和为 lastans ,那么当天的 li,ri 满足下式:
li=min((x+lastans−1)modn+1,(y+lastans−1)modn+1)
ri=max((x+lastans−1)modn+1,(y+lastans−1)modn+1)
在第一天时,我们认为 lastans=0 。保证 1≤x,y≤n 。
输出格式
输出到标准输出。
对于每一组数据,输出 Q 行,每行 i 个整数,依次表示所有小朋友能够获得的最大愉悦度之和(对 108+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≤n≤103,1≤m≤103,1≤Q≤103,1≤ti,ci≤103,1≤vi≤2.5×105。
保证对于所有的数据, ∑n,∑m,∑Q≤104。