E. Итоговые места
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Директор чемпионата Артём постоянно улучшает тестирующую систему, делая её стабильнее, эффективнее и комфортнее.

На этот раз Артём модернизировал систему сортировки команд в таблице результатов. Для тестирования своей модификации Артём решил прогнать её на результатах одного из предыдущих чемпионатов.

Но обнаружилась проблема — у Артёма сохранился только лог посылок, но не сохранилось итогового ранжирования команд.

Помогите Артёму — по имеющейся информации о посылках команд вычислите итоговые результаты команд и их места.

Правила сортировки команд и определения мест

  • В первую очередь команды сортируются в порядке убывания количества правильно решённых задач.
  • При равенстве решённых задач команды сортируются в порядке возрастания суммарного штрафного времени:
    • Пусть команда сдала правильно задачу через $$$M$$$ минут после начала соревнования, до этого сделав по данной задаче ровно $$$F$$$ штрафных попыток.
    • В таком случае команде начислится $$$(M + 20 \cdot F)$$$ штрафного времени за решение этой задачи.
    • Последующие попытки по уже сданной задаче не изменяют штрафное время.
    • Если какая-либо задача не сдана — то штраф по ней не начисляется вне зависимости от количества попыток.
  • При равенстве и количества решённых задач, и суммарного штрафного времени команды делят одно и то же место.
    • Для удобства такие команды сортируются в таблице в порядке возрастания их идентификаторов.
Входные данные

В первой строке через пробел даны два целых числа $$$n$$$ и $$$p$$$ $$$(1 \le n \le 10^3; 1 \le p \le 20)$$$ — количество команд и количество задач на соревновании.

Во второй строке дано целое число $$$q$$$ $$$(1 \le q \le 10^5)$$$ — количество записей о посылках в логе.

В $$$j$$$-й из следующих $$$q$$$ строк содержится информация о $$$j$$$-й посылке в системе — через пробел даны четыре целых числа $$$M_j$$$, $$$ID_j$$$, $$$T_j$$$ и $$$V_j$$$:

  • $$$M_j$$$ $$$(1 \le M_j \le 300)$$$ — минута, на которой совершена посылка;
  • $$$ID_j$$$ $$$(1 \le ID_j \le n)$$$ — идентификатор команды, сделавшей посылку;
  • $$$T_j$$$ $$$(1 \le T_j \le p)$$$ — номер задачи, по которой сделана посылка;
  • $$$V_j$$$ $$$(0 \le V_j \le 1)$$$ — результат тестирования посылки ($$$1$$$ обозначает успех, $$$0$$$ — неудачу).

Гарантируется, что посылки в логе упорядочены в хронологическом порядке, то есть $$$M_j \le M_{j + 1}$$$ для всех $$$1 \le j \lt q$$$.

В том числе это означает, что даже при равенстве $$$M_j = M_{j + 1}$$$ необходимо считать, что $$$j$$$-я посылка произошла раньше, чем $$$(j + 1)$$$-я.

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

В $$$i$$$-й из $$$n$$$ строк выведите через пробел четыре целых числа $$$R_i$$$, $$$ID_i$$$, $$$S_i$$$, $$$X_i$$$:

  • $$$R_i$$$ $$$(1 \le R_i \le n)$$$ — итоговое место команды на $$$i$$$-й строке таблицы;
  • $$$ID_i$$$ $$$(1 \le ID_i \le n)$$$ — идентификатор команды;
  • $$$S_i$$$ $$$(0 \le S_i \le p)$$$ — количество решённых задач командой;
  • $$$X_i$$$ $$$(0 \le X_i \le 10^9)$$$ — суммарное штрафное время команды.
Пример
Входные данные
5 3
23
15 1 1 0
30 2 2 0
30 1 1 1
43 3 1 0
43 2 1 1
65 3 1 0
80 3 2 0
87 3 1 1
99 2 2 1
99 5 2 0
100 1 2 0
100 4 1 0
130 1 2 0
130 5 2 1
130 2 3 0
135 5 2 0
140 5 3 1
199 2 3 0
200 4 3 0
200 1 2 1
280 4 2 0
290 2 3 0
299 2 3 1
Выходные данные
1 2 3 521
2 1 2 290
2 5 2 290
4 3 1 127
5 4 0 0
Примечание

Первый тестовый пример

Всего в соревновании участвовало $$$5$$$ команд, для решения были доступны $$$3$$$ задачи.

  • Команда $$$1$$$:
    • сдала задачу $$$1$$$ в момент времени $$$30$$$, сделав перед этим по ней одну штрафную попытку — получила $$$50$$$ минут штрафа.
    • сдала задачу $$$3$$$ в момент времени $$$200$$$, сделав перед этим по ней две штрафные попытки — получила $$$240$$$ минут штрафа.
  • Команда $$$2$$$:
    • сдала задачу $$$1$$$ в момент времени $$$43$$$ без штрафных попыток — получила $$$43$$$ минуты штрафа.
    • сдала задачу $$$2$$$ в момент времени $$$99$$$ с одной штрафной попыткой — получила $$$119$$$ минут штрафа.
    • сдала задачу $$$3$$$ в момент времени $$$299$$$, сделав перед этим по ней три штрафные попытки — получила $$$359$$$ минут штрафа.
  • Команда $$$3$$$:
    • сдала задачу $$$1$$$ в момент времени $$$87$$$ c двумя штрафными попытками — получила $$$127$$$ минут штрафа.
    • сделала неверную попытку по задаче $$$2$$$, но не сдала её — не получила штрафного времени.
  • Команда $$$4$$$:
    • сделала по каждой задаче по одной неверной попытке, но ничего не сдала — не получила штрафного времени.
  • Команда $$$5$$$:
    • сдала задачу $$$2$$$ в момент времени $$$130$$$, сделав перед этим по ней одну штрафную попытку — получила $$$150$$$ минут штрафа.
    • сдала задачу $$$3$$$ в момент времени $$$140$$$ без штрафных попыток — получила $$$140$$$ минут штрафа.
    • уже после сдачи сделала ещё одну попытку по задаче $$$2$$$ — это не повлияло на её итоговый ранг в таблице.

Итого:

  • Команда $$$2$$$ на первом месте с $$$3$$$ решёнными задачами и $$$521$$$ минутой штрафа.
  • Команда $$$1$$$ на втором месте с $$$2$$$ решёнными задачами и $$$290$$$ минутами штрафа.
  • Команда $$$5$$$ на втором месте с $$$2$$$ решёнными задачами и $$$290$$$ минутами штрафа.
  • Команда $$$3$$$ на четвёртом месте с $$$1$$$ решённой задачей и $$$127$$$ минутами штрафа.
  • Команда $$$4$$$ на пятом месте с $$$0$$$ решёнными задачами и $$$0$$$ минут штрафа.