A student is always bored during his math classes. As the teacher won't let him sleep, he finds something else to do: try to find patterns in the numbers written on the board! Currently, he's spending his time trying to find Hi&Lo subsequences.

Intuitively, a Hi&Lo sequence is any sequence that has consecutive differences with opposite signs, that is, if the first number is greater than the second, then the second is smaller than the third, the third is greater than the fourth, and so on.

Formally, let x[1], x[2], ..., x[n] be the numbers written on the board. A Hi&Lo subsequence of length k that only uses elements from A to B is a sequence of indices a₁, a₂, ..., a_k such that:

1. B ≥ a_k > ... > a₂ > a_{1 ≥} A
2. x[a_i]- x[a_i-1] != 0, for 1 < i <= k
3. ( x[a_i] - x[a_i-1] )( x[a_i+1] - x[a_i] ) < 0, for 1 < i < k 

Note that every sequence with only one element is a Hi&Lo sequence.

However, as the amount of numbers increases, finding a big subsequence is getting harder and harder, so he asked you to create a program to help him and quickly find the largest Hi&Lo subsequence in a given interval. 

Input

The input contains several test cases. A test case begins with a line containing integers N (1 ≤ N ≤ 100000)  and M (1 ≤ M ≤ 10000), separated by spaces. On the second line there are N positive integers, the initial state of the board. M lines follow, each with an instruction. Instructions can be of two kinds:

1) q A B: Print the length of the longest high & low subsequence only using elements in positions from A to B, inclusive. You may assume that 1 ≤ A ≤ B ≤ N. 

2) m A B: Modify the Ath element of the sequence to the positive integer B. You may assume that 1 ≤ A ≤ N. 

No number on the board will ever exceed 10⁹. There is a blank line after each test case. The last test case is followed by a line containing two zeros.

Output

For each instruction of type 1, print a line containing an integer, the answer to the query. After each test, print a blank line. 

Example

Input:
5 7
5 7
1 2 3 4 5
q 2 4
m 3 1
q 2 4
m 3 2
q 2 4
m 4 2
q 2 4

0 0

Output:
2
3
2
1