Little Marica's Fairy Tale Train Ride

Little Marica is creating an unusual fairy tale about a train ride taken by N children, numbered from 1 to N (from the youngest with number 1 to the oldest with number N). The train starts at station 0 and stops sequentially at stations 1, 2, 3, … up to infinity.

Marica’s narrative consists of two types of events:

• A statement of the form: "At stop \(X\), child \(A\) got out", which means that the child with identifier \(A\) got off the train at station \(X\). These statements are given in arbitrary order.
• A query from her grandfather: "Based on the statements so far, among the children with identifiers \(\ge B\), who is the youngest child that rode for \(Y\) or less stops?" If, at the moment of a query, no statement has been given for a child then assume that child rides for an infinite number of stops.

Your task is to process a sequence of these events. For every query, you must output the answer as it stands at that moment. Specifically, if a child’s exit station (i.e. the number of stops the child rode) is \(\le Y\), then that child is a valid candidate; among candidates with identifiers \(\ge B\), output the smallest (youngest) identifier. If there is no such child, output -1.

inputFormat

The first line contains two integers \(N\) and \(Q\) — the number of children and the number of events respectively.

Each of the following \(Q\) lines describes an event in one of the following two formats:

• 1 X A: A statement indicating that child \(A\) got out at station \(X\).
• 2 B Y: A query asking, among children with identifiers \(\ge B\), which is the youngest child that rode for \(Y\) or less stops.

It is guaranteed that \(1 \le A, B \le N\). For children that have not yet been mentioned in a statement at the time of a query, assume that they are still on the train (i.e. riding for an infinite number of stops).

outputFormat

For each query, output a single integer on a new line — the identifier of the youngest child (with an identifier \(\ge B\)) who rode for \(Y\) or less stops. If no such child exists, output -1.

sample

5 5
1 3 2
1 2 4
2 2 3
1 1 3
2 3 1

2
3