A cache holds a fixed number of entries and counts how often each is touched, by storing or reading. When it is full, the least often touched entry goes, and if several are equally untouched, the one that has gone longest without a touch goes. Report the answer to every read.

Two things have to be ordered at once here, the use counts and, within one count, the order of last use. Keeping a list per count, each in use order, gives both: the entry to evict is at the end of the list belonging to the smallest count in use.

Command 1 stores value y under key x, command 2 reads key x and ignores y.

Input

The cache size on the first line, then the command count and one line per command holding its kind and two numbers.

Output

One line per read, holding the value stored, or -1 if the key is not held.

Sample test cases

Input 2 10 1 1 1 1 2 2 2 1 0 1 3 3 2 2 0 2 3 0 1 4 4 2 1 0 2 3 0 2 4 0 Expected output 1 -1 3 -1 3 4

Input

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

Expected output 1 -1 2