DDOSvoid is learning about bitwise operations and has come across an interesting problem.
You are given two sequences, $a_i$ and $b_i$, both of length $n$. Additionally, there are $m$ queries. In each query, you are given an interval $[l,r]$. Your task is to calculate the bitwise $OR$ operation on the following integers:$a_l,a_l+b_{l+1},a_l+b_{l+1}+b_{l+2},⋯,a_{l+1}+b_{l+2},a_{l+1}+b_{l+2}+b_{l+3},⋯,a_r$. In other words, you need to evaluate $⨁_{i=l}^r⨁_{j=i}^r(a_i+\sum_{k=i+1}^jb_k)$. The symbol $⊕$ represents the bitwise $OR$ operation.
The first line of the input contains a single integer $T$, indicating the number of test cases.
In each test case:
The first line contains to integers $n,m(1≤n≤10^5,1≤m≤10^6)$.
The second line contains $n$ integers $a_i(0≤a_i≤5×10^8)$.
The third line contains $n$ integers $b_i(0≤b_i≤5000)$.
The next $m$ lines, each line contains two integers $l,r(1≤l≤r≤n)$.
It is guaranteed that in all test cases, $∑n≤10^5,∑m≤10^6$.
To simply the output, we use $ans_i$ to represent the answer to the $i$-th query and $base=233,P=998244353$.
In each test case you just need to output an integer $(∑_{i=1}^mans_i×base^i)\ mod\ P$.
1 5 1 1 2 3 4 5 1 1 1 1 1 2 4\n · \n · · · · \n · · · · \n · \n
1631\n
For query $[2,4]$, you need to calculate the bitwise $OR$ operation on the following integers, $a_2,a_2+b_3,a_2+b_3+b_4,a_3,a_3+b_4,a_4$