Problem Statement

You are given a sequence of linear functions $f_0, f_1, \dots, f_{N-1}$ of length $N$, where $f_i(x)=a_ix+b_i$.
You are given $Q$ queries; process them.
In the $i$-th query, you are given integers $l, r, p, x$. Output $f_{(r-1) \oplus p}(f_{(r-2) \oplus p}(\dots f_{(l+1) \oplus p}(f_{l \oplus p}(x)) \dots )) \bmod 998244353$.
Here, $\oplus$ denotes the bitwise exclusive OR.

Input

$N\ Q$
$a_0 \ b_0$
$a_1 \ b_1$
$\vdots$
$a_{N-1} \ b_{N-1}$
$l_0 \ r_0 \ p_0 \ x_0$
$l_1 \ r_1 \ p_1 \ x_1$
$\vdots$
$l_{Q-1} \ r_{Q-1} \ p_{Q-1} \ x_{Q-1}$

The input satisfies the following constraints.

• All input values are integers.
• $N$ is a power of $2$.
• $1 \leq N \leq 2^{18} = 262144$
• $1 \leq a_i < 998244353 \ (0 \leq i < N)$
• $0 \leq b_i < 998244353 \ (0 \leq i < N)$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq l_i < r_i \leq N \ (0 \leq i < Q)$
• $0 \leq p_i < N \ (0 \leq i < Q)$
• $0 \leq x_i < 998244353 \ (0 \leq i < Q)$

Output

Output $Q$ lines. On the $i$-th line, output the answer to the $i$-th query.

Sample

4 3
1 1
2 1
1 3
2 0
0 4 0 1
1 3 2 2
2 4 1 5

16
5
13