Or

Problem Description

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},\cdots,a_{l+1}+b_{l+2},a_{l+1}+b_{l+2}+b_{l+3},\cdots,a_{r}$. In other words, you need to evaluate $\bigoplus_{i=l}^{r}\bigoplus_{j=i}^r(a_i+\sum_{k=i+1}^{j}b_k)$. The symbol $\oplus$ represents the bitwise OR operation.

Input

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\le n \le 10^5,1\le m\le 10^6)$. The second line contains $n$ integers $a_i(0\le a_i \le 5\times 10^8)$. The third line contains $n$ integers $b_i(0\le b_i\le 5000)$. The next $m$ lines, each line contains two integers $l,r(1\le l \le r \le n)$. It is guaranteed that in all test cases, $\sum n\le 10^5,\sum m\le 10^6$.

Output

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 $(\sum_{i=1}^m ans_i\times base^{i})\bmod P$.

Sample Input

1
5 1
1 2 3 4 5
1 1 1 1 1
2 4

Sample Output

1631

Hint

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$

Source

2023“钉耙编程”中国大学生算法设计超级联赛（2）