Tom and Jerry are playing with matrices. Jerry gifts Tom with a matrix of size $$M \times N$$. The matrix element have a unique property that each cell of the matrix has value $$A_{i,j} = X + i + j$$. Since Tom loves challenges, Jerry will give Tom $$Q$$ queries. Each of these queries can be of any of the following three types:

$$R$$ $$C_1$$ $$C_2$$: Delete the cells in the Row $$R$$ starting from column $$C_1$$ and ending at column $$C_2$$ $$(1 \le C_1 \le C_2 \le N, 1 \le R \le M)$$
$$C$$ $$R_1$$ $$R_2$$: Delete the cells in column $$C$$ starting from row $$R_1$$ and ending at row $$R_2$$ $$(1 \le R_1 \le R_2 \le M, 1\le C \le N)$$.
$$K$$: Take all the remaining elements in the array and sort the elements by their values. Now, return the $$K^{th}$$ smallest element. If $$K$$ is greater than the number of elements remaining, then print $$-1$$.($$1 \le K \le 10^9$$)

You are required to print the output only in case of the queries of type 3. You must help Tom to solve the tasks and answer the queries given by Jerry.

Input format

The first line of input contains four integers, $$M$$, $$N$$, $$X$$, and $$Q$$ ($$1 \le N, M, X \le 10^9, 1 \le Q \le 5*10^5 $$). Here, $$Q$$ is the number of queries and $$M$$ and $$N$$ are the dimensions of the matrix.
The next $$Q$$ lines contain queries of the type mentioned in the question.
- 1 A B C for queries of type 1
- 2 A B C for queries of type 2
- 3 A for queries of type 3

No two deleted sub rows or subcolumns will intersect, that is the segments queried to be deleted are disjoint.

Output format

For queries of type 3, print a single integer on a new line corresponding to the answer of that query as mentioned in the question.