← 返回题目列表

Codeforces · 1819/F

F. 无论愿意与否,破解,发布!

中文机器翻译题面 查看原题

你一直梦想着在一家大型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$$$ 的选择取决于您。

输入

第一行包含两个整数 $$$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$$$。

示例

输入 #1

2 4
aa
ac
dd
ac

输出 #1

2 12
4 4
-1
12 12

输入 #2

3 2
acc
bdd

输出 #2

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。