Brain Hole Treatment

SHTSC, the inventor of the automatic problem solving machine, has now revealed his new invention: the brain hole treatment device. In this problem, we model the brain as a binary sequence. A 1 indicates normal brain tissue, whereas a 0 indicates a brain hole. Initially, the brain is healthy (all ones).

The device works in two ways:

• Dig Operation: Given an interval, convert all cells in that interval to 0 (i.e. dig a brain hole).
• Treatment Operation: Given a source interval and a target interval, the device "excavates" the source interval to collect normal tissues. Suppose the source interval has $x$ cells with value 1. Then, scanning the target interval from left to right, for each cell that is 0, if $x>0$, it is filled with a 1 and $x$ is decreased by 1. Any leftover tissues are discarded. Finally, the entire source interval is set to 0.

In addition, SHTSC will ask queries of the form: in a given interval, what is the length of the longest continuous segment of brain holes (0's)? If there are multiple operations, execute them in order, and answer each query immediately.

Formally, let the brain be represented as an array \(a[1\ldots n]\). Initially, \(a_i = 1\) for all \(1 \le i \le n\). There are three types of operations:

1. Dig Operation: 1 L R — For all indices \(i\) with \(L \le i \le R\), set \(a_i = 0\).
2. Treatment Operation: 2 L R U V — Use the source interval \([L,R]\) and target interval \([U,V]\). Let \(x\) be the number of indices in \([L,R]\) where \(a_i = 1\). Then, for indices \(j\) from \(U\) to \(V\) (in increasing order), if \(a_j = 0\) and \(x > 0\), set \(a_j = 1\) and decrease \(x\) by 1. Finally, set every \(a_i\) for \(i \in [L,R]\) to 0.
3. Query Operation: 3 L R — Report the length of the longest contiguous segment of 0's within the interval \([L,R]\).

Note: In all operations, the indices are 1-indexed.

Input Constraints: You may assume that \(n\) and the number of operations are reasonably small so that a direct simulation is possible.

inputFormat

The first line contains two integers \(n\) and \(q\) — the length of the brain array and the number of operations, respectively.

Each of the following \(q\) lines represents an operation in one of the following formats:

• 1 L R: Dig operation — set all positions from \(L\) to \(R\) to 0.
• 2 L R U V: Treatment operation — use the source interval \([L,R]\) to attempt to fill the holes (0's) in the target interval \([U,V]\).
• 3 L R: Query operation — output the length of the longest contiguous segment of 0's in the interval \([L,R]\).

outputFormat

For each query (operation of type 3), output one integer on a separate line representing the length of the longest consecutive 0's within the given interval.

sample

10 6
1 2 6
3 1 10
2 7 10 1 4
3 1 10
2 1 4 8 10
3 1 10

5
6
7