DRWLNS - Drawing Lines

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 <= 109) and M (1 <= M <= 105) 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 1st query, there are no line segments. So point 10 is not on any segment.

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

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

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

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

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

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

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

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

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

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

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

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


Added by:Md. Najim Ahmed
Date:2015-12-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2015-12-11 12:54:05 Md. Najim Ahmed
i'm sorry :( but there was a serious mistake in the data set. its been fixed now and all submission has been rejudged ... some additional sample test cases have also been added ...
again, i'm really sorry for this inconvenience :(

Last edit: 2015-12-12 15:59:43
2015-12-11 12:37:34 abdou_93
@Md. Najim Ahmed , Good problem .
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.