C. 餐厅
每个测试点时间限制：2 秒
内存限制：512 兆字节

在一个巨大的王国中，有一座无限大的餐厅。它可以表示为所有单元格 $(x, y)$ 的集合，其中 $x$ 和 $y$ 是非负整数。餐厅里有无限多张桌子。每张桌子占据四个单元格：

$$(3x+1,\ 3y+1),\quad (3x+1,\ 3y+2),\quad (3x+2,\ 3y+1),\quad (3x+2,\ 3y+2) $$

其中 $x$ 和 $y$ 是任意非负整数。所有不属于任何桌子的单元格都是走廊。

有 $n$ 位客人依次来到餐厅。每位客人出现在单元格 $(0,0)$，并希望到达一个桌子的单元格。

• 在每一步中，他们可以移动到相邻（共享一条边）的走廊单元格。
• 在最后一步，他们必须移动到相邻的空闲桌子单元格。
• 客人会占据所选的桌子单元格，其他客人不能移动到该位置。

每位客人有一个特征 $t_i$，取值为 $0$ 或 $1$。他们按顺序进入餐厅，从 $(0,0)$ 开始移动。

• 如果 $t_i = 1$：第 $i$ 位客人会走到最近的空闲桌子单元格。
• 如果 $t_i = 0$：第 $i$ 位客人会走到最近的、属于一张完全空闲的桌子的桌子单元格（注意：之后其他客人也可以选择同一张桌子的其他单元格）。

距离定义为到达桌子单元格所需的最少步数。
如果存在多个相同距离的桌子单元格，则客人优先选择 $x$ 坐标最小的；如果仍有并列，则选择 $y$ 坐标最小的。

对于每位客人，求出他们选择的桌子单元格。

---

输入格式

第一行包含一个整数 $q$（$1 \le q \le 5000$），表示测试用例数量。随后是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 50000$），表示客人数。

第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$（$t_i \in \{0,1\}$），表示每位客人的特征。

保证所有测试用例的 $n$ 之和不超过 $50000$。

---

输出格式

对于每个测试用例，输出 $n$ 行，每行两个整数，表示对应客人坐下的单元格坐标。

---

示例输入

2
6
0 1 1 0 0 1
5
1 0 0 1 1

示例输出

1 1
1 2
2 1
1 4
4 1
1 5
1 1
1 4
4 1
1 2
2 1

---

提示

考虑第一个测试用例：

• 第 1 位客人到达单元格 $(1,1)$ 的距离为 $2$，他坐在这里。
• 第 2 位客人到达 $(1,2)$ 的距离为 $3$，到达 $(2,1)$ 的距离也是 $3$。由于 $x$ 坐标更小，他选择 $(1,2)$。
• 第 3 位客人到达 $(2,1)$ 的距离为 $3$，他选择它。
• 第 4 位客人到达 $(1,4)$ 的距离为 $5$，他选择它。
• 第 5 位客人到达 $(4,1)$ 的距离为 $5$。
• 第 6 位客人到达 $(1,5)$ 的距离为 $6$，到达 $(2,2)$ 的距离也是 $6$。由于 $x$ 坐标更小，他选择 $(1,5)$。
•