【 Sample Input 】

5 5
0 0 0 0 0
5 4 1 2 3
1001
10
1
4
2 1 0 0
1 2 1 0
0 2 3 1
2 2 0 1

【 Sample Output 】

5
19
7
1

【HINT】

【样例1解释】

共有T=4组数据，这里只解释第一组。5名选手的真实能力值为[1,0,0,2,1]。5组询问分别是对长度为5,4,1,2,3的前缀进行的。

1. 对于长度为1的前缀，由于只有1号一个人，因此答案为1。

2. 对于长度为2的前缀，由于2个人已经是2的幂次，因此不需要进行扩充。根据抽签d1,1 = 1 可知 2 号为擂主，由于a2<1，因此1号获胜，答案为1。

3. 对于长度为3的前缀，首先1号、2号比赛是1号获胜（因为d1,1=1，故2号为擂主，a2 <1），然后虽然4号能力值还不知道，但3号、4号比赛一定是4号

获胜（因为d1,2 =0，故 3 号为擂主，a3<1），而决赛1号、4号谁获胜都有可能（因为d2,1 = 1，故 4 号为擂主，如果a4 <2则1号获胜，a4≥2则4号获胜）。综上所述，答案为1+4=5。

4. 对于长度为4 的前缀，我们根据上一条的分析得知，由于a4≥2 ，所以决赛获胜的是4 号。

5. 对于长度为5的前缀，可以证明，可能获胜的选手包括4号、7号、8号，答案为19。

因此，该组测试数据的答案为(1×19)⊕(2×4)⊕(3×1)⊕(4×1)⊕(5×5)=5。

【数据范围】

对于所有测试数据，保证：2≤n,m≤10^5，0≤ai,Xj <2^31，1≤ci ≤n，1≤T ≤256。

【 Source/Category 】