John is a bit upset now. Today was his chemistry central viva and it did not go very well. So to cheer up he bought a notebook, a pencil and an eraser.

In the note book there are N points drawn in a row. The points are numbered from 1 to N serially.

Now, John decided to do a strange thing with those points.

At each moment, John puts his pencil or eraser at a point A and drags it to point B. As a result, some line segments may be created.

And then, sometimes he stops and thinks of a point C and tries to find out if point C is on a line segment or not.

You have to solve a similar problem.

Input

First line of the input will contain two integers N (1 <= n <= 10⁹) and M (1 <= M <= 10⁵) where N denotes number of points and M denotes number of queries.

Then M line follows. Each line contains a query.

Each query will be one of the following forms:

0 A B: which means an eraser has been dragged from point A to point B.

1 A B: which means a pencil has been dragged from point A to point B.

2 C: which means you are asked to answer the state of point C. There will be at least one query of this type.

(It is guaranteed that A <= B and 1 <= A, B, C <= N)

Output

For each query of the form "2 C", print a single line. If point C is NOT on any line segment then print -1.

Otherwise, print the start and end point of the segment.

See sample and explanation for details.

Sample>

Input
25 14
2 10
1 20 25
1 9 13
2 12
2 7
1 11 21
2 15
0 17 20
0 22 25
2 21
2 5
1 1 8
2 12
2 4

Output
-1
9 13
-1
9 25
21 21
-1
9 16
1 8

Explanation

In the 1^st query, there are no line segments. So point 10 is not on any segment.

After 2^nd query, there is 1 line segment: [20, 25].

After 3rd query, there are 2 line segments:  [9, 13], [20, 25].

In the 4^th query, point 12 is on [9, 13] segment.

In the 5^th query, point 7 is not on any segment.

After 6^th query, there is 1 line segment [9, 25]. ([9, 13], [11, 21] and [20, 25] segments will merge into only 1 segment).

In the 7^th query, point 15 is on [9, 25] segment.

After 9^th query there are 2 segments: [9, 16] and [21, 21].

In the 10^th query, point 21 is on [21, 21] segment.

In the 11^th query, point 5 is not on any segment.

After 12^th query there are 3 segments: [1,8],[9, 16] and [21, 21].

In the 13^th query, point 13 is on [9, 16] segment.

In the 14^th query, point 4 is on [1, 8] segment.