对于一个数组 bb，定义：
odd（b）odd（b）：先筛选出 bb 中出现次数为奇数的元素，再将这些元素按照“出现次数降序，出现次数相同时按元素大小升序排序”的新数组。
even（b）even（b）：先筛选出 bb 中出现次数为偶数的元素，再将这些元素按照“出现次数降序，出现次数相同时按元素大小升序排序”的新数组。
比如 b=b=[1, 2, 1]，那么 odd（b）odd（b） = [2]；b=b=[3, 3, 2, 2, 1, 2, 1, 2, 4]，那么 even（b）even（b） = [2, 1, 3]；
现在给你一个长度为 nn 的数组 aa，有 qq 次询问，每次询问给你四个数 L,R,k,VL,R,k,V。你需要回答：你能构造出多少种长度为 kk，值域为 [1,V][1,V]的数组 bb，使得 odd（a[L,R]）=even（b）odd（a[L,R]）=even（b） ？答案对 22 取模。强制在线。
第一行输入一个整数 TT (1≤T≤1051≤T≤105），表示测试的总数。
对于每个测试样例， 第一行输入一个数 nn，表示数组的长度。接下来一行 nn（1≤n≤1051≤n≤105）个数 a1,a2,⋯,ana1,a2,⋯,an（1≤ai≤1091≤ai≤109）。保证样例中 nn 的总和不超过 3×1053×105。
接下来一个数 qq （1≤q≤1051≤q≤105），表示询问的次数。保证样例中 qq 的总和不超过 105105。
接下来 qq 行，每行四个整数 L,R,k,VL,R,k,V（1≤L≤R≤n1≤L≤R≤n， 1≤k,V≤10181≤k,V≤1018），含义如题面所示。强制在线。在第 jj 次询问时，令 preansj=∑i=1j−1ansipreansj=∑i=1j−1ansi。你读入的 L′,R′,k′,V′L′,R′,k′,V′ 需要异或上 preansjpreansj 才是真正的 L,R,k,VL,R,k,V。
1
5
1 2 3 2 5
2
1 4 4 5
1 3 14 70
1
对于第一个查询，我们得到的 odd（a[1,4]）odd（a[1,4]） = [1, 3]。可能的 bb 为：
一共有 66 种情况。因此输出 00。