网络工程专业代表计算机学院ACM集训队欢迎小23们来参加集训队选拔赛，这是一道签到题。

小S上中学啦！在一次数学课上老师提问了他一个问题，具体问题如下：

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

小S想这不是我小学学过的异或运算嘛，轻轻松松回答了这个问题，你知道他是如何解出的吗？

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

接下来一行输入n个整数 a1, a2, a3, ... , an (0≤a_i≤10¹⁰)

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