题目描述

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

给定两个序列，$a_{i}$ 和 $b_{i}$，长度均为 $n$。此外，还有 $m$ 个查询。在每个查询中，你会得到一个区间 $[l,r]$。你的任务是计算以下整数的按位或（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 \leq n \leq 10^{5}, 1 \leq m \leq 10^{6})$。

第二行包含 $n$ 个整数 $a_i$ $(0 \leq a_i \leq 5 \times 10^{8})$。

第三行包含 $n$ 个整数 $b_i$ $(0 \leq b_i \leq 5000)$。

接下来的 $m$ 行，每行包含两个整数 $l, r$ $(1 \leq l \leq r \leq n)$。

保证所有测试用例中，$\sum n \leq 10^{5}$，$\sum m \leq 10^{6}$。

输出格式

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

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

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

1631

解释 #1

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