P3613 [Shenji 15. Example 2] Parcel Locker

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.

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.

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

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