You are given the X coordinate of N points on the X axis.

You need to handle Q queries of following three types :

1. Add a point at X coordinate x.
2. Shift all points in the range $[L, R]$ by a distance L to the left.
3. 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$