{"raw_statement":[{"iden":"problem statement","content":"**Beware the special input format and the smaller memory limit than usual.**\nThere is an undirected graph with vertices $1, 2, \\dots, N$, initially without edges.  \nYou need to process the following $Q$ queries on this graph:\n  \n\n1 $u$ $v$\n\nType $1$: Add an edge between vertices $u$ and $v$.  \nBefore adding the edge, $u$ and $v$ belong to different connected components (i.e., the graph always remains a forest).\n  \n\n2 $u$ $v$\n\nType $2$: If there is a vertex adjacent to both $u$ and $v$, report its vertex number; otherwise, report $0$.  \nGiven that the graph always remains a forest, the answer to this query is uniquely determined.\n  \n\nThe queries are given in an encrypted form.  \nThe original query is defined by three integers $A, B, C$, and the encrypted query is given as three integers $a, b, c$.  \nLet $X_k$ be the answer to the $k$\\-th type-$2$ query. Define $X_k = 0$ for $k = 0$.  \nRestore $A, B, C$ from the given $a, b, c$ as follows:\n\n*   Let $l$ be the number of type-$2$ queries given before this query (not counting the query itself). Then, use the following:\n    *   $A = 1 + (((a \\times (1+X_l)) \\mod 998244353) \\mod 2)$\n    *   $B = 1 + (((b \\times (1+X_l)) \\mod 998244353) \\mod N)$\n    *   $C = 1 + (((c \\times (1+X_l)) \\mod 998244353) \\mod N)$"},{"iden":"constraints","content":"*   All input values are integers.\n*   $2 \\le N \\le 10^5$\n*   $1 \\le Q \\le 10^5$\n*   $1 \\le u < v \\le N$\n*   $0 \\le a,b,c < 998244353$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $Q$\n$\\rm{Query}$$_1$\n$\\rm{Query}$$_2$\n$\\vdots$\n$\\rm{Query}$$_Q$"},{"iden":"sample input 1","content":"6 12\n143209915 123840720 97293110\n89822758 207184717 689046893\n67757230 270920641 26993265\n952858464 221010240 871605818\n730183361 147726243 445163345\n963432357 295317852 195433903\n120904472 106195318 615645575\n817920568 27584394 770578609\n38727673 250957656 506822697\n139174867 566158852 412971999\n205467538 606353836 855642999\n159292205 319166257 51234344"},{"iden":"sample output 1","content":"0\n2\n0\n2\n6\n0\n1\n\nAfter decrypting all queries, the input is as follows:\n\n6 12\n2 1 3\n1 2 6\n1 2 4\n1 1 3\n2 4 6\n2 1 4\n1 5 6\n1 1 2\n2 1 4\n2 2 5\n2 3 4\n2 2 3\n\nThis input has a $6$\\-vertex graph and $12$ queries.\n\n*   The first query is `2 1 3`.\n    *   No vertex is adjacent to both vertex $1$ and vertex $3$, so report $0$.\n*   The second query is `1 2 6`.\n    *   Add an edge between vertices $2$ and $6$.\n*   The third query is `1 2 4`.\n    *   Add an edge between vertices $2$ and $4$.\n*   The fourth query is `1 1 3`.\n    *   Add an edge between vertices $1$ and $3$.\n*   The fifth query is `2 4 6`.\n    *   The vertex adjacent to both vertices $4$ and $6$ is vertex $2$.\n*   The sixth query is `2 1 4`.\n    *   No vertex is adjacent to both vertices $1$ and $4$, so report $0$.\n*   The seventh query is `1 5 6`.\n    *   Add an edge between vertices $5$ and $6$.\n*   The eighth query is `1 1 2`.\n    *   Add an edge between vertices $1$ and $2$.\n*   The ninth query is `2 1 4`.\n    *   The vertex adjacent to both vertices $1$ and $4$ is vertex $2$.\n*   The tenth query is `2 2 5`.\n    *   The vertex adjacent to both vertices $2$ and $5$ is vertex $6$.\n*   The eleventh query is `2 3 4`.\n    *   No vertex is adjacent to both vertices $3$ and $4$, so report $0$.\n*   The twelfth query is `2 2 3`.\n    *   The vertex adjacent to both vertices $2$ and $3$ is vertex $1$."},{"iden":"sample input 2","content":"2 1\n377373366 41280240 33617925"},{"iden":"sample output 2","content":"The output may be empty."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}