我们称一个整数数组 $d_1, d_2, \ldots, d_m$ 为 good，当且仅当它的长度等于 $0$，或者对于任意的 $1\le i\le m$，两个值 $\sum\limits_{j=1}^{i} d_j$ 和 $\sum\limits_{j=i}^{m} d_j$ 都是非负的。这里，$\sum\limits_{j=l}^{r} d_j$ 表示 $d_l+d_{l+1}+\ldots+d_{r}$。

我们定义数组的 beauty 为其最长 good 子序列的长度$^1$。

给定一个长度为 $n$ 的数组 $a$，其元素 仅由 $-1$ 和 $1$ 组成。

你需要处理 $q$ 个查询。查询有两种类型：

1. 将元素 $a_p$ 替换为 $-a_p$，其中 $p$ 是查询的参数；
2. 查询由元素 $[a_{l},a_{l+1},\ldots,a_r]$ 组成的数组的 beauty，其中 $(l, r)$ 是查询的参数。

输入

第一行，给出两个整数 $n$, $q$ $(1\le n, q\le 5 \cdot 10^5)$，分别表示数组 $a$ 的长度和查询的数量。

第二行，给出 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(a_i \in \{-1, 1\})$，表示数组 $a$ 的元素。

接下来的 $q$ 行中，每行描述一个查询。第一个数字 $type_i$ $(1 \le type_i \le 2)$ 表示查询的类型。第一种类型的查询格式为 1 p $(1 \le p \le n)$，第二种类型的查询格式为 2 l r $(1 \le l \le r \le n)$。

输出

对于每一个第二种类型的查询，输出一个整数，表示对应数组的 beauty，每个答案占一行。

注释

$^1$ 如果数组 $c$ 可以通过从数组 $b$ 中删除若干（可能为零）个元素后得到，那么称 $c$ 为 $b$ 的一个子序列。空数组是任何数组的子序列。

示例

输入

5 4
1 1 1 -1 1
2 1 5
1 3
2 1 4
2 2 5

输出

5
2
3

输入

4 4
1 1 1 -1
2 1 2
2 2 4
2 3 3
2 3 4

输出

2
2
1
1

评分

1. （$2$ 分）：$a_i = (-1)^{i+1}$，对于所有 $1 \le i \le n$，并且没有第一种类型的查询；
2. （$7$ 分）：$n \le 16$，并且没有第一种类型的查询；
3. （$21$ 分）：$n, q \le 100$；
4. （$20$ 分）：$n, q \le 3000$；
5. （$27$ 分）：$n, q \leq 2 \cdot 10^5$，并且没有第一种类型的查询；
6. （$14$ 分）：$n, q \leq 2 \cdot 10^5$；
7. （$9$ 分）：无额外限制。