Dynamic String Maintenance and Lexicographical Suffix Query

You are given a dynamic array \(s = [s_1, s_2, ..., s_n]\) where each \(s_i\) is an integer satisfying \(|s_i| \le 10^9\). The array supports two types of operations:

1. Update Operation: Given three integers \(l\), \(r\), and \(d\), for every index \(i\) with \(l \le i \le r\), update the element \(s_i\) as \(s_i = s_i + d\). Note that \(d\) can be negative.
2. Query Operation: Given two integers \(l\) and \(r\), consider all suffixes of the subarray \(s[l..r]\). That is, for every \(p\) with \(l \le p \le r\) consider the subarray \(s[p..r]\). You are to determine the starting index \(p\) such that \(s[p..r]\) is lexicographically minimum among these suffixes. In lexicographical comparison, if one subarray is a prefix of another, then the shorter one is considered to be smaller.

All indices are 1-indexed.

inputFormat

The first line of input contains two integers \(n\) and \(m\) representing the number of elements in the string and the number of operations, respectively.

The second line contains \(n\) integers \(s_1, s_2, \ldots, s_n\) denoting the initial array.

Each of the following \(m\) lines represents an operation in one of the following formats:

• For an update operation: 1 l r d
• For a query operation: 2 l r

outputFormat

For each query operation, output one line with a single integer representing the starting index of the lexicographically smallest suffix of \(s[l..r]\).

sample

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

2
2
2