ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5910: Warehouse

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：4 通过：2
提交提交记录统计Web Board

题目描述

    曾几何时，当世界更美丽，阳光更明亮，草更绿，香肠味道更好在阿兰迪亚更好吃。它的首都是我们英雄德拉夫德工作的地方。他不会编程或编造问题（事实上，当时很少有人看到电脑），但他仍然很高兴。他在一个仓库工作，那里保存着一种神奇但不含酒精的饮料Ogudar-Olok。我们不会详细描述他的工作，而是更好地看一下仓库的简化版本。
    仓库有一套货架。它有n个架子，每个架子分为m个部分。搁板从上到下编号从 1 开始，每个搁板的部分也从左到右编号，也从 1 开始。每个部分只能包含一盒饮料，无论他怎么努力，DravDe 都无法将盒子放在已经有饮料的部分。在他的工作过程中，DravDe经常注意到他必须在填充部分放置一个盒子。在这种情况下，他的解决方案很简单。DravDe忽略了该部分，并查看了右侧的下一个部分。如果它是空的，他就把盒子放在那里。否则，他会一直寻找右侧的第一个空白部分。如果在架子的尽头没有找到空的部分，他会查看它下面的架子，然后是下一个，依此类推。此外，每次他看到一个新的架子时，他都会从架子的起点开始。如果德拉夫德仍然找不到盒子的空部分，他会立即将其全部喝光，并将空瓶子扔掉以免被抓住。
在一次很棒的派对之后，有很多Ogudar-Olok 醉酒的德拉夫德要求你帮助他。与他不同，您可以编程，因此对仓库中箱子的计数过程进行建模对您来说很容易。
计数过程包含两种类型的查询消息：

· «+1 x y id» （其中 x， y 是整数，1≤x≤n， 1≤y≤m，id 是一串小写拉丁字母 − 长度从 1 到 10 个字符）。 该查询意味着仓库得到了一个标识为 id 的框，该框应放在货架 x 上的 y 部分中。如果该部分已满，请使用上述规则。可以保证，在流程的每一刻，仓库中所有盒子的标识符都是不同的。您不必回答此查询。

· «-1 id» （其中 id 是一串小写拉丁字母 − 长度为 1 到 10 个字符）。该查询意味着标识为 id 的框将从仓库中删除。您必须回答此查询（请参阅输出格式）。

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).
Input
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.
Output
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.
Examples
Input 
2 2 9
+1 1 1 cola
+1 1 1 fanta
+1 1 1 sevenup
+1 1 1 whitekey
-1 cola
-1 fanta
-1 sevenup
-1 whitekey
-1 cola
Output 
1 1
1 2
2 1
2 2
-1 -1
Input 
2 2 8
+1 1 1 cola
-1 cola
+1 1 1 fanta
-1 fanta
+1 1 1 sevenup
-1 sevenup
+1 1 1 whitekey
-1 whitekey
Output 
1 1
1 1
1 1
1 1

输入格式

第一个输入行包含整数 n、m 和 k （1≤n，m≤30， 1≤k≤2000） - 货架的高度、宽度和仓库中需要分析的操作量。 在以下 k 行中，查询按上述格式的出现顺序给出。

输出格式

对于 «-1 id» 类型的每个查询，在单独的行中输出两个数字 − 货架的索引和具有此标识符的框所在的部分的索引。如果进行查询时仓库中没有这样的框，则输出不带引号的 «-1 -1»。
Input 

2 2 9
+1 1 1 cola
+1 1 1 fanta
+1 1 1 sevenup
+1 1 1 whitekey
-1 cola
-1 fanta
-1 sevenup
-1 whitekey
-1 cola
Output 
1 1
1 2
2 1
2 2
-1 -1
Input 
2 2 8
+1 1 1 cola
-1 cola
+1 1 1 fanta
-1 fanta
+1 1 1 sevenup
-1 sevenup
+1 1 1 whitekey
-1 whitekey
Output 
1 1
1 1
1 1
1 1

输入样例 复制 

2 2 9
+1 1 1 cola
+1 1 1 fanta
+1 1 1 sevenup
+1 1 1 whitekey
-1 cola
-1 fanta
-1 sevenup
-1 whitekey
-1 cola

输出样例 复制 

1 1
1 2
2 1
2 2
-1 -1

分类标签