对于一个数组 $b$，定义：
$odd（b）$：先筛选出 $b$ 中出现次数为奇数的元素，再将这些元素按照“出现次数降序，出现次数相同时按元素大小升序排序”的新数组。
$even（b）$：先筛选出 $b$ 中出现次数为偶数的元素，再将这些元素按照“出现次数降序，出现次数相同时按元素大小升序排序”的新数组。
比如 $b=$[1, 2, 1]，那么 $odd（b）$ = [2]；$b=$[3, 3, 2, 2, 1, 2, 1, 2, 4]，那么 $even（b）$ = [2, 1, 3]；
现在给你一个长度为 $n$ 的数组 $a$，有 $q$ 次询问，每次询问给你四个数 $L, R, k, V$。你需要回答：你能构造出多少种长度为 $k$，值域为 $[1, V]$的数组 $b$，使得 $odd（a[L, R]） = even（b）$ ？答案对 $2$ 取模。强制在线。
第一行输入一个整数 $T$ ($1 \le T \le 10^5$），表示测试的总数。
对于每个测试样例， 第一行输入一个数 $n$，表示数组的长度。接下来一行 $n$（$1 \leq n \leq 10^5$）个数 $a_1, a_2, \cdots, a_n$（$1 \leq a_i \leq 10^9$）。保证样例中 $n$ 的总和不超过 $3 \times 10^5$。
接下来一个数 $q$ （$1 \leq q \leq 10^5$），表示询问的次数。保证样例中 $q$ 的总和不超过 $10^5$。
接下来 $q$ 行，每行四个整数 $L, R, k, V$（$1 \leq L \leq R \leq n$， $1 \leq k, V \leq 10^{18}$），含义如题面所示。强制在线。在第 $j$ 次询问时，令 $preans_j = \sum_{i = 1}^{j - 1}ans_i$。你读入的 $L', R', k', V'$ 需要异或上 $preans_j$ 才是真正的 $L, R, k, V$。
对于每个样例，每次询问输出一个值，方案数对 $2$ 取模后的结果。
1 5 1 2 3 2 5 2 1 4 4 5 1 3 14 7\n \n · · · · \n \n · · · \n · · · \n
0 1\n \n
对于第一个查询，我们得到的 $odd（a[1, 4]）$ = [1, 3]。可能的 $b$ 为：
[1, 1, 3, 3][1, 3, 1, 3][1, 3, 3, 1][3, 1, 1, 3][3, 1, 3, 1][3, 3, 1, 1]一共有 $6$ 种情况。因此输出 $0$。