Flip

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