Вы долго об этом мечтали и наконец устроились работать в крупную IT-компанию. Вы долго-долго учились всем существующим современным технологиям и уже готовы применить все свои знания на практике. Но тут вы садитесь за свой рабочий стол и видите лист с распечатанным крупными буквами девизом компании: abcdabcdabcdabcd....
В девизе компании указаны четыре главных принципа — a (Тяп), b (Ляп), c (Кряк), d (Релиз). Поэтому вы рассматриваете строки длины \(n\), состоящие из указанных четырех букв латинского алфавита. Неупорядоченные пары букв «ab», «bc», «cd» и «da» в этом девизе соседние, поэтому будем называть такие пары символов хорошими. Итак, если вам дана строка \(s\) длины \(n\), и известно, что неупорядоченная пара символов \(\{ x, y \}\) хорошая, то со строкой можно совершить одну из указанных операций:
- если \(s_n = x\), то разрешается заменить этот символ на \(y\),
- если существует такое \(1 \le i < n\), что \(s_i = x\) и \(s_{i+1} = \ldots = s_n = y\), то разрешается заменить \(i\)-й символ строки на \(y\), а все последующие — на \(x\).
Например, строку bacdd можно заменить на одну из строк bacda, bacdc или badcc, а строку aac можно заменить на aab или aad.
Непустую последовательность операций для строки \(s\) будем называть корректной, если выполняются следующие два условия:
- после совершения всех операций снова получится строка \(s\),
- никакая строка, кроме \(s\), в ходе совершения операций не возникнет более одного раза. При этом строка \(s\) должна возникнуть ровно два раза — перед началом выполнения операций и после выполнения всех операций.
Теперь мы готовы перейти к условию задачи! У вас есть множество строк, которое изначально пусто. Далее \(q\) раз в множество добавится очередная строка \(t_i\), либо строка \(t_i\) удаляется из множества. После каждого запроса требуется вывести минимальный и максимальный размер корректной последовательности операций, в ходе которой каждое слово возникает хотя бы один раз. Выбор начальной строки \(s\) остается за вами.
Выходные данные
Для каждого из \(q\) запросов выведите два целых числа — минимальный и максимальный размер корректной последовательности операций, в ходе которой каждое слово из множества возникает хотя бы один раз.
Если не существует ни одной последовательности операций, удовлетворяющей условию задачи, выведите одно число \(-1\).