CF1819F.Willy-nilly, Crack, Into Release!

You have long dreamed of working in a large IT company and finally got a job there. You have studied all existing modern technologies for a long time and are ready to apply all your knowledge in practice. But then you sit down at your desk and see a sheet of paper with the company's motto printed in large letters: abcdabcdabcdabcd....

The company's motto contains four main principles— a (Willi), b (Nilli), c (Crack), d (Release). Therefore, you consider strings of length $n$ consisting of these four Latin letters. Unordered pairs of letters "ab", "bc", "cd", and "da" in this motto are adjacent, so we will call such pairs of symbols good. So, if you are given a string $s$ of length $n$, and it is known that the unordered pair of symbols ${ x, y }$ is good, then you can perform one of the following operations on the string:

• if $s_n = x$, then you are allowed to replace this symbol with $y$,
• if there exists $1 \le i \lt n$ such that $s_i = x$ and $s_{i+1} = \ldots = s_n = y$, then you are allowed to replace the $i$-th symbol of the string with $y$, and all subsequent symbols with $x$.

For example, the string bacdd can be replaced with one of the strings bacda, bacdc, or badcc, and the string aac can be replaced with aab or aad.

A non-empty sequence of operations for the string $s$ will be called correct if the following two conditions are met:

1. after performing all operations, the string becomes $s$ again,
2. no string, except for $s$, will occur more than once during the operations. At the same time, the string $s$ can occur exactly twice - before the start of the operations and after performing all operations.

Now we are ready to move on to the problem statement! You have a set of strings that is initially empty. Then, each of $q$ queries adds another string $t_i$ to the set, or removes the string $t_i$ from the set. After each query, you need to output the minimum and maximum size of a correct sequence of operations in which each word occurs at least once. The choice of the initial string $s$ is up to you.

你一直梦想着在一家大型IT公司工作，如今终于如愿以偿。你长期钻研所有现有的前沿技术，已准备好将所学知识付诸实践。然而，当你坐到工位上时，却看到一张纸上印着公司口号，以醒目的大号字体写着：abcdabcdabcdabcd...。

该公司的口号蕴含四大核心原则——a（Willi）、b（Nilli）、c（Crack）、d（Release）。因此，你考虑由这四个拉丁字母组成的长度为 $n$ 的字符串。口号中无序对 "ab"、"bc"、"cd" 和 "da" 相邻出现，我们称此类符号对为好对。于是，若给定一个长度为 $n$ 的字符串 $s$，且已知无序符号对 $\{ 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$ 可由你自由选择。

The first line contains two integers $n$ and $q$ ($1 \le n \le 20$, $1 \le q \le 100\,000$) — the length of the strings under consideration and the number of queries to modify the set of strings.

Each of the next $q$ lines contains a string $t_i$ ($\lvert t_i \rvert = n$). All strings consist of characters "a", "b", "c" and "d". If the string $t_i$ was not in the set before the query, it is added to the set, otherwise it is removed from the set.

第一行包含两个整数 $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$ 在本次查询前不在集合中，则将其加入集合；否则，将其从集合中移除。

For each of the $q$ queries, output two integers: the minimum and maximum size of a correct sequence of operations in which each word from the set appears at least once.

If there is no sequence of operations that satisfies the condition of the problem, output a single number $-1$.

对于每个查询，输出两个整数：满足条件的正确操作序列的最小长度和最大长度，其中集合中的每个单词至少出现一次。

若不存在满足题目条件的操作序列，则输出单个数字 $-1$。

Let's consider the first test example.

• After the first query, the set of important words is equal to {aa}, the minimum sequence of actions has the following form: aa, ab, aa. The maximum sequence of actions that fits is aa, ab, ba, bb, bc, cb, cc, cd, dc, dd, da, ad, aa.
• After the second query, the set of important words is equal to {aa, ac}. The minimum and maximum sequences of actions are: aa, ab, ac, ad, aa.
• After the third query, the set of important words is equal to {aa, ac, dd}. There is no sequence of actions that fits the condition, so $-1$ should be outputted.
• After the fourth query, the set of important words is equal to {aa, dd}. The minimum and maximum sequences of actions are as follows: aa, ab, ba, bb, bc, cb, cc, cd, dc, dd, da, ad, aa.

我们来考虑第一个测试样例。

• 第一次查询后，重要单词集合为 $\{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。