#P18018. May We Answer Your Questions Right?

May We Answer Your Questions Right?

May We Answer Your Questions Right?

给定一个长度为 nn 的整数数组 a1,…,ana_1,\ldots,a_n,需要处理 qq 次操作:

  • 1 i val:将 aia_i 修改为 valval;
  • 2 L R:判断 aL+2aL+1+4aL+2+⋯+2R−LaRa_L+2a_{L+1}+4a_{L+2}+\cdots+2^{R-L}a_R 的正负性。

更一般地,Vasya 将序列 x1,…,xkx_1,\ldots,x_k 的“和”定义为 ∑i=1k2i−1xi\sum_{i=1}^k2^{i-1}x_i,越靠右的元素权重越大。你只需要输出这个和为正、为负还是为零,不需要输出其具体值。

输入格式

第一行一个整数 tt,表示测试用例数。

每个测试用例第一行两个整数 n,qn,q,第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。接下来 qq 行,每行按上述格式描述一个操作。

输出格式

对每个类型为 2 的操作,依次输出一行:和为正输出 1,为负输出 -1,为零输出 0。

数据范围

1≤t≤5×1051\le t\le5\times10^5,1≤n,q≤5×1051\le n,q\le5\times10^5,−109≤ai,val≤109-10^9\le a_i,val\le10^9,1≤i≤n1\le i\le n,1≤L≤R≤n1\le L\le R\le n。

单个输入文件中,所有测试用例的 nn 之和、qq 之和分别不超过 5×1055\times10^5。每个测试用例至少包含一个类型为 2 的操作。

样例 1

输入

2
4 7
9 -4 2 -1
2 1 4
2 2 3
2 2 4
1 1 8
2 1 4
1 2 -5
2 1 4
7 1
2026 2 5 -14 59 59 -75
2 1 7

输出

1
0
-1
0
-1
-1