10342: J
Description
有两个长n的数组a[1..n]和b[1..n],对这个两个数组进行两种操作。为了描述方便,我们先定义一个函数 f(n)。f(n)返回n模232的余数。
1. 给出一对区间边界 x, y(1 ≤ x ≤ y ≤ n),和四个参数 p, q, r, s。对于每个 i(x ≤ i ≤ y),计算 tmpa = f(a[i] × p + b[i] × q); tmpb = f(a[i] × r + b[i] × s)。然后再使得 a[i] = tmpa; b[i] = tmpb。
2. 给出一对区间边界 x, y(1 ≤ x ≤ y ≤ n),询问 f(∑[x ≤ i ≤ y] a[i] × b[i])是多少。
Input
输入只有一组数据。
每组数据第一行为两个整数n,m(1 ≤ n, m ≤ 105)。n意义见描述,m表示操作数目。
接下来一行为n个正整数,表示a[1..n],数组中每个数不超过1000。
接下来一行为n个正整数,表示b[1..n],数组中每个数不超过1000。
之后是m行表示m个操作。每个操作命令的格式是“1 x y p q r s”(1 ≤ x ≤ y ≤ n, 0 ≤ p, q, r, s ≤ 1000)或者“2 x y”(1 ≤ x ≤ y ≤ n)。前者表示第一种操作,后者表示第二种操作。各参数意义见描述。
输入的每行,所有数字之间都用一个空格分开。
Output
对于每组数据的每个第二种操作,输出查询的结果。每个输出占一行。
Sample Input Copy
5 3
1 1 1 1 1
2 2 2 2 2
2 1 5
1 2 4 1 1 0 0
2 1 5
Sample Output Copy
10
4
HINT
操作第一组。∑[1 ≤ i ≤ 5] a[i] × b[i] = 2 + 2 + 2 + 2 + 2 = 10。输出10。
操作第二组,数组a变成1 3 3 3 1,数组b变成2 0 0 0 2。
操作第三组。∑[1 ≤ i ≤ 5] a[i] × b[i] = 2 + 0 + 0 + 0 + 2 = 4。输出4。