Codeforces Round 866 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Willy-nilly, Crack, Into Release!

time limit per test

3 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputYou 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:

- after performing all operations, the string becomes $$$s$$$ again,
- 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

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

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

Examples

Input

2 4 aa ac dd ac

Output

2 12 4 4 -1 12 12

Input

3 2 acc bdd

Output

2 44 28 44

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:49:38 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|