Given an array A of n elements, there are q queries, each falling into one of two types:
- 1ix: Assign the value x to Ai.
- 2lrx: Count the number of pairs (i,j) such that l≤i≤j≤r and the maximum value in the subarray Ai...j does not exceed x.
Answer the queries of type 2.
### Input
- The first line contains two integers n,q.
- The second line contains n integers Ai.
- The next q lines each contain a query in the specified format.
### Output
- Print an integer as the answer for each query of type 2.
### Constraints
- 1≤n,q≤105.
- 1≤Ai,x≤109.
- 1≤l≤r≤n.
### Example
Input:
661145141142142211421541542333
Output:
1170
