Memories of Bitterness

YQH is haunted by memories of bitter experiences. In his dream, his brain is divided into \(n\) regions, each storing memories (as a multiset) and initially empty. He performs \(m\) operations of three types:

• Operation 1: For all regions from \(l\) to \(r\) (inclusive), a memory with bitterness value \(k\) appears. Formally, for every region \(i\) where \(l \le i \le r\), insert \(k\) into region \(i\).
• Operation 2: Cleaning operation on regions \(l\) to \(r\). Let \(M\) be the maximum bitterness among all memories in regions \(l\) to \(r\). For each region \(i\) in \([l, r]\) that is not empty, if the maximum in region \(i\) equals \(M\), then remove exactly one occurrence of \(M\) from that region. If a region is empty, nothing happens.
• Operation 3: Query. Report the maximum bitterness value among all memories in regions \(l\) to \(r\). If there is no memory in any region within the range, output \(-1\).

The operations are given in order. The input starts with two integers \(n\) and \(m\), followed by \(m\) lines describing the operations. The operations are formatted as follows:

• Operation 1: 1 l r k
• Operation 2: 2 l r
• Operation 3: 3 l r

Your task is to simulate these operations and output the answer for each query (Operation 3).

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of regions and the number of operations respectively.

The next \(m\) lines each describe an operation in one of the following formats:

• 1 l r k: For each region from \(l\) to \(r\) (inclusive), insert a memory with bitterness value \(k\).
• 2 l r: For each region from \(l\) to \(r\), if the maximum memory equals the overall maximum in \([l, r]\), remove one occurrence of that maximum.
• 3 l r: Query the maximum bitterness in regions \(l\) to \(r\). If no memory exists in any of these regions, output \(-1\).

outputFormat

For each Operation 3, output the maximum bitterness value in the specified range. If there is no memory in any region in the range, output \(-1\).

sample

3 6
1 1 3 5
3 1 3
1 2 2 7
3 1 3
2 1 3
3 1 3

5
7
5