Original Description

NPSC 國是個團結的國家。「轉」作為該國的古老文化之一，幾乎所有 NPSC 國的程式競賽選手，在寫到平衡二元樹（balanced binary tree）相關的題目時都會寫伸展樹（splay tree）。然而，總會有一些意圖破壞國家和諧的分離主義者，他們總是寫「分裂／合併式樹堆」（merge-split treap），意圖分裂族群。為了維護二元樹的主權與領土完整，NPSC 國通過了《反分裂二元樹法》，以追蹤並調查這些傷害民族感情的人們。

NPSC 國的執法人員總共調查了 $N$ 個分離主義者，將他們編號為 $0$ 到 $N-1$，並且發現任兩個分離主義者之間都有直接聯繫。某一天，NPSC 國的情報單位發現了一些奇怪的現象，可以描述為很多個事件，每個事件都是這 $N$ 個人中的某 $K$ 個人不再與另外 $N-K$ 個人直接聯繫。調查人員認為這可能代表著分離主義者之間發生了內鬨，而開始分門結黨、彼此分離。這件事對國家的發展有重要影響，因此調查人員把每一個這樣的事件全部記錄在一份機密文件上。

你身為 CSPN 國的間諜，輾轉取得了這份文件。這份文件經過加密，但是你成功攔截到了解密這份文件的公式，因此你決定把它解密來研究，以備不時之需。

具體來說，要解密這份文件需要一個解密函數，定義為 $F(x)=(x\ \text{xor}\ A) \bmod N$，其中 $A$ 的初始值是給定的，但會隨著解密的過程改變。（$x\ \text{xor}\ A$ 代表 $x$ 和 $A$ 的「按位異或」（exclusive or），即 C / C++ 中的 $x$ ^ $A$ ； $p\bmod N$ 代表 $p$ 除以 $N$ 的餘數，即 C / C++ 中的$p\% N$ 。

這份文件解密前可以分為 $M$ 行，每行有許多個介於 $0$ 到 $2^ {32}-1$ 之間的非負整數，且都是下列兩種格式之一：

1. $1\ Q\ a_1\ a_2\ a_3 \cdots a_Q$: 代表編號為 $F(a_1),F(a_2),F(a_3),\cdots,F(a_Q)$ 的人們不再與其他 $N-Q$ 個人直接聯繫。若這群人的集合為 $T$，而所有人的集合為 $S$，在 $T$ 中的任兩人的聯繫狀態並不會改變，在 $S\setminus T$ 之間的任兩人亦同。一個人有可能在這個清單中出現兩次以上，但是與只出現一次是同樣的意思。保證$1\leq Q\leq N$。
2. $2\ a\ b$: 根據編號 $F(a),F(b)$ 的人當前是否有直接聯繫改變函數 $A$ 的值：若這兩人當前有直接聯繫，則將 $A$ 改變為 $(22695477A+1) \bmod 2^ {32}$；否則，將 $A$ 改變為 $(69069A+1) \bmod 2^ {32}$。假如 $F(a)=F(b)$，則視為兩人有直接聯繫。

這份文件是按照事件的發生順序排序，而一開始任兩個人都有直接聯繫。解密也必須按照文件的順序，也就是說遇到第二種格式時只依照所有該行之前的事件作判斷。

然而，因為這份文件實在是過於龐大，所以你決定寫一個程式來幫你解密這份文件。又因為把整份解密文件全部存下來比較費時，所以你決定先存下解密結束時的 $A$ 值就好了。

Original Input Format

輸入的第一行有三個非負整數 $N,M,A$，分別代表總人數、機密文件的行數與解密時初始的 $A$ 值。
接下來有 $M$ 行，代表要解密的文件。詳細的格式請見題目敘述。

• $2\leq N\leq 3\times 10^ 6$
• $1 \le M \le 5 \times 10^ 6$
• $A$ 與所有文件中的數字均是介於 $0$ 和 $2^ {32}-1$ 之間的整數
• $1 \le Q \le N$
• 整份要被解密的文件最多只會有 $5\times 10^ 6$ 個數字。

Original Output Format

請輸出一行包含一個非負整數，代表整份文件解密結束之後的 $A$ 值。

Original Sample Input

Sample Input 1:
3 2 1
1 1 7
2 0 2

Sample Input 2:
3 2 1
1 1 7
2 0 3

Original Sample Output

Sample Output 1:
69070

Sample Output 2:
22695478

Original Limits

• Time Limit: 6 second
• Memory Limit: 1024 MB

Program To Be Hacked

#include <cstdio>
#include <cstdint>

const int kN = 3000007;
uint32_t now[kN];
int vis[kN];
inline bool Query(int a, int b) { return now[a] == now[b]; }

int main() {
  srand(time(NULL));
  int N, M;
  uint32_t A;
  scanf("%d%d%u", &N, &M, &A);
  auto F = [&](uint32_t x){ return (A ^ x) % N; };
  uint32_t val = 213;
  while (M--) {
    int type, Q;
    uint32_t a, b;
    scanf("%d", &type);
    if (type == 2) {
      scanf("%u%u", &a, &b);
      A = (Query(F(a), F(b)) ? 22695477 : 69069) * A + 1;
    } else {
      scanf("%d", &Q);
      val = rand();
      
      while (Q--) {
        scanf("%u", &a); a = F(a);
        if (vis[a] == M) continue;
        vis[a] = M; now[a] ^= val;
      }
    }
  }
  printf("%u\n", A);
}

Judge Method

請輸出一筆測試資料，使得上述的程式碼會輸出錯的答案。

Sample Code

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。

#include <cstdio>
int main() {
    printf("3 2 1\n1 1 7\n2 0 2\n2 0 0\n");
}

Hint

你上傳的 code 當中，不能出現 clock 以及 time 這兩個子字串喔！