MapCraft

MapCraft
--------
TiOm4eG очень любит играть в популярную игру "MapCraft". Основной механикой этой игры является создание предметов (крафт). Чтобы создать предмет, нужно выложить предметы, необходимые для его создания, на сетку 3x3.
У TiOm4eG установлена модификация, позволяющая получать доступ ко всем предметам из специального терминала, не храня их у себя в инвентаре. Этот терминал может как принимать предметы, так и мгновенно создавать новые (если необходимые ресурсы есть в терминале, конечно же). Этот терминал можно редактировать для своих нужд, например, задавать новые инструкции.
Помимо игры в MapCraft, TiOm4eG обожает статистику. Поэтому ему стало интересно узнать значение некоторой функции для каждого предмета.
Пусть значение функции craft(item, x) равно количеству предметов item, которое можно создать после x запросов к терминалу.
Сейчас терминал знает набор рецептов R, состоящий из N различных рецептов, во всех этих рецептах участвует M различных предметов. Перед запросами в терминале находилось C различных предметов в каком-то количестве. Для всех рецептов R[i] вычислите craft(R[i], 0) + craft(R[i], 1) +...+ craft(R[i], Q), где Q - количество запросов к терминалу.
--------
Формат входных данных:
В первой строке вводятся N, M, C, Q (1 <= N, M, C, Q <= 10000).
В следующих 4N строках вводится список рецептов R в следующем виде:
На первой строке вводится название рецепта.
На следующих трёх строках вводится матрица 3x3, которая задаёт рецепт предмета. Если в какой-то ячейке матрицы хранится строка "empty", то для создания в этой ячейке не должно ничего лежать.
На следующих C строках вводятся (item, value), где item - название предмета, value - количество единиц этого предмета в терминале перед запросами.
После этого в Q строках задаются запросы вида (type, item, value):
Если type = "craft", то терминал создаёт value копий рецепта item, затрачивая необходимые ресурсы.
Если type = "add", то в терминал добавляется value копий предмета item.
Всё названия предметов - строки, состоящие из строчных латинских букв, и имеющие длину не более 20 символов.
Гарантируется, что для одного предмета может быть не больше одного рецепта.
Гарантируется, что каждый запрос "craft" валиден.
Гарантируется, что каждый предмет участвует в создании не более, чем 100 различных предметов.
--------
Формат выходных данных:
В следующих N строках выведите craft(R[i], 0) +... + craft(R[i], Q).
--------
Пример:
--------
mapcraft.in
2 3 2 5
rocketfuel
petrol petrol petrol
empty empty empty
petrol petrol petrol
rocket
ironplate ironplate ironplate
ironplate rocketfuel ironplate
ironplate rocketfuel ironplate
petrol 12
ironplate 1000000
add petrol 5
craft rocketfuel 2
add petrol 1
craft rocketfuel 1
craft rocket 1
--------
mapcraft.out
5
3
--------
Пояснение:
craft(rocketfuel, 0) = 2, craft(rocketfuel, 1) = 2, craft(rocketfuel, 2) = 0, craft(rocketfuel, 3) = 1, craft(rocketfuel, 4) = 0, craft(rocketfuel, 5) = 0.
craft(rocket, 0) = 0, craft(rocket, 1) = 0, craft(rocket, 2) = 1, craft(rocket, 3) = 1, craft(rocket, 4) = 1, craft(rocket, 5) = 0.
--------
Ограничения:
TL - 1500 ms
ML - 256 MB