頂点 $1$ のみからなる単純無向グラフ $G$ があります。頂点 $1$ は赤に塗られています。

$Q$ 個のクエリを順に処理してください。クエリは以下の $2$ 種類のいずれかです。

• 1 x c：現時点におけるグラフ $G$ の頂点数を $V$ として、新しく頂点 $V+1$ をグラフ $G$ に追加し、無向辺 $(x, V+1)$ を張る。頂点 $V+1$ は、$c=1$ のとき白、$c=2$ のとき赤に塗られる。
• 2 x：$\min\limits_{i\in R}\mathrm{dist}(x,i)$ を出力する。ただし、$R$ は現時点における赤の頂点からなる頂点集合であり、$\mathrm{dist}(a,b)$ は頂点 $a$ から頂点 $b$ へ移動するときに用いる辺の本数の最小値である。

ただし、上記のクエリは暗号化されて与えられます。以下の手順で本来のクエリを復号してからクエリを処理してください。

• クエリが与えられる直前におけるグラフ $G$ の頂点数を $V$ とおく。また、これまでに与えられた 2 x 形式のクエリのうち、最も直前に与えられたクエリに対する答えを $K$ とおく。ただし、そのようなクエリが与えられていない場合は $K=0$ と定める。
• 暗号化された入力として $3$ つの整数 $\alpha, \beta, \gamma$ が与えられるので、これらを受け取る。
• 整数 $t$ を $t \gets 1 + (((\alpha \times (1+K)) \bmod 998244353 ) \bmod 2)$ とおく。
  • $t=1$ のときは、1 x c 形式のクエリに対応する入力が与えられることを意味する。暗号化された入力 $\beta, \gamma$ に対し、以下の手順で整数 $x, c$ を復号する。
    • $x \gets 1 + (((\beta \times (1+K)) \bmod 998244353 ) \bmod V)$
    • $c \gets 1 + (((\gamma \times (1+K)) \bmod 998244353 ) \bmod 2)$
  • $t=2$ のときは、2 x 形式のクエリに対応する入力が与えられることを意味する。暗号化された入力 $\beta$ に対し、以下の手順で整数 $x$ を復号する。この形式のクエリにおいて、$\gamma$ は復号処理に使用されないことに注意せよ。
    • $x \gets 1 + (((\beta \times (1+K)) \bmod 998244353 ) \bmod V)$

• $1 \leq Q \leq 10^5$
• 暗号化された入力は、以下の制約を満たす
  • $0 \leq \alpha, \beta, \gamma < 998244353$
• 復号した後の入力は、以下の制約を満たす
  • $t \in \lbrace 1, 2\rbrace$
  • $1 \leq x \leq V$ $($ $V$ はそのクエリが与えられる直前におけるグラフ $G$ の頂点数である$)$
  • $c \in \lbrace 1, 2\rbrace$
• 入力はすべて整数である

• set1 $(10$ 点$)$：1 x c の形式のクエリにおいて $c=2$ を満たすクエリの個数は高々 $20$ 個である
• all $(90$ 点$)$：追加の制約はない

入力は以下の形式で標準入力から与えられます。

各クエリは以下の形式で与えられます。

問題文の指示に従って、クエリの答えを改行区切りで出力してください。