一家著名的公司有两种类型的员工：外向者（extroverts）和内向者（introverts）。这两类人在很多方面都有所不同，在本题中，我们考虑他们在用餐时行为的差异。

该公司的食堂可以表示为一个 $N \times M$ 的网格。换句话说，每个具有整数坐标 $x, y$（$0 \le x \le N$，$0 \le y \le M$）的点都有一张餐桌。每张餐桌仅供一人使用。

我们定义坐标为 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的两点之间的（欧几里得）距离为 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$。

当一名内向者来到食堂时，他会选择一张空闲的餐桌，使得该餐桌到最近的已占用餐桌的最短距离尽可能大。如果有多个餐桌都达到了这个最大的最短距离，他会选择其中 $x$ 坐标最小的餐桌。如果仍有多个餐桌，他会选择其中 $y$ 坐标最小的餐桌。

当一名外向者来到食堂时，他会选择一张空闲的餐桌，使得该餐桌到最远的已占用餐桌的最大距离尽可能小。如果有多个餐桌都达到了这个最小的最大距离，他会选择其中 $x$ 坐标最小的餐桌。如果仍有多个餐桌，他会选择其中 $y$ 坐标最小的餐桌。

给你食堂的大小以及 $Q$ 个事件的描述。每个事件要么是一个人的到达，要么是一个人的离开。对于每次到达，你都需要求出他所占用的餐桌。

输入格式

输入的第一行包含三个空格隔开的整数 $N, M, Q$（$1 \le N, M \le 5000$，$0 \le Q \le 100$）。

接下来的 $Q$ 行描述了事件。如果第 $i$ 个事件是外向者的到达，则第 $i$ 行包含单个字符串 ext；如果该事件是内向者的到达，则该行包含单个字符串 int；如果该事件是某人的离开，则该行包含一个从 1 开始的索引（在所有事件中），表示描述其到达的那个事件的编号。

保证输入数据是合法的，即对于每个到达的人，在其到达时食堂中至少有一张空闲餐桌；且对于每个离开事件，行中描述的索引均对应一个到达事件，且该事件中到达的人此时仍在食堂内。

输出格式

对于每次到达，输出一行，包含两个空格隔开的整数，表示被占用的餐桌的坐标。

样例

输入格式 1

5 5 5
int
1
ext
3
int

输出格式 1

0 0
0 0
0 0

输入格式 2

4 4 8
ext
ext
int
int
int
2
int
int

输出格式 2

0 0
0 1
4 4
4 0
0 4
2 2
0 2