Grid Operations and Queries

You are given an n x n grid. Initially, all cells have the value \(-1\). You must perform a sequence of \(q\) operations on the grid. There are three types of operations:

• Type 1: 1 i x — Update the entire row \(i\) so that its value becomes \(x\).
• Type 2: 2 j y — Update the entire column \(j\) so that its value becomes \(y\).
• Type 3: 3 i j — Query the cell at row \(i\) and column \(j\). The result is determined by the following rule: if column \(j\) has been updated by an operation of type 2 (i.e. its value is not \(-1\)), then the cell's value is the updated column value; otherwise, it takes the value of row \(i\) (if any update has been applied). If neither a row nor a column update has been performed for that cell, output \(-1\).

More formally, for a query operation on cell \((i, j)\), the answer is computed as follows:

[ \text{answer} = \begin{cases} \text{col}_j, & \text{if } \text{col}_j \neq -1, \ \text{row}_i, & \text{otherwise.} \end{cases} ]

Process the operations in the given order and output the result for each query operation.

inputFormat

The first line contains two space-separated integers \(n\) and \(q\) - the size of the grid and the number of operations, respectively.

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

• 1 i x — Update row i with value x.
• 2 j y — Update column j with value y.
• 3 i j — Query the value at cell (i, j).

Note: The indices i and j are zero-indexed.

outputFormat

For each query operation (operation type 3), output the resulting value on a separate line.

## sample

3 5
1 1 5
2 2 3
3 1 1
3 0 2
3 1 2

5
3
3

</p>