Piggy has recently been studying string theory and has now encountered the following problem:
Maintain a dynamic string $s[1..n]$, where the character set of the string consists of all integers $x$ such that $|x| \le 10^9$. Support the following two operations:
1) Given $l, r, d$, for all $l \le i \le r$, update $s[i]$ to $s[i] + d$. Note that $d$ may be negative.
2) Given $l, r$, output the starting position of the lexicographically smallest suffix of the substring $s[l..r]$. That is, if the smallest suffix is $s[p..r]$ (where $l \le p \le r$), output $p$.
Input
The first line contains two non-negative integers $n$ and $q$.
The next line contains $n$ positive integers, representing the initial string.
The next $q$ lines each contain either $1\ l\ r\ d$ or $2\ l\ r$, representing the two types of operations respectively.
Output
For all query operations, output the answers in order.
Constraints
| Test Case ID | $n$ | $q$ | Other Constraints |
|---|---|---|---|
| 1 | $\le 300$ | $\le 300$ | None |
| 2 | $\le 2 \times 10^4$ | $\le 10^4$ | None |
| 3 | |||
| 4 | Only type 2 operations | ||
| 5 | $\le 2 \times 10^5$ | $\le 3 \times 10^4$ | |
| 6 | Data randomly generated | ||
| 7 | |||
| 8 | None | ||
| 9 | |||
| 10 |
For 100% of the data, $1 \le l \le r \le n$, $|d| \le 10^3$, and $|s_i| \le 10^8$.
Note: For test cases 6 and 7, the data is randomly generated where $s_i$ is chosen randomly from $[0, 1]$, $d$ is chosen randomly from $\pm 1$, and the operation type and operation interval are chosen with equal probability.
Examples
Input 1
5 5 3 2 1 4 3 2 1 5 1 2 4 2 2 1 5 1 2 5 1 2 1 5
Output 1
3 5 1