Background

……所以为什么会有两道食堂题？

Description

有一个位于第一象限的食堂。

食堂被划分为若干个 $1\times 1$ 的区域，区域 $(x,y)$ 为以 $(x,y),(x,y+1),(x+1,y),(x+1,y+1)$ 为顶点的正方形。称两个区域 $(x_1,y_1)$ 和 $(x_2,y_2)$ 相邻 当且仅当 $|x_1-x_2|+|y_1-y_2|=1$。

区域有两种类型：

• 过道：顾客可以自由走动；
• 座位：顾客可以坐下用餐。

座位的分布规律是：所有满足 $x\bmod 3\ne 0$ 且 $y\bmod 3\ne 0$ 的区域 $(x,y)$ 是座位，其他区域为过道。四个相连的座位构成一张餐桌。

顾客的容忍度 $o\in{0,1,2}$ 决定了他们愿意坐的座位：

• $o=0$：只坐到对应餐桌没有人的空座位；
• $o=1$：只坐到相邻座位没有人的空座位；
• $o=2$：愿意坐任何空座位。

当顾客坐下后，即使后来变成不符合其容忍度的座位，他也不会离开。

最初餐厅没有顾客，接下来依次发生 $q$ 个事件：

1. 顾客到来：一位容忍度为 $o$ 的顾客从 $(0,0)$ 进入，寻找移动步数最少的、他愿意坐的座位，如果有多个，选 $x$ 最小的，若仍有多个，则选 $y$ 最小的；
2. 座位状态变化：如果原来有人，则该顾客立刻离开；如果原来没人，则有顾客坐下。

你需要输出每次事件的结果。

Format

Input

第一行一个整数 $q\ (1\le q\le5\times10^5)$。

接下来 $q$ 行，每行是以下两种之一：

• 1 o：表示有一位容忍度为 $o$ 的顾客到来；
• 2 x y：表示座位 $(x,y)$ 的状态发生变化，满足 $x\bmod3\in{1,2}$ 且 $y\bmod3\in{1,2}$。

Output

对于每个操作输出一行：

• $t=1$：输出两个整数 $x,y$，表示顾客坐下的位置；
• $t=2$：如果原来有人，输出 out，否则输出 in。

Samples

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

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