#214949. [THUPC 2026 初赛] My Mayday

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2026pre 查看。

荒凉的大地上黄沙飞舞弥漫，惨败的信号灯红光无力黯淡。一高一矮的两个人并排走在这一片不应存在的混凝土废墟之中，笼罩在身上的灰色天穹宛如二人内心感情的真实写照。

“你确定是在这附近吗？”特别行动小队 DC-1025 的队长 O 问道。

“应该不会有错。两个人发出的求救信号最后是在这附近消失的。”T 看着手中的设备“COMPASS”的屏幕说道。
DC-1025 原本计划全体出动探察这片废墟，但因 O 和 T 临时收到了紧急任务，S 和 K 二人便先行前往。不料，后辈二人发出了求救信号后就音信杳无。O 和 T 处理完紧急任务后，立刻前往救援，可映入眼帘的只是一片毫无生机的断壁残垣。

“看这个。”眼尖的 T 注意到了一丝闪光，遂蹲下身子，从被沙土淹没的路面上拾起了一块黑色的小塑料片。塑料片上刻有由深蓝色小方块点缀的无衬线字体的图标，它毫无疑问是 DC-1025 专用的存储芯片“Proof”。看起来，这块芯片多半是 S 和 K 留下的；但至于是二人有意为之，还是在遭遇不测时意外掉落，仅凭现场的情况无从推测。

T 轻轻拭去了芯片上的沙尘，把它插进了随身携带的配套设备中。过了几秒钟，设备屏幕上弹出了令人不安的提示：芯片损坏，读取异常。

O 和 T 通过几乎成为废品的芯片中没有损坏的部分勉强读取出了一些二进制信息。

以下是其中一段读取到的二进制信息的示例，其中 . 表示不能准确读取的二进制位：

+--------+------------------------------------------------+
|.00.....|0..10011...........00011....1001................|
|.00.111.|...10100...10101........01110101...10010...01001|
|.00.011.|...10011...00001...11001.......1...............1|
|.00.0...|...................10011...10101...11010...10101|
+--------+------------------------------------------------+

在如上所示的信息格式中，左侧是一个表示当前时间戳的用二进制表示的无符号整数，右侧是记录具体事件内容的字符串。

二人读取到了一段记录了 件事件的日志，日志中每个时间戳都是由 个二进制位表示的整数。由于具体事件内容较难直接恢复，二人打算从还原事件发生的时间点下手。如果事件记录器本身没有出现异常， 件事件应该按发生的先后顺序记录，排在后面的事件的时间戳应该不小于排在前面的时间戳。

现在给定这 个长度为 的破损的二进制时间戳 。O 和 T 想知道日志中第 件事件发生的最早时间，以及在这件事件发生时间最早的前提下，所有可能的时间戳还原方案的总数。

避免故事就此终结，不让灯火就此熄灭。

从标准输入读入数据。

输入的第一行包含两个正整数 和 ，表示事件的数量和时间戳的长度。保证 。

接下来 行，每行包含一个仅由 0、1 或 . 组成的长度为 的字符串 ，表示第 件事件的时间戳，其中 . 表示读取失败的二进制位。

输出到标准输出。

如果存在将所有 中的 . 还原成 0 或 1，使得 个时间戳按不降顺序排列的方案，则输出一个长度为 且仅包含 0 和 1 的字符串和一个非负整数，分别表示所有还原方案中 可能被还原成的最小的时间戳，以及满足要求的还原方案总数对 取模的结果，中间由一个空格隔开。

否则，如果不存在还原方案，则输出 -1。

样例输入 1

3 4
..10
.1.0
...1

样例输出 1

0101 1

样例输入 2

3 4
..1.
.1..
...1

样例输出 2

0101 4

样例输入 3

3 4
111.
011.
0...

样例输出 3

-1

样例输入 4

3 8
.00.111.
.00.011.
.00.0...

样例输出 4

00010110 2

样例输入 5

4 48
0..10011...........00011....1001................
...10100...10101........01110101...10010...01001
...10011...00001...11001.......1...............1
...................10011...10101...11010...10101

样例输出 5

001100110000000100110011000101010001101000010101 270016253

【样例 1 解释】

可以证明，所有满足时间顺序要求的还原方案中， 最小可以被还原成 0101。当 对应 0101 时，只有 种还原方案，其对应时间戳分别为 0010、0100 和 0101。

【样例 2 解释】

此时 可能对应 0010 或 0011，而 可能对应 0100 或 0101，故总共有 种满足要求的还原方案。