Minh và Sơn vừa nghĩ ra một trò chơi rất thú vị, và trò chơi này được chơi trên một bàn cờ vua kích thước R dòng, C cột. Mỗi người chơi ban đầu sẽ có một số lượng quân vua, trong một nước cờ, quân vua có thể di chuyển tới 1 trong 8 ô liền kề xung quanh nó.

Tiềm năng thắng của một người chơi được định nghĩa là một giá trị bằng với tổng khoảng cách giữa mọi cặp quân cờ mà anh ta có. Khoảng cách giữa 2 quân cờ là số lượt cờ ít nhất cần có để 2 quân cờ di chuyển tới cùng một vị trí (theo luật cờ vua quốc tế), và quân cờ khác không làm ảnh hưởng đến khoảng cách 2 quân cờ ( nói cách khác, có thể coi không có sự hiện diện của mọi quân cờ khác khi tính khoảng cách).

Minh biết rằng chỉ số tiềm năng thắng ảnh hưởng rất lớn đến chiến thuật của cuộc chơi nên Minh muốn nhờ bạn lập trình tính giúp chỉ số này của cả Minh và Sơn.

Input

Dòng đầu: gồm 2 số R và C (1 <= R, C <= 1000) là số dòng và số cột

R dòng tiếp theo, mỗi dòng C ký tự. Ký tự M nghĩa là có quân cờ của Minh trong ô đó, S là của Sơn, . nghĩa là ô cờ trống.

Mỗi người chơi có ít nhất một quân cờ.

Output

In ra trên một dòng duy nhất gồm 2 số cách nhau bởi 1 dấu cách: lần lượt là chỉ số tiềm năng của Minh và Sơn.

Sample test

Input

2 3
SMS
MMS

Output

3 5

Input

2 3
S.M
M..

Output

2 0

Input

4 5
M....
..S.M
SS..S
.M...

Output

10 13

Để phòng chống hư hỏng, mạng lưới điện cần được kiểm tra định kỳ.

Mạng lưới điện bao gồm n nút và n-1 dây điện. Các nút được đánh số 1, 2, ..., n. Mỗi dây điện kết nối hai nút khác nhau, và tất cả các nút đều thông nhau (luôn có đường đi giữa hai nút bất kỳ).

An và Khánh ban đầu đều ở nút 1. Mỗi giây tiếp theo, An hoặc Khánh sẽ di chuyển dọc theo một dây điện đến một nút kề.

Để hoàn thành việc kiểm tra, bây giờ mỗi nút phải được An hoặc Khánh đến thăm ít nhất một lần.

Hai người cần duy trì liên lạc, vì vậy tại bất kỳ thời điểm nào, khoảng cách giữa họ không được vượt quá k. Khoảng cách giữa hai người được định nghĩa là số lần di chuyển (số dây điện) ít nhất cần thiết để An đi đến vị trí của Khánh.

Bây giờ An muốn biết, hai người cần ít nhất bao nhiêu giây để hoàn thành việc kiểm tra mạng lưới? (Biết rằng hai người luôn có thể hoàn thành nhiệm vụ trong điều kiện ràng buộc.)

Input

• Dòng đầu tiên nhập hai số nguyên dương n, k (1 <= k < n <= 10^6)
• n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v biểu thị một dây điện nối nút u và nút v.

Output

• Một dòng duy nhất chứa một số nguyên không âm, là tổng số giây (tổng số lần di chuyển) ít nhất cần thiết để kiểm tra toàn bộ mạng lưới.

Ví dụ 1

Input

4 1
1 2
1 3
3 4

Output

5

Giải thích Chiến lược tối ưu như sau:

