时间限制：3000 ms
内存限制：1024 MiB
标准输入输出
题目类型：传统
评测方式：无测试数据
……所以为什么会有两道食堂题？
有一个位于第一象限的食堂。
食堂被划分为若干个 的区域，区域 为以 为顶点的正方形。称两个区域 和 相邻当且仅当 。
区域有两种类型，一种是可供顾客自由走动的过道，另一种是可供顾客坐下用餐的座位。食堂里的座位非常多，而且排布得很有规律：所有满足 且 的区域 是座位，其他区域都是过道。四个相连的座位构成一张餐桌。
从上空俯瞰，食堂中座位的排布方式如下图：
在过道上，顾客可以自由移动。具体地，如果顾客当前位于过道 ，他可以走一步，移动到相邻的区域。如果顾客移动到了座位，他就会在此坐下。
顾客对座位的偏好可以用容忍度 来描述，其中：
-
的顾客只愿意坐到对应餐桌没有人的空座位上吃饭。
-
的顾客只愿意坐到相邻座位没有人的空座位上吃饭。
-
的顾客愿意坐在任何空座位上吃饭。
当一个顾客坐下之后，他就会专注地吃饭，就算有其他顾客出现，导致当前的座位变成他不愿意坐的座位，他也不会因此离开。
最开始的时候，餐厅里一个顾客也没有。接下来依次发生了 个事件，每个事件是以下两种之一：
- 第一种事件：具有某个容忍度 的顾客从区域 进入餐厅，他会寻找移动步数最少的、他愿意坐的座位坐下，如果这样的座位有多个，顾客会选择 坐标最小的，如果还有多个则会选择 坐标最小的。
- 第二种事件：座位 的状态发生了变化，如果原来有顾客坐在这里，这个顾客会立刻离开餐厅；如果原来这个座位上没有顾客，则会出现一个顾客坐在这里。
你需要对于第一种事件求出顾客选择的座位，对于第二种事件求出是有人离开还是有人坐下。
第一行一个正整数 。
接下来 行，每行先是一个整数 ，表示事件种类。
当 时，接下来读入一个整数 ，表示来了一位容忍度为 的顾客。
当 时，接下来读入两个正整数 ，满足 与 ，表示座位 的状态发生了变化。
对每个操作输出一行。
- 对于 的操作，依次输出两个整数 ，表示顾客坐到了座位 。
- 对于 的操作，如果该座位上有人，输出
out，否则输出 in。
样例输入 1
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
1 4
out
in
4 1
1 1
1 2
2 1
1 5
1 7
样例 #1 解释
以下图片展示了每一步操作影响的位置。数字标识了操作的编号。
来源与致谢
来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。
数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public。