Alice and Bob are playing a stone-taking game.

The game is played on an undirected graph consisting of a start node $S$, an end node $T$, and $n$ edge-disjoint paths connecting $S$ and $T$. The $i$-th path has $k_i$ edges, and the $j$-th edge has $a_{i,j}$ stones. Alice goes first, and then Alice and Bob take turns. In a player's turn, he or she must choose a non-empty, acyclic set of edges and remove a positive integer number of stones from each edge in the set. The number of stones removed from each edge does not have to be the same, but it cannot exceed the current number of stones on that edge. If a player cannot make a move, he or she loses the game.

Alice and Bob play the game multiple times. Alice wants every game to be different, so she decides to let the number of stones $a_{i,j}$ on each edge be chosen arbitrarily from the interval $[l_{i,j}, r_{i,j}]$. Please help Alice calculate how many possible scenarios exist where Alice can win, assuming both players play optimally. Since this number can be very large, you only need to output the result modulo $998\,244\,353$.

Input

The first line contains an integer $n$ ($1 \le n \le 500\,000$), representing the number of paths.

Each of the next $n$ lines contains $2k_i + 1$ integers representing a path. The first integer $k_i$ ($k_i \ge 1$) in the $i$-th line represents the number of edges on the $i$-th path, followed by $2k_i$ integers $l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}, \dots, l_{i,k_i}, r_{i,k_i}$ ($0 \le l_{i,j} \le r_{i,j} \le 500\,000$), representing the range of the number of stones on each edge.

It is guaranteed that $\sum_{1 \le i \le n} k_i \le 10^6$.

Output

Output a single integer representing the answer modulo $998\,244\,353$.

Scoring

Subtask 1 (1 point): $k_i = 1$, $l_{i,j} = r_{i,j}$. Subtask 2 (9 points): $n \le 2$. Subtask 3 (29 points): $l_{i,j} = r_{i,j}$. Subtask 4 (15 points): $k_i = 1$, $l_{i,j} = 0$. Subtask 5 (30 points): $k_i = 1$. Subtask 6 (16 points): No additional restrictions.

Examples

Input 1

1
1 3 5

Output 1

3

Input 2

2
1 4 4
1 6 6

Output 2

1

Input 3

3
1 0 10000
1 0 10000
1 0 10000

Output 3

980506341

Input 4

2
2 1 2 3 4
2 5 6 7 8

Output 4

16

Input 5

3
2 4 5 5 6
2 3 8 2 3
3 1 7 2 8 3 6

Output 5

9407

Input 6

file "nim/6"

Output 6

531065315

Input 7

file "nim/7"

Output 7

115919412