题目描述

在火星上，地球历史上最伟大的音乐作品被保存在大型实体数据库中，使现在和未来的火星居民在思念地球文化时能够重新欣赏这些音乐。

这些数据库逐个音调地保存歌曲，因此被称为 Tone Banks。

最近人们发现，当前使用的数据格式在长期暴露于宇宙辐射后可能发生退化，因此必须尽快把所有记录转换为一种新的格式。

数据点与数据块

旧格式是一张二维网格。每个格点的类型为以下两种之一：

• #
• .

这两种类型互为补类型。

如果两个格点在网格中共用一条边，则称它们相邻。因此，坐标为 $(X,Y)$ 的格点与以下格点相邻：

$$(X+1,Y),\ (X-1,Y),\ (X,Y+1),\ (X,Y-1),$$

前提是相应格点位于网格范围内。

相同类型的格点会形成若干数据块。一个数据块是由同一类型格点组成的连通区域，块中的任意两个格点都能仅经过同类型的相邻格点互相到达。

一个数据块的连通区域内部还可能包含若干由补类型格点组成的数据块。这种包围关系可以继续递归下去，并且每一层的数据块类型交替变化。

对于一个数据块，与它至少有一对格点共边相邻的、被它包围的数据块，称为它的内部数据块。

每个数据块包含的内部数据块数量在 $0$ 到 $26$ 之间。

内部数据块的数量决定该数据块表示的英文字母：

• 包含 $1$ 个内部数据块表示 a；
• 包含 $2$ 个内部数据块表示 b；
• $\ldots$
• 包含 $26$ 个内部数据块表示 z。

不包含任何内部数据块的数据块不表示字母，它表示空串。

完整包围条件

一个数据块必须把它的内部数据块完全包围。

设某内部数据块的一个格点为 $(X,Y)$。它不能与该数据块外侧、颜色与内部数据块相同的数据块相邻。

这里的“不相邻”不仅要求不能共边，也要求不能在对角线上相邻。也就是说，它不能与外侧同类型数据块中的以下位置相邻：

$$(X+1,Y+1),\ (X+1,Y-1),\ (X-1,Y+1),\ (X-1,Y-1).$$

同一个外层数据块中的不同内部数据块之间，可以在对角线上相邻。

合法与非法内部数据块示例

歌曲解码

每首歌曲是一串音调，因此可以表示为一个小写英文字母组成的单词。

为了便于定义，认为给定网格之外存在一个无限大的 . 数据块，而在这个无限数据块内部始终恰好包含一个 # 数据块。

解码从这个唯一的 # 数据块开始。

一个数据块表示的字符串由以下部分依次连接而成：

1. 该数据块自身表示的字母；
2. 它的所有内部数据块所表示的字符串。

内部数据块按照其格点坐标的字典序排列：

• 最小行号更小的数据块在前；
• 若最小行号相同，则最小列号更小的数据块在前。

新数据格式使用完全相同的编码规则，但它编码的是旧格式所表示单词的反转。

请把给定记录安全地转换为新格式。

输入格式

第一行包含两个整数 $N,M$：

$$1\le N,M\le100,$$

分别表示旧格式网格的行数和列数。

接下来 $N$ 行，每行包含 $M$ 个字符，每个字符为 # 或 .。

保证输入网格按照上述规则编码了一个非空单词。

输出格式

首先输出两个整数 $K,L$：

$$1\le K,L\le3000,$$

表示新格式网格的行数和列数。

随后输出 $K$ 行，每行包含 $L$ 个字符 # 或 .。

输出网格必须按照上述规则，编码输入单词的反转。

答案不唯一，输出任意一种满足条件的网格即可。

样例 1

输入

7 7
#######
#.....#
#.....#
#.....#
#.....#
#.....#
#######

一种合法输出

3 3
###
#.#
###

第一个样例编码单词 a，反转后仍然是 a。

样例 2

输入

8 29
#############################
#...##........##............#
#.#.##.#..##..##.####...###.#
#.#.##....##..##.####...#.#.#
#...##........##........###.#
#######################.....#
######.................######
#############################

一种合法输出

14 33
#################################
#################################
#####......................######
#####.################.###.######
#####.#...#######..###.#.#.######
#####.#...#####....###.###.######
#####.#.######..#..###.#.#.######
#####.########.....###.###.######
#####........#########.#.#.######
#####..................###.######
#####..................#.#.######
#####..................###.######
###########................######
#################################

第二个样例编码单词 dabba，因此输出编码其反转 abbad。