题目描述

给定一个长度为 $n$、初始元素全为 $0$ 的数组 $a[1\ldots n]$，以及一个长度为 $n$ 的数组 $p[1\ldots n]$。需要处理 $q$ 个操作，操作分为两类：

1. 更新操作（opt = 1） 给定四个整数 $(\texttt{opt}=1,\, l,\, r,\, x)$。对所有下标满足 $l \le i \le r$ 的位置，将 $a_i$ 加上 $x$：$\forall\,i\in[l,r], a_i \leftarrow a_i + x.$
2. 查询操作（opt = 2） 给定三个整数 $(\texttt{opt}=2,\, l,\, r)$。计算并输出：$\sum_{i=l}^{r} a_{p_i}.$

每次操作输入前需要对输入参数 按上一次查询的答案异或（第一次查询前不异或）。记上一次输出的查询答案为 $\texttt{ans}$（初始时 $\texttt{ans}=0$）。读入的每次操作的参数 $l,r,x$（若存在）都需要先与 $\texttt{ans}$ 做异或再使用。

输入格式

• 第一行：两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$）。
• 第二行：数组 $p$ 的 $n$ 个整数（下标从 $1$ 开始，且 $1 \le p_i \le n$）。
• 接下来每行表示一个操作，格式为两种之一：
  • 更新操作：$1 ,l,r, x$
  • 查询操作：$2 ,l, r$

输出格式

对每个查询操作（即所有$2$操作），输出一行，一个整数，表示 $\displaystyle \sum_{i=l}^{r} a_{p_i}$ 的值（使用异或上一次的答案后的 $l,r$ 进行计算），并把该输出记为新的答案（用于后续操作的异或）。

输入输出样例 #1

输入 #1

6 10
3 6 5 1 2 6
1 1 3 8
1 2 3 9
1 2 5 4
1 2 3 9
2 1 3
1 33 33 38
1 32 32 35
2 35 33
1 36 34 36
2 39 35

输出 #1

34
38
81