Maintain Multiset Collections

You are given (n) multisets numbered from (1) to (n), initially all empty. There are (m) operations to perform on these multisets. The operations are of two types:

• 1 l r c: Add the integer \(c\) to each multiset with an index in the range \([l, r]\).
• 2 l r c: Query the union of the multisets with indices in the range \([l, r]\) (note that the union of multisets is defined as simply the concatenation of them, i.e. duplicates are not removed). Return the \(c\)-th smallest element in this union. For example, \(\{1,1,4\} \cup \{5,1,4\} = \{1,1,4,5,1,4\}\).

All operations are guaranteed to be valid and the query operations will always have a valid answer.

inputFormat

The first line contains two integers (n) and (m) representing the number of multisets and the number of operations, respectively. Each of the next (m) lines contains an operation in one of the following formats:

1 l r c 2 l r c

For the add operation, (c) is added to each multiset with indices from (l) to (r). For the query operation, you should output the (c)-th smallest number from the union (with duplicates) of multisets with indices in ([l, r]).

outputFormat

For each query (operation of type 2), output the answer on a new line.

sample

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

5
5