10342: J

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

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])是多少。

输入只有一组数据。

每组数据第一行为两个整数n，m(1 ≤ n, m ≤ 10⁵)。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)。前者表示第一种操作，后者表示第二种操作。各参数意义见描述。

输入的每行，所有数字之间都用一个空格分开。

对于每组数据的每个第二种操作，输出查询的结果。每个输出占一行。

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

10
4