Hai chị em Hồng, Phúc có một mảnh giấy to gồm \(m\) hàng \(n\) cột, các hàng được đánh số từ 1 đến \(m\) từ trên xuống dưới, các cột được đánh số từ 1 đến \(n\) từ trái sang phải, ô nằm giao giữa hàng \(i\) và cột \(j\) được gọi là ô (\(i,j\)). Hai chị em cùng nhau vẽ và tô màu trên mảnh giấy, em Phúc đã lựa chọn một số ô và tô màu các ô đó, Hồng rất thích kiểu giấy domino nên Hồng muốn vẽ \(k\) hình domino (mỗi hình có kích thước \(1× 2\) hoặc \(2× 1\) và chứa chọn hai ô chưa được tô màu của mảnh giấy). Để tạo điểm nhấn trên mảnh giấy, Hồng muốn lựa chọn các vị trí vẽ \(k\) hình domino để sau đó có thể chọn được một hình vuông lớn nhất, hình vuông không chứa ô đã bị tô màu cũng như ô thuộc vào một trong \(k\) hình domino, hình vuông đó sẽ cho em Phúc vẽ và tô màu.

Yêu cầu: Cho \(m,n,k\) và vị trí các ô mà em Phúc đã tô màu, hãy giúp Hồng lựa chọn các vị trí vẽ \(k\) hình domino để có thể tìm được hình vuông lớn nhất thỏa mãn yêu cầu trên.

Input

• Dòng đầu chứa ba số nguyên \(m,n,k\);
• Tiếp theo là \(m\) dòng, mỗi dòng chứa một xâu độ dài \(n\) mô tả mảnh giấy, ví trí các ô chưa tô màu là ký tự ., vị trí các ô đã được tô màu là #. Dữ liệu đảm bảo để có thể vẽ được \(k\) hình domino.

Output

• Xuất ra độ dài cạnh hình vuông lớn nhất

Constraints

• \(m,n≤ 32\)

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(m,n≤ 8,k≤ 3\).
• Subtask \(2\) (\(30\%\) số điểm): \(m≤ 8,n≤ 32\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 5 2
.....
....#
....# 

2 4 2
1 4 1

3 (<- đây là output)

...22
...1#
...1#