問題文

長さ $N$ の一次関数の列 $f_0,f_1,\dots ,f_{N-1}$ が与えられます。$f_i(x)=a_{i}x+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 ))mod998244353$ を出力してください。
ただし、$\oplus$ はビット単位の排他的論理和を表します。

入力

$NQ$
$a_0{b}_0$
$a_1{b}_1$
$⋮$
$a_{N-1}{b}_{N-1}$
$l_0{r}_0{p}_0{x}_0$
$l_1{r}_1{p}_1{x}_1$
$⋮$
$l_{Q-1}{r}_{Q-1}{p}_{Q-1}{x}_{Q-1}$

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

• 入力はすべて整数
• $N$ は $2$ べきである
• $1\le N\le 2^{18}=262144$
• $1\le a_i<998244353(0\le i<N)$
• $0\le b_i<998244353(0\le i<N)$
• $1\le Q\le 2\times {10}^5$
• $0\le l_i<r_i\le N(0\le i<Q)$
• $0\le p_i<N(0\le i<Q)$
• $0\le x_i<998244353(0\le 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