In an array of integers v_1, v_2, \dots, v_n, an interval [a, b] is called lucky if none of the prefix sums v_a, v_a + v_{a + 1}, \dots, v_a + v_{a + 1} + \dots + v_b is negative. Your task is to deal with q queries of two types that either

1. replace the value of v_i by x; or
2. output whether the interval [a, b] is lucky.

Input

The first line of the input contains two integers n and q.

The second line of the input contains the initial n values of the array.

The following q lines describe the queries that are encoded as 1 i x for the queries of the first type and 2 a b for the queries of the second type.

Output

For each query of the second type, output "YES" if the interval is lucky and otherwise "NO".

Constraints

• 1 \le n, q \le 2 \cdot 10^5
• All values are integers between -10^9 and 10^9.

Examples

Input:

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

Output:

YES
NO
NO