You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

美穗喜欢数据结构，所以她给了你一道数据结构题。

给定一个长度为 $n$ 的整数序列 $a$，有以下几种操作：

• $\texttt{1}\ x$：在 $a$ 末尾加入一个整数 $x$。
• $\texttt{2}\ x$：将 $a_x$ 变为原来的平方。
• $\texttt{3}\ x$：查询 $a_x$ 的值。

请你用数据结构维护一下吧！

输入格式

第一行为两个正整数 $n,q$，后者表示操作次数。

由于出题人懒得造数据，所以 $a_i$ 和操作都将按下述方式随机生成。

与 P1123 [CZOJ 一周一测 R15 A] 刺客传奇 不同，本题正解不依赖数据生成方式。

第二行输入一个正整数 $p$。

则 $a$ 的生成方式为：

• $a_1=p,a_2=q\times p-1$。
• $a_i=(a_{i-1}^2+(q\times a_{i-2})\bmod i+a_{i-2}\times 839730577)\bmod 10^8+1$

第三行输入两个正整数 $\text{op}',x'$。

对于第 $i\in [1,q]$ 次操作，其操作方式 $\text{op}$ 和操作参数 $x$ 将按如下方式生成：

• $\text{op}=(\text{op}'\times x'\times(\text{op}'+x'+i)+x'-\text{op}'+3)\bmod 3+1$。
• $x=((\text{op}'\times x'+21)\times (i+\text{op}'+9)\times i)\bmod n'+1$。

其中 $n'$ 表示当前序列 $a$ 的长度。

每次操作完成上述操作后，将 $\text{op},x$ 作为新的 $\text{op}',x'$。

输出格式

假设每个操作 $3$ 所查询的结果对 $998244853$ 取模后的答案分别为 $c_1,c_2,\cdots,c_q$，则用一行输出 $c_i$ 的按位异或和（异或的过程和结果不需要取模）。

样例

5 5
7
1 12

9418825

15 20
8
12 22

18049235

样例 $\textbf 1$ 解释

生成的 $a$ 为 $\{7,34,78115198,9418825,53389872\}$。

生成的操作依次为：

3 4
2 5
2 3
2 1
1 1

所以显然答案为 $9418825$。

数据范围

对于 $100\%$ 的数据，$1\le n,q\le 10^3,1\le p,x'\le 10,1\le \text{op}'\le 3$。