数组(array)

题目描述

有一个数组 $a$ 和一个集合 $S$，初始每一个数 $a_i$ 都有一个值 $0$ 或 $1$ 且 $S$ 为空。一开始每个数是多少都是未知的。每次可能进行以下三种操作：

1. $\text{MERGE}\ k\ T$：给定集合 $T$，保证 $T$ 的大小为 $k$ 且与 $S$ 的交集为空。令 $x=\displaystyle\bigvee_{i\in T}a_i$，对于集合 $T$ 里所有 $i$，将 $a_i$ 修改为 $x$。
2. $\text{GET}\ x\ y$：保证 $x\not\in S$，已知当前 $a_x=y$，且若 $y$ 等于 $1$ 则将 $x$ 加入集合 $S$。
3. $\text{QUERY}\ p$：询问在满足当前已知的所有信息的情况下，命题 $\forall i\not\in S,a_i=0$ 是否一定为真。若为假，则询问序列 $p,p+1,p+2,\dots n,1,2,\dots p-1$ 中第一个可能使得 $i\not\in S\and a_i\not= 0$ 的数 $i$。

输入格式

本题强制在线。

第一行三个正整数 $n,m,t$，分别表示数组大小，操作次数和强制在线常数。

接下来是 $m$ 行，每行先输入一个字符串 $s$：

• 若 $s$ 为 MERGE，表示是操作 $1$，接下来输入一个数 $k$ 表示集合 $T$ 的大小，后面紧跟 $k$ 个数 $x_i$，表示集合 $T$ 内的元素。
• 若 $s$ 为 GET，表示是操作 $2$，接下来输入两个数 $x,y$。
• 若 $s$ 为 QUERY，表示是操作 $3$，接下来输入一个数 $x$。

需要注意的是，输入中每一个 $x$，令上一次的询问结果为 $lastans$（若没有询问或上次询问命题一定为真则为 $0$，否则为输出中唯一的数），真实值为 $((x-1+t\times lastans)\bmod n)+1$。

输出格式

对于每次 $3$ 操作，第一行一个字符串为 YES 或 NO，表示命题是否为真。若输出为 NO 则需要再输出一个数 $i$，$i$ 的定义如题目描述。

输入输出样例 1

说明/提示

样例解释：

第一次询问，每个数的值都不知道，所以第一个可能不确定的数是 $1$。

第二次询问，当前可能的情况有以下两种：

0 0 0 0 1，0 1 1 1 1

而集合 $S$ 内只有元素 $5$，所以命题为假，从 $5$ 开始的序列第一个可能不为 $0$ 的位置是 $2$。

第三次询问，当前序列只能是 0 0 0 0 1，此时集合 $S$ 内有元素 $5$，命题为真。

数据范围：

对于全部的数据，$1\le k,x \le n\le 500000$，$1\le m\le 1000000$，$1\le \sum k\le 1000000$，$0\le t,y\le 1$。保证任意时刻输入总能存在一种最初的数组 $a$ 使得每个 $2$ 操作符合真实情况。