Pixie has a rooted tree with $n$ nodes, where node $1$ is the root.

Pixie loves polynomials, so he has written a polynomial on each node.

One day, Key saw this tree. For a node $x$, Key defines $F(x)$ as the product of the polynomials on all nodes in the subtree of $x$. Now, Key gives you $q$ queries. Each query is in the form $x\ l\ r$, and you need to tell Key the value of $\left(\sum_{i=l}^r[x^i]F(x)\right)\bmod 998244353$.

Since Key is eager to know the answers, the queries are forced to be online.

Input

The first line contains two positive integers $n$ and $q$, representing the number of nodes in the tree and the number of queries, respectively.

The next $n$ lines describe the polynomials. The $i$-th line (for $i=1$ to $n$) starts with an integer $k_i$, the degree of the polynomial at node $i$. This is followed by $k_i+1$ integers $a_{i,0} \sim a_{i,k_i}$, representing the coefficients of the terms from degree $0$ to $k_i$.

The next $n-1$ lines each contain two positive integers $u, v$, representing an edge in the tree.

The next $q$ lines each contain three integers $x', l', r'$. The actual query parameters are $x=x' \operatorname{xor} \operatorname{lastans}$, $l=l' \operatorname{xor} \operatorname{lastans}$, and $r=r' \operatorname{xor} \operatorname{lastans}$, where $\operatorname{lastans}$ is the answer to the previous query. If there is no previous query, $\operatorname{lastans}$ is $0$.

Output

Output $q$ lines, each representing the answer to a query.

Examples

Input 1

3 6
1 1 1 
1 1 1 
1 1 1 
1 2
2 3
1 0 3
10 9 10
0 3 0
3 3 3
1 1 1
2 2 2

Output 1

8
3
2
3
1
0

Note

The decrypted input is:

3 6
1 1 1
1 1 1
1 1 1
1 2
2 3
1 0 3
2 1 2
3 0 3
1 1 1
2 2 2
3 3 3

Where $F(3)=1+x, F(2)=1+2x+x^2, F(1)=1+3x+3x^2+x^3$.

Constraints

For $100\%$ of the data, $1 \leq n \leq 10^5$, $0 \leq k_i$, $\sum k_i \leq 10^5$, $1 \leq q \leq 2 \times 10^5$, $1 \leq u,v,x \leq n$, $0 \leq l \leq r \leq \sum k_i$, $0 \leq a_{i,j} \leq 998244352$.

Subtasks