U406718 llch的线段树

有一个初始全为 $0$ 的数列，你需要进行下面两种操作： - 将某一个数加上 $x$ - 求出某区间每一个数的和 本题强制在线，每次操作的输入要异或上次询问的答案才为真实数据。

第一行包含两个正整数 $n,m$，表示序列长度和操作的总个数。 接下来 $m$ 行每行包含 $3$ 个整数，$op,x',y'$，表示一个操作，具体如下： 我们记 $last$ 为上一次询问的答案，初始为 $0$。 - $op$ 为 $1$ 时，记 $x=(x'\oplus last)~mod~n+1,y=(y'\oplus last)~mod~10^9$，使第 $x$ 个数加上 $y$。 - $op$ 为 $2$ 时，记 $x=(x'\oplus last)~mod~n+1,y=(y'\oplus last)~mod~n+1$，如果 $x>y$，则交换 $x,y$，输出区间 $[x,y]$ 内每个数的和。

输出包含若干行整数，即为所有操作 $2$ 的结果。

【样例说明】 对于样例二解密后的操作如下： | $op$ | $x$ | $y$ | | :----------: | :----------: | :----------: | | $1$ | $7$ | $678612580$ | | $2$ | $6$ | $8$ | | $2$ | $7$ | $2$ | | $1$ | $7$ | $827340629$ | | $1$ | $9$ | $800403455$ | | $2$ | $3$ | $6$ | | $1$ | $4$ | $816938232$ | | $2$ | $7$ | $2$ | | $1$ | $5$ | $97889120$ | | $1$ | $5$ | $886841096$ | 【数据范围】 对于 $20\%$ 的数据，$1\le n,m \le 10$。 对于 $40\%$ 的数据，$1\le n,m \le 10^4$； 对于 $60\%$ 的数据，$1\le n,m \le 5\times 10^5$； 对于 $100\%$ 的数据，$1\le m \le 5\times 10^5，1\le n \le 10^{18}$。 数据保证对于任意时刻，$a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $long~long$ 范围内。