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:

\(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.