AT_abc350_g [ABC350G] Mediator

[problemUrl]: https://atcoder.jp/contests/abc350/tasks/abc350_g **特殊な入力形式に注意してください。 また、メモリ制限が通常より小さいことに注意してください。** 頂点 $ 1,2,\dots,N $ の $ N $ 頂点からなる無向グラフがあり、最初辺はありません。 このグラフに対して、以下の $ Q $ 個のクエリを処理してください。 > 1 $ u $ $ v $ タイプ $ 1 $ : 頂点 $ u $ と頂点 $ v $ との間に辺を追加する。 辺を追加する前の時点で、 $ u $ と $ v $ は異なる連結成分に属する。(すなわち、グラフは常に森である。) > 2 $ u $ $ v $ タイプ $ 2 $ : 頂点 $ u $ と頂点 $ v $ の双方に隣接する頂点があるならその番号を答え、無ければ $ 0 $ と答える。 グラフが常に森であることから、このクエリに対する解答は一意に定まることが示せる。 但し、上記のクエリは暗号化して与えられます。 本来のクエリは $ 3 $ つの整数 $ A,B,C $ として定義され、これをもとに暗号化されたクエリが $ 3 $ つの整数 $ a,b,c $ として与えられます。 タイプ $ 2 $ のクエリのうち、先頭から $ k $ 個目のものに対する解答を $ X_k $ とします。 さらに、 $ k\ =\ 0 $ に対して $ X_k\ =\ 0 $ と定義します。 与えられた $ a,b,c $ から以下の通りに $ A,B,C $ を復号してください。 - そのクエリより前に与えられたタイプ $ 2 $ のクエリの個数を $ l $ とする(そのクエリ自身は数えない)。このとき、以下の通りに復号せよ。 - $ A\ =\ 1\ +\ (((a\ \times\ (1+X_l))\ \mod\ 998244353)\ \mod\ 2) $ - $ B\ =\ 1\ +\ (((b\ \times\ (1+X_l))\ \mod\ 998244353)\ \mod\ N) $ - $ C\ =\ 1\ +\ (((c\ \times\ (1+X_l))\ \mod\ 998244353)\ \mod\ N) $

入力は以下の形式で標準入力から与えられる。 但し、 $ \rm{Query} $$ _i $ は $ i $ 個目のクエリを表す。 > $ N $ $ Q $ $ \rm{Query} $$ _1 $ $ \rm{Query} $$ _2 $ $ \vdots $ $ \rm{Query} $$ _Q $

タイプ $ 2 $ のクエリの個数を $ k $ としたとき、全体で $ k $ 行出力せよ。 そのうち $ i $ 行目には、タイプ $ 2 $ のクエリのうち、先頭から $ i $ 個目のものに対する解答を出力せよ。

### 制約 - 入力は全て整数 - $ 2\ \le\ N\ \le\ 10^5 $ - $ 1\ \le\ Q\ \le\ 10^5 $ - $ 1\ \le\ u\