#P18306. King's Festival

King's Festival

King's Festival

矮人国王希望用尽可能少的魔法灯照亮节日大厅。

大厅由 N×NN\times N 个方格组成。灯只能放在从左上角到右下角的主对角线上,每个主对角线方格至多放一盏灯。

一盏灯能够照亮:

  • 它所在的方格;
  • 与它在同一行的所有方格;
  • 与它在同一列的所有方格;
  • 与它在同一条对角线上的所有方格,两个对角线方向都包括在内。

有些灯已经固定在主对角线上,不能移动或移除。

求照亮大厅所有方格所需的最少灯数,并给出一种最优放置方案。灯数包括原来已经固定的灯。

输入格式

输入只有一行,包含一个长度为 NN 的字符串,字符只可能为 . 或 #。

第 ii 个字符为 #,表示主对角线从左上角起的第 ii 个方格已经有一盏固定的灯;. 表示该位置还没有灯。

1≤N≤641\le N\le64。

只有一组数据,没有测试组数 TT,也没有单独输入的 NN;NN 由字符串长度确定。

输出格式

第一行输出一个整数,表示最优方案中的总灯数,包括已经固定的灯。

第二行输出一个长度为 NN 的 .、# 字符串,描述最终的放置方案,格式与输入相同。输入中的每个 # 在输出中仍必须是 #。

所有方格都必须被照亮。如果有多种最优方案,可以输出任意一种。

样例 1

......
4
###.#.

样例 2

.#.#...
4
.###.#.