You are given the X coordinate of N points on the X axis.
You need to handle Q queries of following three types :
- Add a point at X coordinate x.
- Shift all points in the range \([L, R]\) by a distance L to the left.
- Find the minimum distance between any two points in the range \([L, R]\).
Input:
First line of input contains two space separated integers N and Q, denoting the number of points and number of queries. Next line contains N integers, denoting the X coordinate of the \(i^{th}\) point. Each of the next Q lines describe a query.
The first integer denotes the type of query. If it is one then it is a type one query and next integer denotes x, the X coordinate of new point to be added.
If the first integer is two then it is a type two query and next two integers are L and R. Here, L and R is the range in which if a point lies, it needs to be shifted to the left by an amount L.
If the first integer is three then it is a type three query and next two integers are L and R. Here, L and R is the range in which you need to find the minimum distance between any two points.
Output:
For each query of third kind, output the required distance on a new line. If there are less than two points in the range \([L, R]\), print 1.
Constraints:
\(1 \le N, Q \le 2 \times 10^5\)
\(1 \le L \le R \le 10^9\)
\(1 \le x \le 10^9\)