Задача . B. Склад

В старые времена, когда мир был красивее, солнце светило ярче, трава была зеленее, а колбаса была вкуснее, самым могущественным государством была страна Арляндия. В ее столице и работал наш герой ДравДэ. Он не умел писать программы, придумывать задачи (вообще в те времена редкие люди видели компьютеры вживую), но наш герой и так неплохо жил — он работал на складе с волшебным, но безалкогольным напитком Огудар-Олок. Мы не будем вдаваться в подробности его профессии, но в данной задаче рассмотрим упрощенную модель склада.

Пусть наш склад состоит из одного стеллажа. Сам стеллаж состоит из n полок, каждая из которых разделена на m ячеек. Полки нумеруются сверху вниз начиная с 1, а ячейки в каждой полке — слева направо, также начиная с 1. В каждую ячейку помещается ровно один ящик напитка, и ДравДэ, даже при всем своем желании, не сможет положить туда еще ящик, если ячейка уже занята. В процессе своей работы ДравДэ нередко замечает, что требуется положить ящик в ячейку, когда там уже что-то лежит. В этом случае ДравДэ делает очень просто: он не трогает эту занятую ячейку, а смотрит на следующую справа от нее. Если она свободна — то место под ящик найдено, и он ставит его туда; иначе он смотрит дальше и ищет первую свободную ячейку справа. Если до конца этой полки не найдется ни одного свободного места, то он начинает рассматривать полку, которая находится под текущей, а потом следующую и т. д. При этом, каждый раз при переходе на новую полку поиск места начинается с ее начала. Если ДравДэ так и не смог найти свободного места для ящика, то он, не медля ни секунды, прямо на рабочем месте выпивает весь напиток из него, а пустую тару выкидывает, таким образом пряча все следы своего преступления.

Однажды, после бурного застолья с напитком Огудар-Олок, ДравДэ попросил вас помочь ему. В отличие от него, вы умеете писать программы, и поэтому вам не составит никакой сложности промоделировать процесс учета ящиков на складе.

Процесс учета состоит из запросов двух видов:

• «+1 x y id» (где x, y — это целые числа, 1 ≤ x ≤ n, 1 ≤ y ≤ m, а id — строка из строчных латинских букв длиной от 1 до 10 символов). Этот запрос означает, что на склад поступил ящик с идентификатором id, который нужно положить на полку номер x в ячейку номер y. Если эта ячейка уже занята, используйте правила, описанные выше. Гарантируется, что в любой момент времени описываемого процесса идентификаторы всех ящиков, присутствующих на складе в данный момент, различны. На этот запрос не нужно отвечать.
• «-1 id» (где id — строка из строчных латинских букв длиной от 1 до 10 символов). Этот запрос означает, что со склада нужно изъять ящик с идентификатором id. На этот запрос нужно вывести ответ (см. формат выходных данных).