문제

임의의 양의 정수 $K$에 대해, 인접한 모든 수 사이의 차이가 $K$인 수열을 $K$-계단 수열이라고 하자. 예를 들어 $[4, 5, 6, 5, 6]$은 인접한 모든 수 사이의 차이가 1이므로 $1$-계단 수열이다. 다른 예로 $[17, 12, 17, 22, 27]$은 인접한 모든 수 사이의 차이가 5이므로 $5$-계단 수열이다. 길이가 1인 수열은 모든 $K$-계단 수열에 포함된다.

길이가 $N$인 수열 $a_1,a_2, \cdots,a_N$이 주어질 때, 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• 1 i j x: 현재 수열의 $i$번째 원소부터 $j$번째 원소까지 각각 $x$를 더한다.
• 2 i j k: $i \le l \le r \le j$이면서, $a_l, a_{l+1}, \cdots, a_r$이 $k$-계단 수열일 때, $r-l+1$의 최댓값을 출력한다.

입력

첫째 줄에 $N$ $(1 \le N \le 100\,000)$과 쿼리의 개수 $Q$ $(1 \le Q \le 100\,000)$가 공백으로 구분되어 주어진다.

둘째 줄에 정수 $a_1, a_{2}, \cdots, a_N(-10\,000 \le a_i \le 10\,000)$이 공백으로 구분되어 주어진다.

셋째 줄부터 $Q$개의 줄에 쿼리가 주어진다.

각 쿼리는 네 정수로 이루어져 있으며 $1\ i\ j\ x(1 \le i \le j \le N; -1\,000 \le x \le 1\,000)$ 혹은 $2\ i\ j\ k(1 \le i \le j \le N; 1 \le k \le 10)$이다.

2번 쿼리는 적어도 하나 주어진다.

출력

2번 쿼리가 주어질 때마다 쿼리를 수행한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5 8
6 4 6 5 3
2 1 5 1
1 1 2 1
2 1 5 2
2 2 3 2
1 3 5 1
1 4 5 -1
2 2 5 2
2 3 3 8

예제 출력 1

2
2
1
4
1

• 2 1 5 1: $[6,4,6,5,3]$에서 가장 긴 1-계단 수열은 $[6,5]$이다.
• 1 1 2 1: 쿼리 수행 결과는 $[7,5,6,5,3]$이다.
• 2 1 5 2: $[7,5,6,5,3]$에서 가장 긴 2-계단 수열은 $[7,5]$와 $[5,3]$이다.
• 2 2 3 2: $[5,6]$에서 가장 긴 2-계단 수열은 $[5]$와 $[6]$이다.
• 1 3 5 1: 쿼리 수행 결과는 $[7,5,7,6,4]$이다.
• 1 4 5 -1: 쿼리 수행 결과는 $[7,5,7,5,3]$이다.
• 2 2 5 2: $[5,7,5,3]$에서 가장 긴 2-계단 수열은 $[5,7,5,3]$이다.
• 2 3 3 8: $[7]$에서 가장 긴 8-계단 수열은 $[7]$이다.