Trong thị trấn Quiet một \(k\) bạn trẻ muốn tham gia vào một cuộc biểu tình. Bởi vì thị trấn rất lớn, họ sẽ di chuyển
đến điểm hẹn bằng ô tô cá nhân. Mỗi người sẽ mang theo một chữ - để cùng nhau ghép lại thành \(1\) từ. Từ là một
số chữ cái từ tập \(\{A ... Z\}\). Không có hai chữ cái nào trùng nhau.

Thị trấn có dạng lưới ô vuông kích thước \(N×M\). Được biết, một chiếc xe tiêu thụ 1 lít xăng khi đi từ ô này sang
ô kề cạnh và không tiêu thụ xăng khi xe đứng yên. Để giảm thiểu nhiên liệu, các bạn trẻ quyết định rằng: nếu 2 chiếc xe gặp nhau ở một ô và tất cả các chữ cái trong hai chiếc xe tạo thành một chuỗi liên tiếp trong từ, thì họ
sẽ tiếp tục cuộc hành trình với một chiếc xe, tất nhiên là mang theo tất cả các chữ cái. Nếu không, những chiếc
xe đi theo cách riêng của mình.

Có một số ô vuông bị cấm đi vào. Ví dụ nếu từ là VOI thì người chở chữ V có thể đến đón người có chữ O
(hoặc ngược lại), rồi cả 2 cùng đi đến người có chữ I. Hoặc O và I đến với nhau, sau đó đến chỗ hẹn cùng V.
Nhưng V và I không nhập bọn với nhau được.

Biết kích thước của thị trấn \(n\) và \(m\), từ \(w\) cần ghép, cấu hình của thị trấn và vị trí ban đầu của những bạn trẻ, bạn
có 2 nhiệm vụ:

(1) Xác định diện tích tối thiểu của một lưới chữ nhật con chứa tất cả \(k\) bạn trẻ.

(2) Tính lượng nhiên liệu tối thiểu được tiêu thụ bởi tất cả các xe ô tô, biết rằng cuối cùng tất cả những bạn
trẻ sẽ đến với nhau trong một chiếc xe.

Input

• Dòng đầu ghi số nhiệm vụ 1 hoặc 2. Dòng thứ hai ghi 2 số tự nhiên \(n\) và \(m\), dòng thứ 3 ghi từ \(w\). Sau đó là \(n\)
  dòng, mỗi dòng ghi \(m\) ký tự đại diện cho các ô của thị trấn. Ô bị cấm ứng với #, ô tự do (đi vào được) ứng với _
  (ký tự gạch dưới). Ký tự @ nếu là điểm khởi đầu với chiếc xe chứa ký tự @ (dĩ nhiên ô này tự do)

Output

• In ra kết quả. Chú ý với nhiệm vụ 2, nếu không có giải pháp (không phải tất cả những người trẻ tuổi có thể đến
  với nhau), in ra -1

Constants

• \(2 \le n, m \le 60\)

• \(2 \le k \le 10\)

• Gọi \(z\) là số ô cấm. Khi đó \(0 \le z \le \frac{n * m}{3}\)

• Một ô có thể có nhiều xe.

Example

1
4 5
JOS
#_O_#
_#__S
_#J_#
___#_

9

2
5 7
BUN
_#_#_#_
__N#__#
_#__B__
U__#_#_
_#_#_#_

6