10342: J

Memory Limit:128 MB Time Limit:10.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

有两个长n的数组a[1..n]b[1..n],对这个两个数组进行两种操作。为了描述方便,我们先定义一个函数 f(n)f(n)返回n232的余数。

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

输入只有一组数据。

每组数据第一行为两个整数nm(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