DDOSvoid 正在学习位运算，并遇到了一个有趣的问题。

给定两个长度为 $n$ 的序列 $a_i$ 和 $b_i$。此外，还有 $m$ 次查询。在每次查询中，给定一个区间 $[l, r]$。你的任务是计算以下整数的按位或（bitwise OR）运算结果：$a_l, a_l + b_{l+1}, a_l + b_{l+1} + b_{l+2}, \dots, a_{l+1} + b_{l+2}, a_{l+1} + b_{l+2} + b_{l+3}, \dots, a_r$。换句话说，你需要计算 $\bigoplus_{i=l}^{r} \bigoplus_{j=i}^{r} (a_i + \sum_{k=i+1}^{j} b_k)$。符号 $\oplus$ 表示按位或运算。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例中： 第一行包含两个整数 $n, m$ ($1 \le n \le 10^5, 1 \le m \le 10^6$)。 第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 5 \times 10^8$)。 第三行包含 $n$ 个整数 $b_i$ ($0 \le b_i \le 5000$)。 接下来的 $m$ 行，每行包含两个整数 $l, r$ ($1 \le l \le r \le n$)。

保证在所有测试用例中，$\sum n \le 10^5, \sum m \le 10^6$。

输出格式

为了简化输出，我们用 $ans_i$ 表示第 $i$ 次查询的答案，并设 $base = 233, P = 998244353$。

在每个测试用例中，你只需要输出一个整数 $(\sum_{i=1}^{m} ans_i \times base^i) \pmod P$。

样例

输入样例 1

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

输出样例 1

1631

说明

对于查询 $[2, 4]$，你需要计算以下整数的按位或运算结果：$a_2, a_2 + b_3, a_2 + b_3 + b_4, a_3, a_3 + b_4, a_4$。