AT_past202209_o ２個のボール

$ 0 $ 以上 $ 2^N $ 未満の数が書かれたボールが入った箱 $ A $ と箱 $ B $ があります。箱 $ A $ には $ i $ $ (0 \leq i \lt 2^N) $ が書かれたボールが $ A_i $ 個、箱 $ B $ には $ i $ $ (0 \leq i \lt 2^N) $ が書かれたボールが $ B_i $ 個入っています。すべてのボールは区別できます。 箱 $ A $ と箱 $ B $ からボールを $ 1 $ 個ずつ取り出すことを考えます。取り出し方は (箱 $ A $ に入っているボールの個数) $ \times $ (箱 $ B $ に入っているボールの個数) 通りありますが、そのうち次の条件を満たす取り出し方の数を $ f(x, y) $ とおきます。 - $ \mathrm{popcount}(x) $ を $ x $ を $ 2 $ 進表記にしたときに出現する $ 1 $ の個数として定義する。 $ A $ から取り出したボールに書かれた数を $ a $ 、 $ B $ から取り出したボールに書かれた数を $ b $ とする。このとき、 $ a $ と $ b $ のビットごとの論理和が $ x $ で、 $ \mathrm{popcount}(a) + \mathrm{popcount}(b) $ が $ y $ になっている。 長さ $ Q $ の数列 $ X,Y $ が与えられるので、すべての $ i $ $ (1 \leq i \leq Q) $ に対して $ f(X_i, Y_i) $ を $ 998244353 $ で割ったあまりを計算してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_0 $ $ A_1 $ $ \dots $ $ A_{2^N-1} $ $ B_0 $ $ B_1 $ $ \dots $ $ B_{2^N-1} $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ f(X_i,Y_i) \bmod{998244353} $ を出力せよ。

### Sample Explanation 1 - $ x = 1, y = 1 $ となる $ (a,b) $ の組み合わせは $ (a,b) = (0, 1), (1, 0) $ です。よって答えは $ A_0 \times B_1 + A_1 \times B_0 = 32 $ となります。 - $ x = 3, y = 2 $ となる $ (a,b) $ の組み合わせは $ (a,b) = (0,3),(1,2),(2,1),(0,3) $ です。よって答えは $ A_0 \times B_3 + A_1 \times B_2 + A_2 \times B_1 + A_3 \times B_0 = 61 $ となります。 - $ x = 2, y = 0 $ となる $ (a,b) $ の組み合わせは存在しません。よって答えは $ 0 $ となります。 ### Sample Explanation 2 少なくとも片方の箱が空である場合もあります。 ### Constraints - $ 1 \leq N \leq 17 $ - $ 1 \leq Q \leq 10^5 $ - $ 0 \leq A_i \lt 998244353 $ $ (0 \leq i \lt 2^N) $ - $ 0 \leq B_i \lt 998244353 $ $ (0 \leq i \lt 2^N) $ - $ 0 \leq X_i \lt 2^N $ $ (1 \leq i \leq Q) $ - $ 0 \leq Y_i \leq 2N $ $ (1 \leq i \leq Q) $ - 入力はすべて整数である。