你一直梦想着在一家大型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。