8. Тяп-ляп, фигак, в релиз!

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

Первая строка содержит два целых числа $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$.

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

• После первого запроса множество строк равно $\{$\texttt{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.