CF35B.Warehouse

Once upon a time, when the world was more beautiful, the sun shone brighter, the grass was greener and the sausages tasted better Arlandia was the most powerful country. And its capital was the place where our hero DravDe worked. He couldn’t program or make up problems (in fact, few people saw a computer those days) but he was nevertheless happy. He worked in a warehouse where a magical but non-alcoholic drink Ogudar-Olok was kept. We won’t describe his work in detail and take a better look at a simplified version of the warehouse.

The warehouse has one set of shelving. It has n shelves, each of which is divided into m sections. The shelves are numbered from top to bottom starting from 1 and the sections of each shelf are numbered from left to right also starting from 1. Each section can contain exactly one box of the drink, and try as he might, DravDe can never put a box in a section that already has one. In the course of his work DravDe frequently notices that he has to put a box in a filled section. In that case his solution is simple. DravDe ignores that section and looks at the next one to the right. If it is empty, he puts the box there. Otherwise he keeps looking for the first empty section to the right. If no empty section is found by the end of the shelf, he looks at the shelf which is under it, then the next one, etc. Also each time he looks at a new shelf he starts from the shelf’s beginning. If DravDe still can’t find an empty section for the box, he immediately drinks it all up and throws the empty bottles away not to be caught.

After one great party with a lot of Ogudar-Olok drunk DravDe asked you to help him. Unlike him, you can program and therefore modeling the process of counting the boxes in the warehouse will be easy work for you.

The process of counting contains two types of query messages:

• «+1 x y id» (where x, y are integers, 1 ≤ x ≤ n, 1 ≤ y ≤ m, and id is a string of lower case Latin letters — from 1 to 10 characters long). That query means that the warehouse got a box identified as id, which should be put in the section y on the shelf x. If the section is full, use the rules described above. It is guaranteed that every moment of the process the identifiers of all the boxes in the warehouse are different. You don’t have to answer this query.
• «-1 id» (where id is a string of lower case Latin letters — from 1 to 10 characters long). That query means that a box identified as id is removed from the warehouse. You have to answer this query (see output format).

很久以前，当世界更加美丽、阳光更加明媚、青草更加翠绿、香肠更加美味时，阿兰迪亚（Arlandia）是世界上最强大的国家，而它的首都正是我们的主人公德拉夫德（DravDe）工作的地方。他既不会编程，也不会编题（事实上，那个年代几乎没人见过计算机），但他依然过得很快乐。他在一座仓库工作，那里储藏着一种神奇却不含酒精的饮品——奥古达尔-奥洛克（Ogudar-Olok）。我们不会详述他的日常工作，而是转而考察这座仓库的一个简化模型。

该仓库只有一组货架，共包含 $n$ 层货架，每层又被划分为 $m$ 个格子。货架从上到下编号，依次为 $1, 2, \dots, n$；每层货架上的格子则从左到右编号，依次为 $1, 2, \dots, m$。每个格子恰好可容纳一箱该饮品；无论德拉夫德如何努力，他都无法将一箱饮品放入一个已有箱子的格子中。在日常工作中，德拉夫德常常发现他需要把一箱饮品放进一个已被占满的格子。此时，他的处理方式非常简单：他直接忽略该格子，转而查看其右侧的下一个格子；若该格子为空，则将箱子放入其中；否则，他继续向右寻找第一个空格子。若在当前货架的最右端仍未找到空格子，则他转向正下方的下一层货架，并从该层最左侧的第一个格子重新开始查找；依此类推。如果经过全部货架仍未能找到空格子，他便会立即将这箱饮品全部喝光，并把空瓶扔掉，以免被人发现。

在一次盛大的聚会之后（会上饮用了大量奥古达尔-奥洛克），德拉夫德请求你帮助他。与他不同，你精通编程，因此对仓库中箱子数量变化过程进行建模对你而言轻而易举。

计数过程包含两类查询消息：

• «+1 x y id»（其中 $x$、$y$ 为整数，满足 $1 \le x \le n$、$1 \le y \le m$；$id$ 是一个由小写拉丁字母组成的字符串，长度为 $1$ 至 $10$ 个字符）。该查询表示仓库新收到一箱标识为 $id$ 的饮品，应将其放置于第 $x$ 层货架的第 $y$ 个格子中。若该格子已被占用，则按上述规则寻找下一个可用空格子。保证在整个过程中，仓库内所有箱子的标识符互不相同。你无需对此类查询作出响应。
• «-1 id»（其中 $id$ 是一个由小写拉丁字母组成的字符串，长度为 $1$ 至 $10$ 个字符）。该查询表示标识为 $id$ 的箱子被从仓库中移除。你必须对此类查询作出响应（参见输出格式）。

The first input line contains integers n, m and k (1 ≤ n, m ≤ 30, 1 ≤ k ≤ 2000) — the height, the width of shelving and the amount of the operations in the warehouse that you need to analyze. In the following k lines the queries are given in the order of appearance in the format described above.

第一行输入包含整数 $n$、$m$ 和 $k$（$1 ≤ n, m ≤ 30$，$1 ≤ k ≤ 2000$）——分别表示货架的高度、宽度以及你需要分析的仓库操作数量。接下来的 $k$ 行按出现顺序给出上述格式的查询。

For each query of the «-1 id» type output two numbers in a separate line — index of the shelf and index of the section where the box with this identifier lay. If there was no such box in the warehouse when the query was made, output «-1 -1» without quotes.

对于每个类型为 «-1 id» 的查询，在单独一行中输出两个数字——该标识符对应的箱子所在的货架索引和货格索引。如果执行查询时仓库中不存在该标识符的箱子，则输出 «-1 -1»（不带引号）。