Problem Description

There are $n(1\le n\le10^5)$ parcel lockers in a supermarket. Each locker has a different number of compartments. The $i$-th locker has $a_i(0\le a_i\le10^5)$ compartments, but we do not know the values of $a_i$. For each locker, the compartments are numbered from 1 to $a_i$. Now there are $q(1 \le q\le10^5)$ operations:

• 1 i j k: Put item $k(0\le k\le 10^9)$ into compartment $j$ of locker $i$. When $k=0$, it means clearing that compartment.
• 2 i j: Query what item is in compartment $j$ of locker $i$. It is guaranteed that the queried locker has had items stored in it.

It is known that the total number of compartments in the supermarket will not exceed $10^7$. The values $a_i$ are fixed but unknown, and it is guaranteed that $a_i$ is at least the maximum compartment index ever used in a store-item request for that locker. Of course, it is also possible that some lockers do not have even a single compartment.

Input Format

The first line contains 2 integers $n$ and $q$, the number of parcel lockers and the number of queries.

The next $q$ lines each contain several integers, representing one operation.

Output Format

For each query operation, output the answer, one per line.

5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1

118014
1

Hint

$\text{upd 2022.7.26}$: A new set of hack testdata has been added.

Translated by ChatGPT 5