• Giây thứ 1: An từ nút 1 di chuyển đến nút 2. (Vị trí: An 2, Khánh 1. Khoảng cách: 1)
• Giây thứ 2: An từ nút 2 di chuyển đến nút 1. (Vị trí: An 1, Khánh 1. Khoảng cách: 0)
• Giây thứ 3: Khánh từ nút 1 di chuyển đến nút 3. (Vị trí: An 1, Khánh 3. Khoảng cách: 1)
• Giây thứ 4: An từ nút 1 di chuyển đến nút 3. (Vị trí: An 3, Khánh 3. Khoảng cách: 0)
• Giây thứ 5: Khánh từ nút 3 di chuyển đến nút 4. (Vị trí: An 3, Khánh 4. Khoảng cách: 1) (Tất cả các nút 1, 2, 3, 4 đều đã được thăm). Không khó để thấy khoảng cách hai người luôn được giữ trong phạm vi 1.

Ví dụ 2

Input

5 4
1 2
1 3
2 4
3 5

Output

4

Giải thích Chiến lược tối ưu như sau:

• Giây thứ 1: An từ nút 1 di chuyển đến nút 2.
• Giây thứ 2: An từ nút 2 di chuyển đến nút 4.
• Giây thứ 3: Khánh từ nút 1 di chuyển đến nút 3.
• Giây thứ 4: Khánh từ nút 3 di chuyển đến nút 5. (Các nút An thăm: 1, 2, 4. Các nút Khánh thăm: 1, 3, 5. Tất cả các nút đã được thăm). Do k = 4 (và mạng lưới chỉ có 5 nút), điều này tương đương với việc không có giới hạn về khoảng cách giữa hai người.

An có một dãy số a gồm N phần tử: a1, a2, ..., a_N.

Một dãy con a{i1}, a{i2}, ..., a{ik} với i1 < i2 < ... < ik được gọi là dãy con tăng nếu a{i1} < a{i2} < ... < a{i_k}.

An muốn thực hiện Q lần thử nghiệm. Mỗi lần thử nghiệm, An sẽ thay đổi giá trị của một phần tử trong dãy và muốn biết độ dài của dãy con tăng dài nhất của dãy mới là bao nhiêu?

Yêu cầu: Cho Q truy vấn, truy vấn thứ i gồm hai số nguyên dương pi và xi. Yêu cầu là: Giả sử phần tử thứ pi của dãy (tức là a{pi}) được thay bằng giá trị xi, thì độ dài của dãy con tăng dài nhất của dãy số sau khi thay đổi là bao nhiêu?

Lưu ý rằng giá trị của các phần tử sẽ không thật sự thay đổi sau các truy vấn (mỗi truy vấn là một giả định độc lập, thực hiện trên dãy số ban đầu).

Hãy viết chương trình trả lời Q truy vấn trên.

Input

• Dòng đầu tiên chứa số nguyên dương N, Q (N, Q <= 300000) - số phần tử và số truy vấn.
• Dòng thứ hai gồm N số nguyên dương a1, a2, ..., aN (ai <= 10^9).
• Q dòng tiếp theo, mỗi dòng gồm hai số nguyên pi và xi (pi <= N, xi <= 10^9) mô tả truy vấn thứ i.

Output

• Gồm Q dòng, dòng thứ i in ra một số nguyên dương là câu trả lời (độ dài dãy con tăng dài nhất) cho truy vấn thứ i.

Ví dụ

Input:

7 3
1 5 3 1 2 4 6
2 2
7 3 
4 100

Output:

5
3
4

Giải thích:

• Dãy số ban đầu là 1 5 3 1 2 4 6.
• Truy vấn 1: Đổi a2 (giá trị 5) thành 2. Dãy mới là 1 2 3 1 2 4 6. Một trong các dãy con tăng dài nhất là 1, 2, 3, 4, 6 (tương ứng a1, a2, a3, a6, a7). Độ dài là 5.
• Truy vấn 2: Đổi a7 (giá trị 6) thành 3 (trên dãy ban đầu). Dãy mới là 1 5 3 1 2 4 3. Một trong các dãy con tăng dài nhất là 1, 3, 4 (tương ứng a1, a3, a6). Độ dài là 3.
• Truy vấn 3: Đổi a4 (giá trị 1) thành 100 (trên dãy ban đầu). Dãy mới là 1 5 3 100 2 4 6. Một trong các dãy con tăng dài nhất là 1, 2, 4, 6 (tương ứng a1, a5, a6, a_7). Độ dài là 4.