Задача J. Логика В.О. Ключевского ≡

Условие

"Когда дурак начинает считать себя остроумным, количество остроумных людей не увеличивается; когда умный человек признает себя остроумным, всегда становится одним умным меньше и иногда одним остроумным больше; когда остроумный начинает считать себя умным, всегда одним остроумным становится меньше и никогда не бывает одним умным больше."

(В.О. Ключевский "Афоризмы и мысли об истории")

Введём множество I = {О, У, Д}. Положим D ⊂ I × I равным D = {(Д, О), (У, О), (О, У)}. Определим на множестве D многозначные функции Ключевского K_Y(a, b), K_O(a, b), значения которых равны множеству возможных приращений количеств умных и остроумных людей соответственно, если "a считает себя b".

Дано N пар (a_i, b_i) ∈ D. Определить нижнюю и верхнюю границы сумм N∑i = 1K_Y(a_i, b_i) и N∑i = 1K_O(a_i, b_i).

Формат входного файла

Входной файл содержит целое число N. Далее следуют N пар целых чисел A_i B_i. Таблица соответствия: О — 0, У — 1, Д — 2.

Формат выходного файла

Выходной файл должен содержать 4 числа: m_Y M_Y m_O M_O.

Ограничения

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

1
1 0

-1 -1   0 1

3
0 1
2 0
1 0

-1 -1   -1 0

Разбор

K_Y(Д, О) = 0, K_O(Д, О) = 0
K_Y(У, О) =  − 1, K_O(У, О) = {0, 1}
K_Y(О, У) = 0, K_O(О, У) =  − 1

Пусть (a, b) ∈ D. Обозначим через C(a, b) количество индексов i, для которых (a_i, b_i) = (a, b). Тогда
∑K_Y(a_i, b_i) =  − C(У, О),
 − C(О, У) ≤ ∑K_O(a_i, b_i) ≤ C(У, О) − C(О, У).