Background

Pig Xiaoxia has recently been studying string-related theory, and now he has encountered the following problem.

Problem Description

Maintain a dynamic string $s_{1..n}$, whose alphabet is all integers with $|x| \leq 10 ^ 9$. You need to support two operations:

1. Input $l, r, d$. For all $l \leq i \leq r$, modify $s_i$ to $s_i + d$. Note that $d$ may be negative.

2. Input $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}$ ($l \leq p \leq r$), output $p$.

Input Format

The first line contains two non-negative integers $n, q$.

The next line contains $n$ positive integers, representing the initial string.

The next $q$ lines each describe an operation in the form $1\ l\ r\ d$ or $2\ l\ r$, corresponding to the two operations above.

Output Format

For each query operation, output the answer in order.

5 5
3 2 1 4 3
2 1 5
1 2 4 2
2 1 5
1 2 5 1
2 1 5

3
5
1

Hint

Constraints: For $100\%$ of the data, $1 \leq l \leq r \leq n$, $|d| \leq 10 ^ 3$, and $|s_i| \leq 10 ^ 8$.

Note: In test points $6$ and $7$, during random generation, $s_i$ is chosen randomly from $\{0, 1\}$, and $d$ is chosen randomly from $\{-1, 1\}$. The operation type and the operation interval are both selected uniformly at random.

Translated by ChatGPT 5