本题目与 Easy Version 的区别仅为 n, q, a_i 的数据范围不同

小 C 天天上课睡觉，不喜欢学习，热心的你不忍心让小 C 这样堕落下去，侬老师上课给小 C 留下了一个问题。但小 C 实在是看不懂，准备摆烂了，你能教教他吗？

具体问题如下：

给你一个长度为 n 的数组 a，数组下标从 1 开始，你需要回答 q 次询问，每次询问会给你两个整数 l, r，你的任务是求出 a_l ~ a_r 的区间和 (a_l + a_l+1 + ... + a_r) 和区间异或和 (a_l ⊕ a_l+1 ⊕ ... ⊕ a_r)，并输出两个值异或起来的值。

提示：

⊕ 是异或符号，在 C / C++ 中，求 a 与 b 的异或值的方法是 a ^ b。

异或运算规则如下：

0 ⊕ 0 = 0

0 ⊕ 1 = 1

1 ⊕ 0 = 1

1 ⊕ 1 = 0

两个整数进行异或运算，指的是它们转成二进制后（位数不同的在前面补 0），每一位相互异或的结果再转成十进制，如二进制下 (01)₂ ⊕ (10)₂ = (11)₂， 即 1 ⊕ 2 = 3。

异或是一种重要的运算，它具有如下性质：

归零性：a ⊕ a = 0；

交换律：a ⊕ b = b ⊕ a；

结合律：(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)；

特别的，对于任意一个整数 a，a ⊕ 0 = a。

第一行输入 2 个整数 n, q (1 ≤ n ≤ 10⁶, 1 ≤ q ≤ 10⁶)

接下来一行输入 n 个整数 a₁, a₂, a₃, ... , a_n (0 ≤ a_i ≤ 10¹⁰)

接下来有 q 行，每行读入两个整数 l, r (1 ≤ l ≤ r ≤ n)