F. Тяп-ляп, кряк, в релиз!
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вы долго об этом мечтали и наконец устроились работать в крупную 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$$$ будем называть корректной, если выполняются следующие два условия:

  1. после совершения всех операций снова получится строка $$$s$$$,
  2. никакая строка, кроме $$$s$$$, в ходе совершения операций не возникнет более одного раза. При этом строка $$$s$$$ должна возникнуть ровно два раза — перед началом выполнения операций и после выполнения всех операций.

Теперь мы готовы перейти к условию задачи! У вас есть множество строк, которое изначально пусто. Далее $$$q$$$ раз в множество добавится очередная строка $$$t_i$$$, либо строка $$$t_i$$$ удаляется из множества. После каждого запроса требуется вывести минимальный и максимальный размер корректной последовательности операций, в ходе которой каждое слово возникает хотя бы один раз. Выбор начальной строки $$$s$$$ остается за вами.

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 20$$$, $$$1 \le q \le 100\,000$$$) — длина рассматриваемых строк и количество запросов изменения множества строк.

Каждая из следующих $$$q$$$ строк содержит строку $$$t_i$$$ ($$$\lvert t_i \rvert = n$$$). Все строки состоят из символов «a», «b», «c» и «d». Если до этого запроса строка $$$t_i$$$ не находилась в множестве, то она добавляется в него, а иначе она удаляется из множества.

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

Для каждого из $$$q$$$ запросов выведите два целых числа — минимальный и максимальный размер корректной последовательности операций, в ходе которой каждое слово из множества возникает хотя бы один раз.

Если не существует ни одной последовательности операций, удовлетворяющей условию задачи, выведите одно число $$$-1$$$.

Примеры
Входные данные
2 4
aa
ac
dd
ac
Выходные данные
2 12
4 4
-1
12 12
Входные данные
3 2
acc
bdd
Выходные данные
2 44
28 44
Примечание

Рассмотрим первый пример.

  • После первого запроса множество строк равно $$$\{$$$aa$$$\}$$$, минимальная последовательность действий имеет следующий вид: aa, ab, aa. В качестве максимальной последовательности действий подходит aa, ab, ba, bb, bc, cb, cc, cd, dc, dd, da, ad, aa.
  • После второго запроса множество строк равно $$$\{$$$aa, ac$$$\}$$$. Минимальная и максимальная последовательности действий: aa, ab, ac, ad, aa.
  • После третьего запроса множество строк равно $$$\{$$$aa, ac, dd$$$\}$$$. Не существует последовательности действий, которая подходит под условие, поэтому следует вывести $$$-1$$$.
  • После четвертого запроса множество строк равно $$$\{$$$aa, dd$$$\}$$$. Минимальная и максимальная последовательности действий таковы: aa, ab, ba, bb, bc, cb, cc, cd, dc, dd, da, ad, aa.