Евлампий и его одногруппник Никанор вместе готовятся к экзамену.
Они собираются решить $$$n$$$ задач. Задачи занумерованы от $$$1$$$ до $$$n$$$, и решать их одногруппники будут в порядке нумерации.
Для каждой задачи $$$\#j$$$ известно время $$$t_j$$$, которое потратит на её решение Евлампий, и время $$$s_j$$$, которое потратит на её решение Никанор. Также для каждого из одногруппников известно, решил ли он задачу $$$\#j$$$ правильно или нет.
Евлампий и Никанор планируют действовать так.
Они оба одновременно начинают решать первую задачу. Если тот, кто решил её первым, решил её правильно, то его товарищ прекращает решать эту задачу, и они одновременно начинают решать вторую задачу. Если же решивший задачу первым решил её неправильно, то он приступает к решению второй задачи, а его товарищ дописывает своё решение в надежде, что оно окажется верным.
Далее всё происходит похожим образом. Тот, кто решил некоторую задачу первым и решил её правильно, сразу же сообщает об этом товарищу. В этом случае товарищ либо прекращает решать эту задачу, либо не будет приступать к ней, если ещё не начал её решать.
Ваша задача — определить, через сколько времени одногруппники завершат решение задач (правильно или неправильно — это уж как получится), а также посчитать, сколько правильных решений будет на счету Евлампия, а сколько — на счету Никанора.
Примечание. Если Евлампий и Никанор одновременно завершают решение задачи, и у обоих это решение правильное, то это решение следует учитывать при подсчёте решений для обоих.
Ещё одно примечание. На рисунке показано, как Евлампий и Никанор решали задачи в примере входных данных.
И ещё одно примечание. На всякий случай: использование массивов или иных структур данных в этой задаче не предполагается.
В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество задач.
В каждой из следующих $$$n$$$ строк содержится запись из двух пар (число, символ) вида $$$t_j$$$, $$$a_j$$$, $$$s_j$$$, $$$b_j$$$ $$$(1 \le t_j, \, s_j \le 10^6, \, a_j, \, b_j \in \{A, R\})$$$, где $$$t_j$$$ — время, которое потребуется Евлампию, чтобы решить задачу $$$\#j$$$, $$$s_j$$$ — время, которое потребуется Никанору, чтобы решить задачу $$$\#j$$$, $$$a_j$$$ — символ $$$A$$$, если Евлампий правильно решит задачу $$$\#j$$$ и $$$R$$$, если неправильно; $$$b_j$$$ — символ $$$A$$$, если Никанор правильно решит задачу $$$\#j$$$ и $$$R$$$ — если неправильно.
Выведите три целых числа — время, спустя которое одногруппники завершат решение задач, количество правильных решений Евлампия и количество правильных решений Никанора.
103 R 5 A2 R 6 R4 A 2 A3 R 4 A6 R 1 A7 A 2 R3 A 4 R3 A 2 A4 A 6 A2 R 3 R
33 4 5
Поясним приведённый пример.
Евлампий неправильно решает задачу $$$\#1$$$ за 3 единицы времени, Никанор — тоже неправильно, но за 5 единиц времени.
В момент времени 3 Евлампий приступает к решению задачи $$$\#2$$$, тратит на это 2 единицы времени, однако решает её неправильно. К этому моменту Никанор только ещё дорешал первую задачу.
В момент времени 5 Евлампий начинает решать задачу $$$\#3$$$, а Никанор начинает заниматься задачей $$$\#2$$$ — поскольку эту задачу Евлампий тоже решил неправильно.
В момент времени 9 у Евлампия имеется правильно решённая задача $$$\#3$$$ (первая правильная), и он начинает заниматься задачей $$$\#4$$$ (на нёё ему нужно 3 единицы времени), а Никанор пока продолжает решать задачу $$$\#2$$$ (ему осталось 2 единицы времени до завершения).
В момент времени 11 Никанор, наконец, заканчивает заниматься задачей $$$\#2$$$, которую, впрочем, он так и не смог решить правильно. Он обнаруживает, что задача $$$\#3$$$ уже правильно решена Евлампием, поэтому пропускает её (заметим, что он мог бы решить её правильно, но смысла в этом уже не видит). Результата по задаче $$$\#4$$$ от Евлампия пока никакого нет, так что Никанор приступает именно к этой задаче.
В момент времени 12 Евлампий заканчивает неправильное решение задачи $$$\#4$$$ (поэтому Никанор продолжает бороться с этой задачей ещё 3 единицы времени) и начинает решать задачу $$$\#5$$$, на которую ему потребуется 6 единиц времени.
В момент времени 15 Никанор правильно решает задачу $$$\#4$$$ (первая правильная у него), и начинает заниматься задачей $$$\#5$$$ (Евлампию для её завершения требуется ещё 3 единицы времени).
В момент времени 16 Никанор правильно решает задачу $$$\#5$$$ (вторая правильная у него), и сообщает об этом Евлампию. Евлампий прекращает заниматься задачей $$$\#5$$$ и они оба одновременно приступают к решению задачи $$$\#6$$$.
В момент времени 18 у Никанора появляется неправильное решение задачи $$$\#6$$$, так что Евлампий продолжает решать эту задачу (ему нужно ещё 5 единиц времени). А Никанор приступает к задаче $$$\#7$$$.
В момент времени 22 Никанор заканчивает неправильное решение задачи $$$\#7$$$ и начинает заниматься задачей $$$\#8$$$.
В момент времени 23 у Евлампия получается правильно решить задачу $$$\#6$$$ (вторая правильная для Евлампия), а Никанору нужно ещё 1 единицу времени для решения задачи $$$\#8$$$. Евлампий же начинает решать задачу $$$\#7$$$, так как Никанор с ней не справился.
В момент времени 24 Никанор правильно решает задачу $$$\#8$$$ (третья, решённая правильно) и начинает заниматься задачей $$$\#9$$$ (на её решение ему потребуется 6 единиц времени).
В момент времени 26 Евлампий, наконец, правильно решает задачу $$$\#7$$$ (третья, решённая правильно Евлампием), однако задачу $$$\#8$$$ (которую он тоже мог бы решить правильно) он пропускает, поскольку Никанор её уже решил правильно. Что касается задачи $$$\#9$$$, Никанор ещё не завершил её решение, так что Евлампий начинает тоже ею заниматься.
В момент времени 30 и Евлампий, и Никанор одновременно заканчивают решение задачи $$$\#9$$$. Для обоих она становится четвёртой, решённой правильно. Теперь оба одновременно приступают к решению задачи $$$\#10$$$.
В момент времени 32 Евлампий заканчивает решение задачи $$$\#10$$$, однако оно неправильное. Поэтому Никанор продолжает работу над этой задачей.
В момент времени 33 Никанор завершает решение задачи $$$\#10$$$, оно, к сожалению, тоже неправильное. Но в этот момент решение задач следует считать завершённым.
