Allowance
By Ricardo Oliveira, UFPR 
Brazil
By Ricardo Oliveira, UFPR Brazil
It is getting harder to mrs. Marie to manage the allowance she gives to her grandchildren. Because of that, she asked you to write a program to help her with this task.
Mrs. Marie has N grandchildren, numbered from 1 to N. Initially, grandchild i earns Mi dollars as allowance from his grandma. Mrs. Marie may increase the allowance given to some of his grandchildren many times. When she wants to increase the allowance, she chooses two integers i and j and increases the allowance of all her grandchildren with numbers between i and j, inclusive, by the same amount v. For example, if she decides to increase the allowance by v=10 dollars for all grandchildren with numbers between i=1 and j=3, then the allowance of the grandchildren numbered 1, 2 and 3 will be increased by 10 dollars each.
Also, at any time, she may want to ask who earns the most among the grandchildren between numbers i and j, inclusive. Help mrs. Marie to answer all her queries!
The input contains several test cases. The first line of each test case contains two integers N and Q (1 ≤ N ≤ 105, 1 ≤ Q ≤ 106), the number of grandchildren and the number of operations, respectively. Next line contains N integers M1,M2,...,MN (1 ≤ Mi ≤ 200), the initial allowance of each grandchild. Next Q lines describe an operation each. An operation in the form A i j v (1 ≤ i ≤ j ≤ N, 1 ≤ v ≤ 200) indicates an allowance increase. An operation in the form C i j (1 ≤ i ≤ j ≤ N) indicates a query.
The input ends with end-of-file (EOF).
For each test case, print, for each query, a line containing the number of the grandchild who earns the most among the grandchildren between numbers i and j, inclusive. If there is more than one grandchild earning the most among them, print the one with the smallest number.
| Input Sample | Output Sample |
|
5 6 |
2 |