Problem B
Collection

Marco is a famous collector of vinyl records. Like any serious collector, Marco identifies each record in his collection by a number.

Marco separates his records into playlists, so he can enjoy them in the best way possible. And like every eccentric collector, he has many obsessions when organizing his records. Marco modifies his playlists by joining two playlists into one, or by removing some records from a playlist end to create another one.

Each playlist of Marco is identified by a numbered tag. When two playlists are merged, Marco stores the tag of the second one on the tag stack. Once a playlist is created, Marco removes the tag on the top of the stack and uses it to identify the new playlist.

Since the collection is very large, Marco hired you to organize the records. As if it wasn’t enough to keep everything in order, Marco also demands that you know the collection. That’s why he often asks you which record is where.

Marco will give you three kinds of orders, each one can be identified by two numbers $i$ and $j$:

• Type $1$: You must say what the $j$-th record of the playlist $i$.

• Type $2$: You must add all records from playlist $j$ to playlist $i$.

• Type $3$: You must keep the first $j$ elements of the $i$-th playlist and create a new playlist with the rest of the records.

Marco is very attentive, so every order he gives is valid meaning he will not mention non-existent playlists and will not create empty playlists. If Marco asks you which record is in a certain position of any playlist and such a record does not exist it is because you missed some previous order.

To ease your arrival to the new work, Marco has created $n$ playlists – ranging from $1$ to $n$. The $i$-th one has the vinyl record with number $i$.

Input

The first line of input contains two integers $n$ and $q$ ($ 1 < n \le 10 ^5 $, $ 1 < q \le 10 ^6 $), the number of records and the number of orders Marco will give you. Then $q$ rows follow, where each line contains $t$ – the type of the order – and $i$ and $j$ which describe such order.

Output

For each order of type $1$, you must print a line with the record number that satisfies it.

2 2
1 1 1
1 2 1

1
2

3 3
2 1 2
2 1 3
1 1 3

3

2 3
2 1 2
3 1 1
1 2 1

2