Ephie is working on a new barcode of the length N. This barcode can be coded into a string of 0s and 1s. At first, all of the elements are 0s. In order to create a more complex barcode, she chooses some intervals and changes the values of all the elements in the interval **(from 0 to 1, and vice versa)**. Occasionally, Ephie wonders what are the ends of the sequence in which the pth element is contained. An element belongs to the sequence if and only if it is adjacent to p or if it is adjacent to an element belonging to the sequence. Two elements are adjacent if they are in consecutive positions in the sequence and **they have the same value.**

Given the operations executed on the string, answer Ephie's questions.

## Input

**N and M, representing the length and the number of operations executed on the sequence**are on the first line of the standard input. The operations executed on the string are on the next M lines. The first number on the line represents the type of operation:

**1 for a change of values in the interval**,

**2 for an interrogation**. In the first case, the following numbers will

**be a and b**, representing the ends of the interval on which the operation has been executed. In the second case, the following number will be

**p**, the position for which you need to print 3 numbers of the form

`val x y`

, the value of the **pth element of the sequence**and

**the ends of the sequence which the pth element it belongs to**.

## Output

The output contains the answers to the type 2 operations on each line.## Constraints

`1 ≤ N, M ≤ 100 000`

`1 ≤ a, b, p ≤ N`

**The sequence is 1-based indexed.**

## Sample

Input | Output |
---|---|

5 7 1 1 3 1 2 4 2 1 2 2 2 3 2 4 2 5 | 1 1 1 0 2 3 0 2 3 1 4 4 0 5 5 |