Alice and Bob play a game. The game starts with a graph that contains $n$ nodes and no edges. You are required to process $q$ queries of two types:

• Add a directed edge from $u[i]$ to $v[i]$.
• Print $x[i]$ if there is a directed path from vertex 1 to vertex $x[i]$. Otherwise, print $0$.

Input format

• The first line contains $n$, $q$, and $t$ ($1 ≤ n,\ q ≤ 10^6,\ 0 ≤ t ≤ 1$)($1 ≤ n,\ q ≤ 10^6,\ 0 ≤ t ≤ 1$) denoting the number of nodes, the number of queries, and a constant number $t$.
• Next $q$ lines contain the queries, each with one of the following formats:
  1. Queries of the first type: $1\ a[i]\ b[i]\ (0 ≤ a[i], b[i]≤2\cdot10^9)$
  2. Queries of the second type: $2\ a[i]\ (0≤a[i]≤2\cdot10^9)$.

Nodes $u[i]$ and $v[i]$ for queries of the first type and node $x[i]$ for queries of the second type are generated as follows:

$u[i]=(a[i]⊕(t∗lastans))\ mod\ n + 1,\ v[i]\ =\ (b[i]⊕(t∗lastans))\\ mod\ n + 1\ u[i]=(a[i]⊕(t∗lastans))\ mod\ n+1,\ v[i]=(b[i]⊕(t∗lastans))\ mod\ n + 1$

$x[i]=(a[i]⊕(t∗lastans))\ mod\ n + 1\ x[i]=(a[i]⊕(t∗lastans))\ mod n + 1$

where $lastans$ denotes the answer for the last query of the second type (initially $lastans = 0$)

Output format

For each query of type 2, print one integer denoting the answer to the query.