G. Бум
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
input.txt
вывод
output.txt

Рассмотрим известную игру Бум (aka Шляпа) с упрощенными правилами.

В игре участвуют n команд по два человека. Цель игры: объяснить слова своему напарнику, не используя однокоренные и созвучные.

Игрок номер j команды с номером i (1 ≤ i ≤ n, 1 ≤ j ≤ 2) характеризуется двумя числами: aij и bij. Числа обозначают соответственно навык объяснения и навык понимания данного игрока.

Так же для игры используются m карточек. На каждой карточке написано слово. Карточка с номером k (1 ≤ k ≤ m) характеризуется числом ck — сложностью слова, написанного на ней.

Перед началом игры карточки складываются в колоду и перемешиваются. Далее команды делают ходы в следующем порядке: 1-й игрок 1-й команды, 1-й игрок 2-й команды, ... , 1-й игрок n-ой команды, 2-й игрок 1-й команды, ... , 2-й игрок n-й команды, 1-й игрок 1-й команды и т.д.

Каждый ход длится t секунд. Ход производится следующим образом: изначально время хода равно t. Пока время хода больше 0, ходящий игрок берет верхнюю карточку из колоды и начинает объяснять слово на ней своему напарнику. Время, за которое j-й игрок i-й команды объяснит слово с карточки k своему напарнику (q-му игроку i-й команды) равно max(1, ck - (aij + biq) - dik) (если j = 1,  то q = 2,  иначе q = 1). Величина dik — это количество секунд, которое i-я команда уже потратила на объяснение слова k за предыдущие ходы. Изначально, все dik равны 0. Если команда успевает до конца хода отгадать слово, то из времени хода вычитается указанное выше время, отгаданная карточка выходит из игры, принося команде одно очко, и ход продолжается. Если же команда не успевает отгадать слово, то карточка кладется вниз колоды, а dik увеличивается на время хода, потраченное на объяснение этого слова на текущем ходу. Таким образом, когда этой команде достанется это же слово, они начнут его объяснять не с начала, а с того места, на котором остановились. Игра заканчивается тогда, когда все m карточек отгаданы.

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

Входные данные

В первой строке содержатся два целых числа n, t (1 ≤ n, t ≤ 100), обозначающие соответственно количество команд и продолжительность одного хода.

В следующих n строках входного файла содержатся по четыре целых числа: ai1, bi1, ai2, bi2 (1 ≤ aij, bij ≤ 100) — навыки первого и второго игроков i-й команды. Команды заданы в том порядке, в котором они ходят.

В следующей строке входного файла содержится целое число m (1 ≤ m ≤ 100) — число карточек.

В следующих 2m строках содержится описания карточек. Каждая карточка описывается двумя строками. В первой строке описания карточки содержится слово, состоящее не более, чем из 20 символов. Слова содержат только строчные буквы латинского алфавита. Во второй строке описания карточки содержится целое число ck (1 ≤ ck ≤ 100) — сложность слова, написанного на k-й карточке. Карточки перечислены в том порядке, в котором они лежат в колоде сверху вниз. Слова на всех карточках различны.

Выходные данные

Выведите n строк. В i-й строке сначала выведите число si — количество очков, заработанных i-й командой. Далее выведите si слов, разделяя их пробелами, — слова с карточек, отгаданных командой i в том порядке, в котором они были отгаданы.

Примеры
Входные данные
2 2
1 1 1 1
1 1 1 1
3
home
1
car
1
brother
1
Выходные данные
2 home car 
1 brother
Входные данные
2 4
1 2 2 1
2 3 2 2
4
armchair
3
quetzalcoatl
10
pilotage
5
defibrillator
7
Выходные данные
2 armchair quetzalcoatl 
2 pilotage defibrillator