Willy-nilly, Crack, Into Release!
Contest: Codeforces Round 866 (Div. 1)
Difficulty rating: 3500
Tags: data structures, dp

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 < 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.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

Note:
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.

Example input:
2 4
aa
ac
dd
ac

Example output:
2 12
4 4
-1
12 12

Example input:
3 2
acc
bdd

Example output:
2 44
28 44

Editorial:
There are two ways to approach this problem. Let's start with a solution that does not involve associations with known images. Consider a cyclic sequence of strings that satisfies the condition of the problem. Consider the longest common prefix of all the strings in this sequence. It is not very interesting to us, since by definition it does not change with the operations.
There are two cases. Either the sequence of operations has a length of $$$2$$$, when we perform some action and then immediately "cancel" it with a second action. This case is only possible if there are no more than two important strings in the set. In this case, the required condition can be easily checked in $$$\mathcal{O}(n)$$$ time.
Otherwise, our sequence consists of more than two operations and this is much more like a cycle. Let's say, for example, that the first non-constant character in the sequence of strings initially equals "a". Then after the first change it will be equal to either "b" or "d". Note that after this the first character will no longer be able to immediately turn into "a", since the only way to do this is to "cancel" the operation $$$\ldots acccc\ldots c \to \ldots caaaa\ldots a$$$, but this is only possible in the first case. Thus, the first character will be required to go "around the cycle" $$$abcda$$$. This cycle can be divided into four segments based on the value of the first character of the string. In each of these segments, we are interested in the sequence of operations that transforms the string with the suffix $$$zx\ldots x$$$ into a string that matches the original in the prefix, but its suffix is $$$zy \ldots y$$$, where $$$x \neq y \neq z \neq x$$$ and the pair of characters $$$\{ x,y \}$$$ is "good".
With the help of a not very complicated analysis of cases, we can see that for each prefix we are interested in $$$6$$$ groups of paths that connect strings whose characters, except for the suffix being considered, match, and these paths visit all important strings with the prefix being considered. Within each group of paths, we are interested in the minimum and maximum path, respectively. Note that these values can be easily calculated using dynamic programming. We can calculate all these states in $$$\mathcal{O}(4^n)$$$ time. Then we need to iterate over the length of the common prefix of all the strings and answer the query in $$$\mathcal{O}(n)$$$ time.
So far, we can only calculate the states of interest to us in some galactic time. But this is not entirely scary! Let's say, for example, that when we add or remove one string from the set of important strings, only $$$\mathcal{O}(n)$$$ states change, since only the states responsible for the prefixes of the added/deleted string $$$s$$$ will change. To some extent, this is reminiscent of a segment tree, or rather, a quadtree.
We just need to figure out how to get rid of the $$$\mathcal{O}(4^n)$$$ term in the asymptotic complexity. But this is also simple. Let's notice that if there are no strings with the given prefix in the set of important strings, then the states responsible for this prefix will depend only on the length of the remaining suffix, and all these values can be precomputed in $$$O(n)$$$ time. Thus, we store a trie with strings from the queries, in each node of which we store the state of the dynamic programming, and in case we need the values of the dynamic programming from non-existent trie nodes during recalculation, we can replace them with precomputed values.
Time complexity: $$$\mathcal{O}(nq)$$$.
The author's code is not very complicated, but if you suddenly want to understand it, I warn you that it uses several "hacks" of questionable justification. For example, instead of $$$6$$$ dynamic programming states, only $$$3$$$ really useful ones are stored there. The combinatorial structure MinMaxValue is used to simplify the support of simultaneous maximum and minimum values, and much more. I think that it will be especially useful for beginners to familiarize themselves with how to simplify their lives in implementing combinatorial problems.
Now let's turn to the geometric interpretation of the problem. Imagine a square with a size of $$$(2^n-1) \times (2^n-1)$$$. In its corners, we can draw squares with sizes of $$$(2^{n-1}-1 \times 2^{n-1}-1)$$$ each. Let's say that strings starting with the character $$$a$$$ go to the upper-left square, strings starting with the character $$$b$$$ go to the upper-right, the character $$$c$$$ corresponds to the lower-right corner, and the character $$$d$$$ corresponds to the lower-left. Then we can divide the four resulting squares into four parts each in the same way and divide the strings by corners already by the second character, and so on. In the end, each string is associated with an integer point with coordinates from the interval $$$[0, 2^n-1]$$$. We also have lines from the drawn squares, which are naturally divided into vertical and horizontal segments of length $$$1$$$ each.
This picture is useful because it depicts a graph whose vertices correspond to the strings being considered, and its edges connect pairs of strings that are obtained from each other by means of one move. Thus, looking at the picture, much of the structure of simple cycles in the problem being considered becomes clear and obvious, and with the help of such a picture it is much easier to describe the transitions in the dynamic programming and not get confused.