Progressive Task Difficulty

This problem involves a game with N tasks, each of which has an initial difficulty \(D_i\). Damian then performs several update operations on these tasks to gradually change their difficulty. The game supports two types of operations:

• Patch Operation: For tasks from L to R, update their difficulty using the formula: \(D_i = D_i + S + (i - L) \times C\).
• Rewrite Operation: For tasks from L to R, completely reset their difficulty using the formula: \(D_i = S + (i - L) \times C\).

A contiguous subsegment of tasks (from task a to task b, where 1 ≤ a ≤ b ≤ N) is considered playable if the difficulties form an arithmetic sequence, i.e. for all a ≤ i < b, the difference \(D_{i+1} - D_i\) is equal to some constant integer \(k\) (which may be negative). Note that a single task is considered a playable subsegment of length 1. Damian sometimes needs to answer queries asking for the length of the longest playable subsegment within a given interval.

inputFormat

The first line contains two integers N and Q, representing the number of tasks and the number of operations respectively.

The second line contains N integers \(D_1, D_2, \dots, D_N\) representing the initial difficulties.

The next Q lines each describe an operation in one of the following formats:

• 1 L R S C — Patch operation. For each task i in [L, R], update \(D_i = D_i + S + (i - L) \times C\).
• 2 L R S C — Rewrite operation. For each task i in [L, R], set \(D_i = S + (i - L) \times C\).
• 3 L R — Query. Find the length of the longest contiguous subsegment within the interval [L, R] whose difficulties form an arithmetic sequence.

outputFormat

For each query operation (type 3), output a single integer on a new line representing the length of the longest playable subsegment in the specified interval.

sample

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

5
3
3