시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 0 0 0 0.000%

문제

Damian is making a video game! It consists of N missions with the ith mission initially having a difficulty of Di. Featuring state-of-the-art game design, the game can be played both forwards and backwards. Of course, it is also important that players feel a sense of progression — there should be a constant increase in difficulty. As such, Damian carries out a series of operations.

There are two types of operations that he does. The first type of operation is a patch operation defined by four integers L, R, S and C, meaning that mission i where L ≤ i ≤ R will have its difficulty Di increased by S + (i − L) × C.

The second type of operation is a rewrite operation defined by four integers L, R, S and C, meaning that mission i where L ≤ i ≤ R will have its difficulty Di set to S + (i − L) × C.

Damian decides that a contiguous subsequence of missions forms a playable segment if and only if their difficulties change at a constant rate (after all, players can always play the game backwards instead)! In other words, missions a to b where 1 ≤ a ≤ b ≤ N form a playable segment if and only if Di+1 − Di = k for all a ≤ i < b where k is some integer (possibly k ≤ 0). A single mission on its own forms a playable segment of length 1.

Occasionally, Damian will run an evaluate query defined by two integers L and R, meaning that he wants to find the length of the longest playable segment between missions L and R at that point in time.

Alas, Damian’s operations do not necessarily improve the gaming experience. As such, he needs your help to answer the queries so that he can develop the best game possible.

입력

Your program must read from standard input.

The first line contains two integers, N and Q, representing the number of missions, and the total number of operations and queries.

The second line contains N space-separated integers, D1, . . . , DN, defined above.

Q lines will follow, each representing either an operation or a query.

If the line begins with the integer 1, the next 4 integers are L, R, S and C, representing a patch operation.

If the line begins with the integer 2, the next 4 integers are L, R, S and C, representing a rewrite operation.

If the line begins with the integer 3, the next 2 integers are L and R, representing an evaluate query.

출력

Your program must print to standard output.

The output should consist of a single integer on a single line for each evaluate query, the length of the longest playable segment between missions L and R at that point in time.

제한

  • 1 ≤ N, Q ≤ 3 × 105
  • −106 ≤ Di, S, C ≤ 106
  • 1 ≤ L ≤ R ≤ N

예제 입력 1

10 6
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10
3 9 10
2 5 10 -2 -2
3 1 10

예제 출력 1

5
6
2
7

For the first evaluate query, missions 5 to 9 form the longest playable segment (with k = 1).

After the patch operation, the difficulties become [0, 0, 0, 0, 1, 2, 3, 4, 5, 5].

For the second evaluate query, missions 4 to 9 form the longest playable segment (with k = 1).

For the third evaluate query, missions 9 to 10 form the longest playable segment (with k = 0), as we only consider missions between missions L = 9 and R = 10.

After the rewrite operation, the difficulties become [0, 0, 0, 0, −2, −4, −6, −8, −10, −12].

For the final evaluate query, missions 4 to 10 form the longest playable segment (with k = −2).

예제 입력 2

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

예제 출력 2

5
5
10

예제 입력 3

10 5
1 2 3 4 1 2 3 4 5 5
3 1 4
3 4 5
3 2 4
3 5 9
3 10 10

예제 출력 3

4
2
3
5
1

예제 입력 4

10 5
1 2 3 4 1 2 3 4 5 5
2 10 10 6 1
3 5 10
1 5 5 4 1
3 1 5
3 1 6

예제 출력 4

6
5
5

Note that C is not necessarily 0 when L = R. However, its value is irrelevant to the operation.

예제 입력 5

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

예제 출력 5

4
2
9