We call an array of integers $d_1, d_2, \ldots, d_m$ good if its length is equal to $0$, or for any $1\le i\le m$, both values $\sum\limits_{j=1}^{i} d_j$ and $\sum\limits_{j=i}^{m} d_j$ are non-negative. Here, $\sum\limits_{j=l}^{r} d_j$ denotes $d_l+d_{l+1}+\ldots+d_{r}$.

We define the beauty of the array as the length of its longest good subsequence$^1$.

You are given an array $a$ of length $n$, which consists of numbers $-1$ and $1$.

You need to perform $q$ queries. The queries are of two types:

1. replace the element $a_p$ with $-a_p$, where $p$~--- the parameter of the query;
2. find the beauty of the array consisting of elements $[a_{l},a_{l+1},\ldots,a_r]$, where $(l, r)$~--- the parameters of the query.

Input

In the first line, two integers $n$, $q$ are given $(1\le n, q\le 5 \cdot 10^5)$~--- the length of the array $a$ and the number of queries, respectively.

In the second line, $n$ integers $a_1, a_2, \ldots, a_n$ $(a_i \in \{-1, 1\})$ are given~--- the elements of the array $a$.

In the next $q$ lines, the description of the queries is given. The first of the numbers $type_i$ $(1 \le type_i \le 2)$ denotes the type of the query. Queries of the first type are given in the format 1 p $(1 \le p \le n)$, and queries of the second type are given in the format 2 l r $(1 \le l \le r \le n)$.

Output

For each query of the second type, output one integer in a separate line~--- the beauty of the corresponding array.

Note

$^1$ An array $c$ is called a subsequence of an array $b$ if it is possible to remove a certain number of elements from the array $b$ (possibly zero) so that the array $c$ is formed. The empty array is a subsequence of any array.

Example

Input

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

Output

5
2
3

Input

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

Output

2
2
1
1

Scoring

1. ($2$ points): $a_i = (-1)^{i+1}$ for $1 \le i \le n$, and there are no type one queries;
2. ($7$ points): $n \le 16$, and there are no type one queries;
3. ($21$ points): $n, q \le 100$;
4. ($20$ points): $n, q \le 3000$;
5. ($27$ points): $n, q \leq 2 \cdot 10^5$, and there are no type one queries;
6. ($14$ points): $n, q \leq 2 \cdot 10^5$;
7. ($9$ points): no additional restrictions.