Berland 地图是一个大小为 n × m 的矩形,由大小为 1 × 1 的单元格组成。每个单元格要么是陆地,要么是水。地图被海洋包围。
湖泊是水细胞的最大区域,由侧面连接,不与海洋相连。形式上,湖是一组水细胞,因此可以从该集合中的任何一个细胞到达任何其他细胞,而无需离开该集合,并且仅移动到旁边相邻的细胞,它们都不位于矩形的边界上,并且不可能向集合中添加一个水细胞以使其与任何其他细胞连接。
你的任务是在地球上填满最少数量的水格,这样 Berland 就会有 k 个湖泊。注意地图上的湖泊初始数量不少于k。
输入
输入的第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 50, 0 ≤ k ≤ 50) - 地图的大小以及地图上应保留的湖泊数量。
接下来的 n 行每行包含 m 个字符 — 地图的描述。每个字符都是“.” (表示对应的单元格是水)或“*”(表示对应的单元格是陆地)。
保证地图至少包含k个湖泊。
输出
在第一行中打印应从水转变为陆地的最小单元格数。
在接下来的n行中打印m个符号——更改后的地图。格式必须严格遵循输入数据中地图的格式(不需要打印地图的大小)。如果有多个答案,请打印其中任何一个。
保证给定数据存在答案。
示例
输入 #1
5 4 1 **** *..* **** **.* ..**
输出 #1
1 **** *..* **** **** ..**
输入 #2
3 3 0 *** *.* ***
输出 #2
1 *** *** ***
注意
在第一个示例中,只有两个湖泊 - 第一个由单元格 (2, 2) 和 (2, 3) 组成,第二个由单元格 (4, 3) 组成。覆盖第二个湖是有利可图的,因为它较小。请注意,左下角的水域不是湖泊,因为该区域与海洋接壤。