問題文

長さ $N$ の一次関数の列 $f_0, f_1, \dots, f_{N-1}$ が与えられます。$f_i(x)=a_ix+b_i$ です。
$Q$ 個のクエリが与えられるので、処理してください。
$i$ 番目のクエリでは、整数 $l, r, p, x$ が与えられるので、$f_{(r-1) \oplus p}(f_{(r-2) \oplus p}(\dots f_{(l+1) \oplus p}(f_{l \oplus p}(x)) \dots )) \bmod 998244353$ を出力してください。
ただし、$\oplus$ はビット単位の排他的論理和を表します。

入力

$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}$

入力は以下の制約を満たします。

• 入力はすべて整数
• $N$ は $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)$

出力

$Q$ 行出力してください。 $i$ 行目には $i$ 番目のクエリの答えを出力してください。

サンプル

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