为了即将到来的节日，矮人国王想要照亮王国的市政厅。市政厅是一个 $N \times N$ 的方格网，所有的方格都必须被照亮。然而，为了节省能源并保护灯笼的魔力，国王希望尽可能少地使用灯笼。他决定将这些灯笼的放置位置限制在网格的主对角线上，即从左上角到右下角的对角线。

这些魔法灯笼是很久以前制作的，具有独特的力量：它们不仅能照亮自身所在的方格，还能以特定的模式投射出长长的光束。也就是说，当放置在某个方格上时，每个灯笼会照亮：

• 其所在行的所有方格，
• 其所在列的所有方格，以及
• 穿过其所在方格的两条对角线上的所有方格。

其中一些灯笼已经被矮人工程师放置好，固定在地面上，无法移动。

输入格式

输入仅包含一行，描述了已经放置在主对角线上的灯笼。它包含一个仅由字符 . 或 # 组成的字符串。当且仅当第 $i$ 个字符为 # 时，主对角线上的第 $i$ 个方格已经放置了灯笼。

数据范围

输入字符串的长度至少为 1，至多为 64。

输出格式

输出的第一行应包含一个整数：为了照亮市政厅的所有方格（包括已经放置的灯笼），需要在主对角线上放置的最少灯笼数量。输出的第二行应包含与输入格式相同的灯笼放置描述；这应当包含最初放置的灯笼。如果存在多个正确的解决方案，你可以输出其中任意一个。

样例

样例输入 1

......

样例输出 1

4
###.#.

样例输入 2

.#.#...

样例输出 2

4
.###.#.