AT_past202209_o ２個のボール

There are two boxes $ A $ and $ B $ that contain balls with integers between $ 0 $ and $ 2^N-1 $ written on them. Box $ A $ contains $ A_i $ balls with the integer $ i $ $ (0 \leq i \lt 2^N) $ , and Box $ B $ contains $ B_i $ balls with the integer $ i $ $ (0 \leq i \lt 2^N) $ . All balls are distinguishable. Consider picking up one ball from each of Box $ A $ and Box $ B $ . Among the (number of balls in Box $ A $ ) $ \times $ (number of balls in Box $ B $ ) ways to do so, let $ f(x, y) $ be the number of ones that satisfy the following condition. - Here we denote by $ \mathrm{popcount}(x) $ the number of $ 1 $ s in the binary notation of $ x $ . Let $ a $ and $ b $ be the integers written on the balls from $ A $ and $ B $ , respectively. Then, the bitwise OR of $ a $ and $ b $ is $ x $ , and $ \mathrm{popcount}(a) + \mathrm{popcount}(b) $ is $ y $ . You are given sequences $ X $ and $ Y $ of length $ Q $ each. Compute $ f(X_i, Y_i) $ modulo $ 998244353 $ for every $ i $ $ (1 \leq i \leq Q) $ .

Input is given from Standard Input in the following format: > $ 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 $

Print $ Q $ lines. The $ i $ -th line should contain $ f(X_i,Y_i) \bmod{998244353} $ .

### Sample Explanation 1 - For $ x = 1 $ and $ y = 1 $ , the corresponding pairs $ (a, b) $ are $ (a,b) = (0, 1), (1, 0) $ . Thus, the sought number is $ A_0 \times B_1 + A_1 \times B_0 = 32 $ . - For $ x = 3 $ and $ y = 2 $ , the corresponding pairs $ (a, b) $ are $ (a,b) = (0,3),(1,2),(2,1),(0,3) $ . Thus, the sought number is $ A_0 \times B_3 + A_1 \times B_2 + A_2 \times B_1 + A_3 \times B_0 = 61 $ . - For $ x = 2 $ and $ y = 0 $ , there are no corresponding pairs $ (a, b) $ . Thus, the sought number is $ 0 $ . ### Sample Explanation 2 One or more of the boxes may be empty. ### 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) $ - All values in input are integers.