F. Forest Game
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a game that Alice and Bob play on an undirected graph.

First, Bob chooses $$$k$$$ vertices uniformly at random and marks them as special. Alice does not know which vertices are special. Then Alice chooses a walk consisting of at most $$$m$$$ edges starting from vertex $$$x$$$. If one of the vertices visited by the walk is special, Alice wins, otherwise Bob wins. In particular, if vertex $$$x$$$ is special, Alice wins.

Given a graph with $$$n$$$ vertices and no edges initially, your task is to process two types of queries:

  1. $$$1 \ u \ v$$$ – add an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that $$$v$$$ was not reachable from $$$u$$$ before the query.
  2. $$$2 \ x \ m \ k$$$ – find the probability that Alice wins the game with the parameters $$$x$$$, $$$m$$$ and $$$k$$$ on the current graph if she plays optimally.
Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 2\times 10^5, 1\le q \le 5\times 10^5$$$) — the number of vertices and queries.

The next $$$q$$$ lines contain the descriptions of queries. The queries are given in an encoded format. Each query is a line starting with an integer $$$t$$$ ($$$1 \le t \le 2$$$) — the type of the query.

  • If $$$t=1$$$, then two integers $$$u \oplus last$$$ and $$$v \oplus last$$$ follow ($$$1 \le u, v \le n$$$, $$$u \ne v$$$).
  • If $$$t=2$$$, then three integers $$$x \oplus last$$$, $$$m \oplus last$$$ and $$$k \oplus last$$$ follow ($$$1 \le x \le n$$$, $$$1 \le m \le 10^9$$$, $$$1 \le k \le n$$$).
Here $$$last$$$ denotes the answer to the last type 2 query or $$$0$$$ if there were no type 2 queries previously, and $$$\oplus$$$ denotes the bitwise XOR operation.
Output

For each type 2 query, print the probability modulo $$$998244353$$$.

Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output an integer $$$x$$$ such that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Example
Input
4 6
2 2 2 2
1 499122176 499122179
1 499122179 499122181
2 499122181 499122179 499122178
1 2 5
2 3 2 0
Output
499122177
1
249561089