在“Right Place to Ask”城市信息咨询台工作可不是一件容易的事！作为一名员工，你经常会收到很难立即回答的问题。

Vasya 也不喜欢回答问题。然而，他喜欢让计算机程序来回答。现在，他有一个由 $n$ 个整数组成的数组 $a$：$a_1, a_2, \dots, a_n$，他想写一个程序来响应以下查询：

• 1 i val：将值 val 赋给元素 $a_i$；
• 2 l r：计算数字 $a_l, a_{l+1}, \dots, a_r$ 的 Vasya 和。

Vasya 并不认为所有数字都一样好。他更喜欢靠右的数字，而且是恰好两倍的喜欢！因此，他将数字 $x_1, x_2, \dots, x_k$ 的 Vasya 和定义为以下值：

$$\sum_{i=1}^{k} 2^{i-1} \cdot x_i = x_1 + 2x_2 + 4x_3 + \dots + 2^{k-1}x_k$$

即使 Vasya 写不出这样的程序，也没关系：除了在“Right Place to Ask”，还有哪里能帮他计算出偏向右侧数字的结果呢？所以，现在解决这个问题的重担落在了你的肩上！为了简化计算，你只需要确定每个 Vasya 和是正数、负数还是零。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 5 \cdot 10^5$)，表示测试用例的数量。接下来的 $t$ 个测试用例描述格式如下。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 5 \cdot 10^5$)，分别表示 Vasya 数组中的整数个数和查询次数。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示 Vasya 数组中从左到右的元素。

接下来的 $q$ 行中，每行描述一个查询，格式为 1 i val 或 2 L R ($1 \le i \le n$, $-10^9 \le val \le 10^9$, $1 \le L \le R \le n$)。第一种类型的查询表示需要将元素 $a_i$ 的值修改为 val。第二种类型的查询表示你需要求出数字 $a_L, a_{L+1}, \dots, a_R$（当然，严格按此顺序）的 Vasya 和的符号。查询中的所有数字均为整数。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $5 \cdot 10^5$，且每个测试用例中至少包含一个第二种类型的查询。

输出格式

对于每个测试用例，针对每个第二种类型的查询输出一个整数。如果给定查询中的 Vasya 和为正数，输出 1；如果为负数，输出 -1；否则输出 0。

样例

输入样例 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

1
0
-1
0
-1
-1

说明

在第一个测试用例中，Vasya 和分别为 $1, 0, -4, 0, -2$。

在第二个测试用例中，Vasya 和为 $-30$。

请注意，在本题中，输入和输出数据可能非常大。建议使用您所使用的编程语言中可用的输入输出加速方法。