Conway's Game of Life is a zero-player game—it consists of a two-dimensional rectangular world where each cell is either alive or dead, and the life or death of a cell in the next time step depends on the number of living or dead cells in the four adjacent squares. — Wikipedia

Today we will study the XOR Game of Life. Specifically, for any cell, the cell is alive at the next time step if and only if the number of living cells in its four adjacent squares is odd.

Given $n$ initially living cells (at time $0$), can you calculate the sum of the number of living cells from time $L$ to time $R$?

Input

The first line contains four integers $n, L, R, type$. The meanings of $n, L, R$ are as described above. The $type$ parameter provides a hint about the data type, which can help you obtain partial points; the meaning of this parameter is described in detail in the [Constraints] section.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th living cell.

Output

Output a single integer representing the sum of the number of living cells from time $L$ to time $R$. The answer should be taken modulo $998244353$.

Examples

Input 1

3 0 3 2
0 -1
0 0
2 2

Output 1

55

Input 2

2 0 89 2
-15 -44
47 -34

Output 2

37830

Input 3

8 19260817 20210131 2
9 1
-1 -9
0 10
0 4
5 -3
-7 1
1 5
4 2

Output 3

767830283

Note

For Example 1, the cell states at the 4 time steps are:

Constraints

The meanings of the data type $type$ are:

• $type = 0$: Guarantees that for all initially living cells, the parity of $x + y$ is distinct for each.
• $type = 1$: Guarantees $L = R$, i.e., only querying the number of living cells at time $L(R)$.
• $type = 2$: No special constraints on the data.