mod 2

Problem Description

对于一个数组 $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$ 取模。强制在线。

Input

第一行输入一个整数 $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$。

Output

对于每个样例，每次询问输出一个值，方案数对 $2$ 取模后的结果。

Sample Input

1
5
1 2 3 2 5
2
1 4 4 5
1 3 14 7

Sample Output

0
1

Hint

对于第一个查询，我们得到的 $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$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（1）