D2. 无限序列（困难版本）

每个测试的时间限制：$2$ 秒
每个测试的内存限制：$256$ MB

这是该问题的困难版本。与简单版本的区别在于，在此版本中 $l \le r$。只有解决了所有版本的题目，你才能进行 Hack。

给定一个正整数 $n$ 以及一个无限二进制序列 $a$ 的前 $n$ 项。该序列定义如下：

对于 $m > n$，

$$a_m = a_1 \oplus a_2 \oplus \dots \oplus a_{\lfloor \frac{m}{2} \rfloor} $$

其中 $\oplus$ 表示按位异或运算。

你的任务是计算给定区间 $[l, r]$ 内元素的和：

$$a_l + a_{l+1} + \dots + a_r$$

---

输入格式

每个测试包含多个测试用例。
第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。

每个测试用例的描述如下：

• 第一行包含三个整数 $n, l, r$（$1 \le n \le 2 \times 10^5$，$1 \le l \le r \le 10^{18}$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$a_i \in \{0,1\}$）—— 序列 $a$ 的前 $n$ 项。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

---

输出格式

对于每个测试用例，输出一个整数 —— 给定区间内元素的和。

---

示例

输入

9
1 1 1
1
2 3 10
1 0
3 5 25
1 1 1
1 234 567
0
5 1111 10000000000
1 0 1 0 1
1 1000000000000000000 1000000000000000000
1
10 41 87
0 1 1 1 1 1 1 1 0 0
12 65 69
1 0 0 0 0 1 0 1 0 1 1 0
13 46 54
0 1 0 1 1 1 1 1 1 0 1 1 1

输出

1
5
14
0
6666665925
0
32
3
2

---

说明

• 在第一个测试用例中，序列 $a$ 为
  $[\underline{1},1,1,0,0,1,1,1,1,1,\dots]$，$l=1$，$r=1$。
  区间 $[1,1]$ 的元素和为 $a_1 = 1$。

• 在第二个测试用例中，序列 $a$ 为
  $[1,0,1,1,1,0,0,1,1,0,\dots]$，$l=3$，$r=10$。
  区间 $[3,10]$ 的元素和为
  $a_3 + a_4 + \dots + a_{10} = 1 + 1 + 1 + 0 + 0 + 1 + 1 + 0 = 5$。