Во время проведения соревнований по программированию тестирующая система хранит информацию обо всех отправленных на проверку решениях и автоматически формирует турнирную таблицу, которая показывает, какое место занимает каждый из участников. В этой задаче вам нужно помочь тестирующей системе и самостоятельно составить турнирную таблицу по имеющимся данным.
Тестирующая система хранит информацию о решениях в записях формата Ti Si Pi Ri, где
По данной информации формируется содержание турнирной таблицы в соответствии со следующими правилами:
Форматирование турнирной таблицы осуществляется в соответствии со следующими правилами:
Составьте турнирную таблицу, соблюдая все описанные требования.
Первая строка содержит целые числа N и M (1 ≤ N ≤ 26, 1 ≤ M ≤ 105) — число задач и число отправленных решений.
Следующие N строк описывают решения. Каждая из них содержит число Ti, строку Si, символы Pi и Ri (0 ≤ Ti ≤ 105, 1 ≤ |Si| ≤ 20, 'A' ≤ Pi ≤ 'Z', Pi {'+', '-'}) — время отправки решения, имя участника, отправившего решение, идентификатор задачи и результат проверки.
Имена участников состоят только из строчных латинских букв и знаков подчёркивания. Идентификаторы задач принадлежат множеству первых N заглавных букв латинского алфавита. Строки, описывающие решения, упорядочены в порядке неубывания значений Ti.
Выведите турнирную таблицу, составленную и оформленную в соответствии с правилами (см. примеры).
В системе Contester вы можете перейти к просмотру турнирной таблицы по ссылке, расположенной в левой части страницы с задачей.
## Входные Данные
Первая строка содержит целые числа N и M (1 ≤ N ≤ 26, 1 ≤ M ≤ 105) — число задач и число отправленных решений.Следующие N строк описывают решения. Каждая из них содержит число Ti, строку Si, символы Pi и Ri (0 ≤ Ti ≤ 105, 1 ≤ |Si| ≤ 20, 'A' ≤ Pi ≤ 'Z', Pi {'+', '-'}) — время отправки решения, имя участника, отправившего решение, идентификатор задачи и результат проверки.Имена участников состоят только из строчных латинских букв и знаков подчёркивания. Идентификаторы задач принадлежат множеству первых N заглавных букв латинского алфавита. Строки, описывающие решения, упорядочены в порядке неубывания значений Ti.
## Выходные Данные
Выведите турнирную таблицу, составленную и оформленную в соответствии с правилами (см. примеры).
## Примеры
Входные данные4 2115 rivest A -47 cormen B -52 rivest B +118 stein B -122 cormen A +152 cormen C -267 leiserson B -320 stein D -349 cormen B -366 stein B -366 leiserson C +367 leiserson A +392 rivest A -487 stein D -499 cormen B +567 stein B -599 stein B +617 cormen D +7028 cormen C -9064 rivest A +10026 stein D -Выходные данные################################################################# R # Contestant # A # B # C # D # + # T ################################################################## 1 # cormen # + # +2 # -2 # + # 3 # 1278 ## # # 02:02 # 08:19 # 117:08 # 10:17 # # ################################################################## 2 # leiserson # + # -1 # + # # 2 # 733 ## # # 06:07 # 04:27 # 06:06 # # # ################################################################## 3 # rivest # +2 # + # # # 2 # 9156 ## # # 151:04 # 00:52 # # # # ################################################################## 4 # stein # # +3 # # -3 # 1 # 659 ## # # # 09:59 # # 167:06 # # #################################################################Входные данные2 65 korotkevich A -7 korotkevich B -12 korotkevich A +14 mitrichev A -20 korotkevich B -26 mitrichev A -Выходные данные############################################# R # Contestant # A # B # + # T ############################################## 1 # korotkevich # +1 # -2 # 1 # 32 ## # # 00:12 # 00:20 # # ############################################## # mitrichev # -2 # # 0 # 0 ## # # 00:26 # # # #############################################
## Примечание
В системе Contester вы можете перейти к просмотру турнирной таблицы по ссылке, расположенной в левой части страницы с задачей.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of operations.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i < 0 $ denotes a purchase (cash outflow) and $ a_i > 0 $ denotes a sale (cash inflow).
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ -10^6 \leq a_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Find the minimum initial capital $ C \geq 0 $ such that the cumulative sum after each operation never becomes negative:
$$
C + \sum_{j=1}^i a_j \geq 0 \quad \forall i \in \{1, \dots, n\}
$$
Equivalently,
$$
C \geq -\min_{1 \leq i \leq n} \left( \sum_{j=1}^i a_j \right)
$$
Thus, the minimal initial capital is:
$$
C = \max\left(0, -\min_{1 \leq i \leq n} S_i \right), \quad \text{where } S_i = \sum_{j=1}^i a_j
$$