Yuta 有一个包含 $n$ 个整数的数组 $A_1, A_2, \dots, A_n$，并保留了数组 $A$ 的初始内容作为 $A'$（初始时 $A'_i = A_i$）。随后，他会对数组 $A$ 执行 $m$ 次操作。

操作共有三种类型：

• “$1\ l\ r$”：Yuta 想要计算所有 $i \in [l, r]$ 的 $A_i$ 之和。
• “$2\ l\ r\ k$”：Yuta 对序列 $A$ 执行以下伪代码：

  for (int i = l; i <= r; i++) A[i] = A[i - k];

• “$3\ l\ r$”：对于所有 $i \in [l, r]$，Yuta 将 $A_i$ 恢复为 $A'_i$。

请帮助 Yuta 执行所有给定的操作。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2 \cdot 10^5$)。 第二行包含 $n$ 个整数 $A_i$ ($0 \le A_i \le 10^9$)。 接下来 $m$ 行，每行描述一个上述格式的操作。保证 $1 \le l \le r \le n$ 且 $1 \le k < l$。

输出格式

对于每种类型为 1 的操作，输出一行，包含一个整数：所需的总和。

样例

样例输入 1

5 7
1 2 3 4 5
1 1 5
2 3 4 1
1 1 5
2 3 4 2
1 1 5
3 1 5
1 1 5

样例输出 1

15
12
11
15