曾几何时,世界更美丽,阳光更明亮,草更绿,香肠味道更好,阿兰迪亚是最强大的国家。它的首都是我们的英雄DravDe工作的地方。他不会编程或编造问题(事实上,当时很少有人看到计算机),但他仍然很高兴。他在一个仓库工作,那里存放着一种神奇但不含酒精的饮料 Ogudar-Olok。我们不会详细描述他的工作,而是更好地了解仓库的简化版本。
仓库有货架一套。它有 n 个架子,每个架子分为 m 个部分。架子从上到下从 1 开始编号,每个架子的部分从左到右也从 1 开始编号。每个部分只能容纳一盒饮料,无论 DravDe 怎样尝试,他都无法将盒子放入已经有饮料的部分中。在工作过程中,DravDe 经常注意到他必须在已填充的区域中放置一个框。在这种情况下,他的解决方案很简单。 DravDe 忽略该部分并查看右侧的下一个部分。如果它是空的,他就把盒子放在那里。否则,他会继续寻找右侧的第一个空部分。如果在架子末端没有找到空的部分,他会查看其下方的架子,然后是下一个,依此类推。而且,每次他查看新的架子时,他都会从架子的开头开始。如果DravDe仍然找不到盒子的空部分,他会立即喝光所有瓶子,并将空瓶子扔掉以免被发现。
在一场盛大的聚会后,很多 Ogudar-Olok 喝醉了的 DravDe 请求你帮助他。与他不同的是,您可以进行编程,因此对仓库中箱子的计数过程进行建模对您来说将是一件容易的事。
计数过程中包含两类查询消息:
- «+1 x y id»(其中 x、y 是整数,1 ≤ x ≤ n、1 ≤ y ≤ m,id 是小写拉丁字母字符串 — 长度为 1 到 10 个字符)。该查询意味着仓库有一个标识为 id 的盒子,该盒子应放入货架 x 上的 y 部分。如果该部分已满,请使用上述规则。确保过程中的每个时刻仓库中所有箱子的标识符都是不同的。您不必回答此查询。
- «-1 id»(其中 id 是一串小写拉丁字母 — 长度为 1 到 10 个字符)。该查询意味着标识为 id 的盒子已从仓库中删除。您必须回答此查询(请参阅输出格式)。
输入
第一输入行包含整数 n、m 和 k (1 ≤ n, m ≤ 30, 1 ≤ k ≤ 2000) — 货架的高度、宽度以及仓库中需要分析的操作量。在接下来的 k 行中,查询按照上述格式的出现顺序给出。
输出
对于“-1 id”类型的每个查询,在单独的行中输出两个数字 - 货架索引和具有该标识符的盒子所在部分的索引。如果查询时仓库中没有这个盒子,则输出“-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 1 2 2 1 2 2 -1 -1
输入 #2
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
输出 #2
1 1 1 1 1 1 1 1