U573250 强制在线寂寂寞寞队
题目背景
那一天的寂寞，寂寞起来。
题目描述
马嘉祺购买了一套 $N$ 个彩色柠檬（其中有些颜色可能相同），摆成一排，你需要回答马嘉祺的提问。马嘉祺会向你发布如下指令：
1. $Q\ L\ R$ 代表询问你从第 $L$ 个柠檬到第 $R$ 个柠檬中共有几种不同颜色的柠檬。
2. $R\ P\ C$ 把第 $P$ 个柠檬替换为颜色 $C$ 柠檬 。
为了满足马嘉祺的要求，你知道你需要干什么了吗？
本题 **强制在线**，马嘉祺会给定一个值 $lemon$，设上一次询问的答案为 $ans$，每次你得到的 $L,R,P,C$ 都需要解密，解密方式为：
$$
l \gets ((l\oplus (lemon \times ans)+114514) \bmod n)+1 \\
r \gets ((r\oplus (lemon \times ans)+114514) \bmod n)+1\\
p \gets ((p\oplus (lemon \times ans)+1919810) \bmod n)+1\\
c \gets ((c\oplus (lemon \times ans)+1919810)\bmod 10^6) +1
$$
注意当 $l>r$ 时记得交换。
```cpp
int to1(int x){
return ((x^(lemon*lst))+114514)%n+1;
}
int to2(int x){
return ((x^(lemon*lst))+1919810)%n+1;
}
int to3(int x){
return ((x^(lemon*lst))+1919810)%(1000000)+1;
}
```
输入格式
第 $1$ 行一个整数 $lemon$，表示密码子。
第 $2$ 行两个整数 $N$，$M$，分别代表初始柠檬的数量以及马嘉祺会做的事情的个数。
第 $3$ 行 $N$ 个整数，分别代表初始柠檬排列中第 $i$ 个柠檬的颜色。
第 $4$ 行到最后，每行分别代表马嘉祺会做的一件事情，格式见题干部分。
输出格式
共 $cnt$ 行，$cnt$ 表示询问的个数。
说明/提示
时代少年团我们喜欢你。
对于 $30 \%$ 的数据，满足 $lemon=0$。
对于 $100 \%$ 的数据，满足 $n \le 50000,m\le 50000,V\le 1000000,lemon \le 1000$。