Parcel Locker Operations

In a supermarket there are (n) parcel lockers, where (1 \le n \le 10^5). The (i)-th locker contains (a_i) compartments numbered from 1 to (a_i), where (1 \le a_i \le 10^5), but the exact values of (a_i) are unknown. However, for each locker, it is guaranteed that (a_i) is at least as large as the maximum compartment number used in any operation on that locker. Note that some lockers may have no compartments used at all.

There are (q) operations ((1 \le q \le 10^5)) of the following two types:

1. Operation of the form: 1 i j k\newline This means storing an item with value (k) (where (0 \le k \le 10^9)) into compartment (j) of locker (i). When (k=0), it indicates that the compartment is being cleared.

2. Operation of the form: 2 i j\newline This is a query operation that asks what item is currently stored in compartment (j) of locker (i). It is guaranteed that locker (i) has had at least one store operation before a query is made on it.

Your task is to process all the operations. For each query operation, output the value stored in the corresponding compartment. If a compartment has never been assigned a value, assume its value is 0.

inputFormat

The input consists of several lines:

• The first line contains two integers (n) and (q), the number of lockers and the number of operations.
• Each of the next (q) lines contains an operation in one of the two formats:
  • For a store operation: 1 i j k
  • For a query operation: 2 i j

It is guaranteed that the total number of compartments across all lockers does not exceed (10^7).

outputFormat

For each query operation, output a single integer representing the item stored in the specified compartment. If the compartment is empty (i.e. no item was stored or it was cleared), output 0.

sample

2 5
1 1 3 100
1 2 1 200
2 1 3
1 2 1 0
2 2 1

100
0