There is a dining hall located in the first quadrant.

The dining hall is divided into several $1 \times 1$ regions, where a region $(x, y)$ is defined as the square with vertices $(x, y), (x, y + 1), (x + 1, y), (x + 1, y + 1)$. Two regions $(x_1, y_1)$ and $(x_2, y_2)$ are said to be adjacent if and only if $|x_1 - x_2| + |y_1 - y_2| = 1$.

There are two types of regions: aisles, where customers can move freely, and seats, where customers can sit to dine. There are many seats in the dining hall, arranged in a regular pattern: all regions $(x, y)$ satisfying $x \pmod 3 \neq 0$ and $y \pmod 3 \neq 0$ are seats, and all other regions are aisles. Four connected seats form a dining table.

The layout of the seats in the dining hall, viewed from above, is as follows:

In the aisles, customers can move freely. Specifically, if a customer is currently at an aisle $(x, y)$, they can take one step to move to an adjacent region. If a customer moves to a seat, they will sit down there.

A customer's preference for seats can be described by their tolerance $o \in \{0, 1, 2\}$, where: Customers with $o = 0$ are only willing to sit at an empty seat at a dining table where no one else is currently sitting. Customers with $o = 1$ are only willing to sit at an empty seat where no one is sitting in any adjacent seat. * Customers with $o = 2$ are willing to sit at any empty seat.

Once a customer sits down, they focus on their meal; even if other customers arrive and cause the current seat to become one they would not be willing to sit in, they will not leave.

Initially, there are no customers in the restaurant. Subsequently, $q$ events occur, each being one of the following two types: Type 1: A customer with a certain tolerance $o$ enters the restaurant from region $(0, 0)$. They will look for an empty seat they are willing to sit in that requires the minimum number of steps to reach. If there are multiple such seats, the customer will choose the one with the smallest $x$-coordinate, and if there are still multiple, the one with the smallest $y$-coordinate. Type 2: The status of seat $(x, y)$ changes. If there was a customer sitting there, that customer immediately leaves the restaurant; if there was no customer at this seat, a new customer appears and sits there.

You need to determine the seat chosen by the customer for Type 1 events, and whether someone leaves or sits down for Type 2 events.

Input

Read data from standard input.

The first line contains a positive integer $q$ ($1 \leq q \leq 5 \times 10^5$).

The next $q$ lines each start with an integer $t \in \{1, 2\}$, representing the event type.

When $t = 1$, an integer $o \in \{0, 1, 2\}$ follows, representing a customer with tolerance $o$.

When $t = 2$, two positive integers $x, y$ ($1 \leq x, y \leq 10^4$) follow, satisfying $x \pmod 3 \in \{1, 2\}$ and $y \pmod 3 \in \{1, 2\}$, representing that the status of seat $(x, y)$ has changed.

Output

Output to standard output.

For each operation, output one line. For $t = 1$ operations, output two integers $x, y$ representing that the customer sat at seat $(x, y)$. For $t = 2$ operations, if there was someone at the seat, output out, otherwise output in.

Examples

Input 1

10
1 0
1 0
2 1 1
2 2 2
1 0
1 1
1 2
1 2
1 2
1 1

Output 1

1 1
1 4
out
in
4 1
1 1
1 2
2 1
1 5
1 7

Note

The following image shows the positions affected by each step. The numbers identify the operation index.