Đất nước ~ABC~ gồm ~n~ thành phố, có ~m~ con đường hai chiều với độ dài là ~1~ nối giữa một cặp thành phố. Có ~k~ khách du lịch, vị khách thứ ~i~ đang ở thành phố ~a_i~. Hiện đang có một sự kiện xảy ra ở thành phố ~b~, với mỗi khách du lịch, hãy in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện này.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,m,k~.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ miêu tả con đường ~(u,v)~.
• Dòng tiếp theo gồm ~k~ số nguyên dương miêu tả thành phố mà vị khách thứ ~i~ đang ở.
• Dòng cuối cùng chứa số nguyên dương ~b~ - thành phố nơi diễn ra sự kiện.

Output

• Với mỗi vị khách, in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện. Nếu không có đường đi thì in ra -1.

Điều kiện

• ~ 1 \le n,m,k \le 2*10^5~.

Subtask

• ~50\%~ số điểm: ~n,m,k \le 1000~.
• ~50\%~ số điểm: Không giới hạn gì thêm.

Ví dụ

Input 1:

4 3 3
1 2 
2 3
3 4
1 2 3
4

Output 1:

3 2 1

Input 2:

5 4 3
1 2
2 3
3 1
4 5
1 2 5
3

Output 2:

1 1 -1

Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận ~n \times m~, ô ở hàng ~i~ cột ~j~ được gọi là ô ~(i,j)~.

Đây là tài liệu mật và khẩn cấp, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Biết rằng bạn có thể đi sang ~4~ ô kề cạnh với ô đang đứng và mỗi ô ~(i,j)~ sẽ được miêu tả bằng một kí tự như sau:

• ~c(i,j) = .~, nếu đây là một ô bình thường có thể đi.
• ~c(i,j) = *~, đây là vùng nguy hiểm tuyệt đối không được đi vào.
• ~c(i,j) = S~, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
• ~c(i,j) = T~, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả kích thước bảng.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.

Output

• In ra một dòng là khoảng cách đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Nếu không có một đường đi nào như vậy, in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 1000~

Ví dụ

Input 1:

3 4 
S...
....
...T

Output 1:

5

Input 2:

3 4 
S.*T
*.*.
*...

Output 2:

7

Cho một đồ thị có hướng không trọng số gồm ~n~ đỉnh và ~m~ cạnh. Bạn đang đứng ở đỉnh ~S~ của đồ thị và mục tiêu của bạn là đến được đỉnh ~T~. Tuy nhiên, khác với bình thường, mỗi bước đi của bạn chỉ có thể đi qua đúng ~3~ cạnh nối tiếp nhau bắt đầu từ đỉnh đang đứng. Ví dụ, có bốn cạnh ~(1,2), (2,3), (3,4), (3,5)~, khi đứng ở đỉnh ~1~ thì trong một bước bạn chỉ được đi tới đỉnh ~4~ hoặc ~5~.

Cho đỉnh ~S~ và ~T~ hãy tìm số bước đi ngắn nhất để từ đỉnh ~S~ tới được ~T~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả số đỉnh và số cạnh.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u,v~ miêu tả cạnh một chiều ~u,v~.
• Dòng cuối gồm ~2~ số nguyên dương ~S~ và ~T~ miêu tả đỉnh xuất phát và đỉnh đích.

Output

• In ra một số là số bước ít nhất để đi từ ~S~ tới ~T~, nếu không có cách đi nào thì in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 2*10^5~

Ví dụ

Input 1:

5 5 
1 2
2 3
3 4
4 5
5 4
1 5

Output 1:

2

Input 2:

5 4
1 2
2 3
3 4
4 5
1 5

Output 2:

-1

Đất nước ~ABC~ gồm ~n~ thành phố nối với nhau bởi ~m~ con đường. Con đường thứ ~i~ nối hai chiều giữa hai thành phố ~u_i~ và ~v_i~, với độ dài là ~1~.

Luật pháp của ~ABC~ rất lạ, có ~k~ bộ ba được coi là "xấu" ~(a_i,b_i,c_i)~, khi di chuyển, bạn không được đi liên tiếp qua các thành phố ~a_i,b_i,c_i~. Lưu ý rằng, vẫn có thể đi theo thứ tự liên tiếp ~a_i,c_i,b_i~.

Bạn cần đi từ thành phố ~1~ tới ~n~, hãy tìm cách di chuyển ngắn nhất.

Input

• Dòng đầu chứa ba số nguyên ~n,m,k~ ~(n \le 3000; 1 \le m \le 2 \times 10^4; 0 \le k \le 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~u_i, v_i~ ~(1 ≤ u_i, v_i ≤ n; u_i ≠ v_i)~.
• ~k~ dòng sau, mỗi dòng gồm ba số nguyên dương ~a_i,b_i,c_i~ ~(1 ≤ a_i, b_i, c_i ≤ n) ~

Output

• Dòng đầu chứa một số ~d~ là đường đi ngắn nhất, nếu không có hãy in ra ~-1~.

Subtask

• Subtask ~2~: Không có ràng buộc gì thêm.

Sample Input 1

4 4 1
1 2
2 3
3 4
1 3
1 4 3

Sample Output 1

2

Đất nước U có ~n~ thành phố, đánh số từ 1 đến ~n~. Các thành phố được nối với nhau bởi hệ thống giao thông gồm m tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp thành phố, đảm bảo luôn có đường đi lại giữa hai thành phố bất kì trong nước (trực tiếp hoặc đi qua một số thành phố khác). Giữa hai thành phố bất kì không có quá một tuyến đường nối trực tiếp.

Có tổng cộng ~b~ kho lương thực được đặt trên khắp cả nước, mỗi kho nằm ở một thành phố khác nhau. Để bảo vệ đất nước khỏi quân xâm lược, Thủ tướng U đã chọn ra ~r~ thành phố khác nhau để đặt trại quân sự.

Yêu cầu: Để giải quyết vấn đề lương thực cho quân doanh, với mỗi thành phố được đặt trại quân sự, nhiệm vụ của bạn là tính toán số tuyến đường ít nhất cần đi nếu xuất phát từ thành phố đó đến một kho lương thực bất kì.

Input

• Dòng thứ nhất gồm bốn số nguyên: ~n,m,b,r\ (2 \le n \le 5.10^5; 1 \le m \le 5.10^5; 1 \le b,r \le n)~
• Dòng thứ hai gồm ~b~ số nguyên là chỉ số của các thành phố được đặt kho lương thực;
• Dòng thứ ba gồm ~r~ số nguyên là chỉ số của các thành phố được đặt trại quân sự;
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~ và ~v~ thể hiện có một tuyến đường hai chiều nối trực tiếp hai thành phố ~u~ và ~v~.

Output

• Xuất ra ~r~ số nguyên trên cùng một dòng là kết quả tính được của các thành phố được đặt trại quân sự theo thứ tự của dữ liệu.

Subtask

• Subtask 1: (40% số test): ~n \le 5000~
• Subtask 2: (60% số test): Không có ràng buộc gì thêm.

Sample Input 1

6 6 2 3
3 2
1 5 4
1 2
1 6
3 6
2 3
4 5
3 4

Sample Output 1

1 2 1

Explanation 1

• Thành phố ~1~: ~1 → 2~
• Thành phố ~4~: ~4 → 3~
• Thành phố ~5~: ~5 → 4 → 3~

Cho một đơn đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Độ dài của mỗi cạnh là ~1~. Ta định nghĩa khoảng cách giữa hai đỉnh ~u~ và ~v~ là độ đường đi ngắn nhất từ ~u~ đến ~v~.

Ban đầu, tất cả các đỉnh được tô màu ~0~. Cho ~q~ truy vấn, truy vấn thứ ~i~ yêu cầu tô màu ~c_i~ cho tất cả các đỉnh có khoảng cách đến ~u_i~ nhỏ hơn hoặc bằng ~d _i~.

Hãy cho biết màu của từng đỉnh sau khi thực hiện xong ~q~ truy vấn trên.

Input

• Dòng đầu ghi hai số nguyên dương ~n,m~ miêu tả số cạnh và số đỉnh.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u_i~ và ~v_i~ ~(u_i, v_i \le n)~ mô tả một cạnh trong đồ thị. Dữ liệu vào đảm bảo đồ thị đã cho là đơn đồ thị.
• Dòng tiếp theo ghi số nguyên dương ~q~ - miêu tả số truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng ghi ba số nguyên ~u_i, d_i, c_i~

Giới hạn

• ~n,m,q \le 10^5~.
• ~d_i \le 10~.
• ~c_i \le 10^5~.

Output

In ra ~n~ dòng, dòng thứ ~i~ in ra một số nguyên duy nhất - màu của đỉnh ~i~ sau khi thực hiện ~q~ truy vấn trên.

Sample Input

7 7
1 2
1 4
2 3
3 6
4 5
5 6
6 7
3
7 3 1
5 1 2
5 0 3

Sample Output

0
1
1
2
3
2
1

Cho một đồ thị vô hướng gồm ~n~ đỉnh ~m~ cạnh. Cạnh ~i~ nối giữa đỉnh ~u_i~ và ~v_i~ và có kí tự ~c_i~ được viết lên trên nó.

Hãy tìm một đường đi từ ~1~ đến ~n~ ngắn nhất mà sau khi viết các kí tự có được khi đi qua các cạnh là một xâu palindrome. Nếu không tồn tại bất kì đường đi nào thỏa mãn là palindrome, in ra ~-1~.

Lưu ý: Đồ thị có thể tồn tại khuyên và cạnh lặp, các đỉnh và cạnh có thể đi qua lại nhiều lần.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 1000)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~u_i, v_i, c_i~ mô tả cạnh thứ ~i~ của đồ thị.

Output

• Nếu tồn tại một đường đi tạo ra xâu palindrome, in ra độ dài ngắn nhất có thể. Nếu không, in ra ~-1~.

Sample Input 1

4 5
1 1 a
1 2 a
2 3 a
3 4 b
4 4 a

Sample Output 1

5

Explanation 1

Đi qua các cạnh ~2, 3, 4, 5, 5~, ta nhận được xâu aabaa.

Sample Input 2

3 4
1 1 a
1 2 a
2 3 b
3 3 b

Sample Output 2

-1

Một công ty có ~n~ nhân viên đang trong quá trình tái cơ cấu tổ chức. Sau quá trình này, sơ đồ cấp bậc trong công ty tạo thành một đồ thị dạng cây gồm ~n~ đỉnh, mỗi đỉnh là sếp của tất cả các con của chúng.

Mỗi nhân viên có một danh sách gồm ~k_i~ người họ đồng ý làm sếp trực tiếp của mình. Ngoài ra, mỗi nhân viên cần được tính toán lại lương sao cho lương của mỗi người sếp phải lớn hơn tổng lương của những nhân viên người đó quản lí.

Hãy tìm cách tái cơ cấu lại công ty sao cho tổng lương phải trả cho ~n~ nhân viên là nhỏ nhất có thể.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - số nhân viên trong công ty.
• ~n~ dòng tiếp theo, mỗi dòng bắt đầu bởi số nguyên ~k_i~. Sau đó là ~k_i~ số nguyên dương là danh sách những người được nhân viên thứ ~i~ đồng ý làm sếp của mình.

Output

• Gồm một số nguyên dương là tổng lương phải trả nhỏ nhất.

Subtask

• Subtask 1 ~(20\%)~: ~2 \le n \le 10, \sum{k_i} \le 20~
• Subtask 2 ~(45\%)~: ~2 \le n \le 200, \sum{k_i} \le 200~.
• Subtask 3 ~(35\%)~: ~2 \le n \le 5000, \sum{k_i} \le 10000~.

Sample Input 1

4
1 4
3 1 3 4
2 1 2
1 3

Sample Output 1

8

Explanation 1

    3
   / \ 
  4   2
 /
1

Lương của từng người là ~[1, 1, 2, 4]~.

Alice vừa mới lạc vào một vùng đất rất kì lạ tên là "Bruhderland". Đây là một vùng đất lai giữa "Wonderland" và "Borderland", nơi có phép màu và cả những trò chơi sinh tử.

Bruhderland được biểu diễn bằng một ma trận ~n \times m~, với ô ~(i,j)~ là một trong các kí tự sau:

• .: có nghĩa là ô đất trống, có thể đi vào.
• *: có nghĩa là ô có một tảng đá, không thể đi vào.
• A: có nghĩa là có một trò chơi với độ khó ~A~ ở ô này, Alice rất giỏi nên sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~1~ sức lực.
• B: có nghĩa là có một trò chơi với độ khó ~B~ ở ô này, Alice vẫn sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~2~ sức lực.

Giả sử, Alice đang ở ô ~(i,j)~, cô có thể đi sang ~4~ ô kề cạnh nếu như ô đó không vượt qua ngoài bảng và không chứa tảng đá nào. Như đã nói, Bruhderland có cả yếu tố phép màu, vậy nên khi vào đây, cô đã học được cách đọc thần chú để phá hủy một tảng đá bất kì mà không mất sức lực nào (nghĩa là có thể đi vào ô chứa tảng đá vừa bị phá hủy), tuy nhiên do năng lực giới hạn, Alice chỉ có thể đọc thần chú ~k~ lần mà thôi.

Alice đang ở ô ~(1,1)~, để thoát ra khỏi Bruhderland, cô sẽ cần đến ô ~(n,m)~. Tuy nhiên, do khá lười tham gia vào các trò chơi, Alice muốn thoát ra khỏi Bruhderland sao cho tốn ít sức lực nhất.

Quan trọng: Dữ liệu đảm bảo kết quả không quá ~2500~.

Input: BRUHDERLAND.INP

• Dòng đầu tiên ghi ~3~ số nguyên dương ~n,m,k~ ~(1 \le n,m \le 1000, 0 \le k \le 5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm một xâu kí tự độ dài ~m~ miêu tả hàng thứ ~i~ của ma trận.
• Dữ liệu đảm bảo ô ~(1,1)~ là kí tự . và luôn tồn tại cách đi từ ~(1,1)~ tới ~(n,m)~ nếu sử dụng thần chú một cách hợp lý.

Output: BRUHDERLAND.OUT

• In ra một số nguyên dương là số sức lực ít nhất cần tiêu tốn để đến được ô ~(n,m)~.

Scoring:

• Subtask ~1~ ~(10\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ chỉ gồm kí tự A
• Subtask ~2~ ~(15\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B và ..
• Subtask ~3~ ~(10\%)~: ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~4~ ~(10\%)~: Các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~5~ ~(15\%)~: ~n \times m \le 10^5~ và ~k = 0~.
• Subtask ~6~ ~(20\%)~: ~n \times m \le 10^5~.
• Subtask ~7~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

4 4 0
.AAA
AAAA
AAAA
AAAA

Sample Output 1

6

Sample Input 2

5 4 0
.AAA
***A
AAAA
A***
AAAA

Sample Output 2

13

Sample Input 3

5 4 0
.AAA
***B
AAAA
A**B
BAAA

Sample Output 3

9

Sample Input 4

5 4 2
.BAA
****
AABA
A***
BABA

Sample Output 4

6

Có một ma trận dạng lưới ô vuông gồm ~m~ hàng và ~n~ cột. Các hàng được đánh số từ ~1~ đến ~m~ theo thứ tự từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ theo thứ tự từ trái qua phải. Ô nằm trên hàng ~i~ và cột ~j~ được ký hiệu là ~(i, j)~. Một số ô trên lưới có chứa chướng ngại vật, các ô còn lại là ô trống.

Có một con robot di chuyển trên lưới này. Vị trí xuất phát và vị trí kết thúc của con robot là những ô trống đã được cố định từ trước. Con robot được cài sẵn một chuỗi lệnh điều khiển là một xâu ký tự ~C~. Mỗi lệnh của chuỗi là một trong các ký tự U, D, L, R, H. Gọi vị trí hiện tại của robot là ~(i, j)~. Ý nghĩa của từng ký tự lệnh như sau:

• U: Đi lên trên ~1~ bước tới ô ~(i - 1, j)~
• D: Đi xuống dưới ~1~ bước tới ô ~(i + 1, j)~
• L: Đi sang trái ~1~ bước tới ô ~(i, j - 1)~
• R: Đi sang phải ~1~ bước tới ô ~(i, j + 1)~
• H: Đứng yên tại ô ~(i, j)~

Con robot sẽ lần lượt thực hiện các lệnh trong chuỗi lệnh ~C~. Chú ý rằng, nếu một lệnh làm con robot đi ra ngoài bảng hoặc đi vào một ô có chướng ngại vật, con robot sẽ bỏ qua và không thực hiện lệnh di chuyển này.

Người ta nhận thấy rằng, nếu xuất phát tại vị trí đã chọn, sau khi thực hiện hết các lệnh trong chuỗi lệnh ~C~, con robot có thể không dừng lại ở vị trí kết thúc đã chọn. Vì vậy, ta cần sửa lại xâu ký tự ~C~ để con robot sẽ dừng lại tại đúng vị trí kết thúc mong muốn sau khi kết thúc thực hiện chuỗi lệnh ~C~. Trong mỗi phép biến đổi, bạn được thực hiện một trong ba thao tác sau:

• Chèn thêm một lệnh vào chuỗi ~C~ ở một vị trí bất kỳ.
• Thay đổi một lệnh bất kỳ trong chuỗi ~C~.
• Xoá đi một chuỗi con liên tiếp bất kỳ của chuỗi ~C~.

Hãy sử dụng ít phép biến đổi nhất có thể để với chuỗi lệnh ~C~, robot sẽ bắt đầu ở vị trí xuất phát đã chọn và kết thúc ở vị trí kết thúc đã chọn. Chú ý rằng, bạn không cần cực tiểu hoá số bước di chuyển của robot, chỉ cần số bước biến đổi chuỗi lệnh là nhỏ nhất có thể. Các ô xuất phát và kết thúc của robot là các ô trống. Trên hành trình của mình, robot có thể đi qua những ô này hay bất kỳ ô trống nào khác một số lần tuỳ ý.

Input

• Dòng đầu tiên chứa số nguyên ~\Theta~ ~(1 \leq \Theta \leq 6)~ là số thứ tự của subtask chứa test này.
• Dòng thứ hai chứa hai số nguyên ~m~ và ~n~ ~(1 \leq m, n \leq 175)~.
• Trong ~m~ dòng tiếp theo, mỗi dòng chứa một xâu ký tự độ dài ~n~ mô tả một hàng của bảng. Mỗi ký tự của những xâu này có thể là . (dấu chấm thể hiện ô trống), # (ô có chướng ngại vật), S (vị trí xuất phát của robot), E (vị trí kết thúc của robot). Dữ liệu vào đảm bảo có chính xác một chữ S và chính xác một chữ E trong lưới.
• Dòng cuối cùng chứa một xâu ký tự mô tả chuỗi lệnh ~C~ được cài đặt trong robot. Xâu ký tự này chỉ chứa từ 1 đến 300 ký tự, là các chữ cái U, D, L, R và H.

Output

Nếu không tồn tại chuỗi lệnh nào giúp robot đi từ vị trí xuất phát tới vị trí kết thúc, in ra số ~-1~ duy nhất. Ngược lại, dòng đầu tiên chứa số nguyên k là số bước biến đổi chuỗi lệnh tối thiểu. Trong k dòng tiếp theo, mỗi dòng thể hiện một phép biến đổi theo một trong ba khuôn dạng sau:

• INS p c (với ~0 \leq p \leq |C|~ và ~c~ là một trong các chữ cái U, D, L, R và H): Chèn ký tự ~c~ vào sau vị trí ~p~ của chuỗi lệnh. Nếu ~p = 0~, ký tự được chèn vào đầu chuỗi lệnh. Nếu ~p = |C|~, ký tự được chèn vào cuối chuỗi lệnh.
• REP p c (với ~1 \leq p \leq |C|~ và ~c~ là một trong các chữ cái U, D, L, R và H): Thay ký tự ở vị trí ~p~ bởi ký tự ~c~.
• DEL l r (với ~1 \leq l \leq r \leq |C|~): Xoá đi đoạn lệnh liên tiếp từ vị trí ~l~ tới vị trí ~r~.

Ở đây, ~|C|~ là độ dài chuỗi lệnh trước khi phép biến đổi diễn ra. Chú ý rằng, sau mỗi phép biến đổi, các ký tự của chuỗi lệnh được đánh số lại từ 1.

Nếu có nhiều phương án biến đổi chuỗi lệnh tối ưu, bạn được đưa ra một phương án bất kỳ.

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask ~1~ (~14~ điểm): ~m = 1~.
• Subtask ~2~ (~10.5~ điểm): Chuỗi lệnh ~C~ chỉ chứa ký tự H.
• Subtask ~3~ (~10.5~ điểm): Dữ liệu vào đảm bảo tồn tại một phương án biến đổi tối ưu mà không cần sử dụng phép biến đổi DEL (xoá một đoạn liên tiếp).
• Subtask ~4~ (~10.5~ điểm): ~m, n \leq 20~ và chuỗi lệnh ban đầu có không quá ~50~ ký tự.
• Subtask ~5~ (~10.5~ điểm): ~m,n \leq 50~ và chuỗi lệnh ban đầu có không quá ~100~ ký tự.
• Subtask ~6~ (~14~ điểm): Không có ràng buộc gì thêm.

Với mỗi test, bạn được 100% số điểm nếu tìm ra số bước biến đổi tối thiểu mà không đưa ra được phương án biến đổi.

Example

Sample Input 1

4
3 5
....E
S#...
..#..
LRRRDDULLDU

Sample Output 1

3

Giải thích

Trong ví dụ đầu tiên, chuỗi lệnh được biến đổi như sau: LRRRDDULLDU ~\rightarrow~ URRRDDULLDU ~\rightarrow~ URRRU ~\rightarrow~ URRRUR. Chuỗi URRRUR sẽ đưa robot từ vị trí xuất phát tới vị trí kết thúc. Chú ý rằng, lệnh U thứ hai không được thực hiện do robot sẽ bị đi ra ngoài bảng nếu đi lên trên.

Sample Input 2

3
3 5
.....
...SE
.....
LLLRRRRRUUD

Sample Output 2

0

Trên bảng kích thước ~n \times m~, máy tính chọn ngẫu nhiên một số ô là hang rắn được kí hiệu bởi kí tự ~+~. Người chơi cần di chuyển từ vị trí là ô chứa kí tự P đến ô chứa kí tự C. Một cách di chuyển được gọi là thông minh nếu càng tránh xa các ô là hang rắn càng tốt. Khoảng cách hai ô ~(x,y)~ và ~(u,v)~ được tính theo khoảng cách Manhattan: ~|x-u|+|y-v|~. Yêu cầu: Tìm cách di chuyển để trong quá trình di chuyển khoảng cách tới ô là hang rắn ngắn nhất là xa nhất.

Input

• Dòng đầu chứa hai số nguyên ~n, m~ ~(n,m \le 2000)~.
• Tiếp theo là ~m~ hàng, mỗi hàng chứa kí tự là một trong các kí tự: ~'+'~ (hang rắn), ~'P'~ (xuất phát), ~'C'~ (đích), ~'.'~ (ô tự do).

Output

• Gồm một dòng chứa một số là khoảng cách tìm được.

Sample Input 1

4 5
P....
.....
+++..
....C

Sample Output 1

2

Vì Gojo Satoru quá yếu, nên một ngày đẹp trời Sukuna đã rủ Chau solo bành trướng lãnh địa.

Cả ~2~ solo trên mảnh đất là một bảng hình chữ nhật ~A~, có diện tích ~N \times M~ với ~N~ hàng và ~M~ cột. Kí hiệu ~(i, j)~ là ô nằm trên hàng thứ ~i~, cột thứ ~j~ với các hàng được đánh số từ trên xuống dưới theo thự từ ~1~ đến ~N~, các cột được đánh số từ trái sang phải theo thự từ ~1~ đến ~M~.

Sukuna và Chau đã bành trướng lên lãnh địa này và vẽ ra ~2~ vùng lãnh địa của mình. Trên bảng ~A~, ta kí hiệu ~A (i , j) = 1~ nếu ô đó chứa biên của phần lãnh địa Chau, ~A (i, j) = 2~ nếu ô đó chứa biên của phần lãnh địa của Sukuna, ~A (i, j) = 3~ nếu nó chứa biên của phần lãnh địa của cả hai người, còn ~A (i, j) = 0~ nếu nó là đất trống. Đảm bảo biên của mỗi lãnh địa tạo thành một vòng khép kín. (Biên tức là vòng ngoài của lãnh địa).

Hình trên là minh họa cho test ví dụ 1.

• Viền màu đỏ là biên của lãnh địa của Chau. Viền màu xanh là biên lãnh địa của Sukuna. Viền màu tím là biên lãnh địa của cả 2.
• Các ô màu cam là các ô thuộc chỉ thuộc lãnh địa của Chau. Các ô màu xanh lá là các ô chỉ thuộc lãnh địa của Sukuna. Các ô màu xanh dương là các ô thuộc lãnh địa của cả hai.

Vì mải dùng Thuật Thức nên Chau không thể dùng Thuật Toán, Chau muốn các bạn tính hộ xem có bao nhiêu ô thuộc cả ~2~ lãnh địa

Yêu cầu: In ra số ô thuộc cả ~2~ lãnh địa.

Input

• Dòng đầu tiên là 2 số tự nhiên ~N, M~ ~(N, M\leq 1000)~ là số hàng và cột của bảng ~A~.
• ~N~ dòng tiếp theo, môi dòng là một hàng của bảng ~A~ và có ~M~ số nguyên không âm nhỏ hơn hoặc bằng 3. Ý nghĩa giá trị của mỗi số nguyên không âm đã nếu ở đề bài ở trên.

Output

• In ra một số nguyên không âm là kết quả của bài toán.

Subtask

• Subtask ~1~ (~25\%~ số điểm): ~N = 1~ .
• Subtask ~2~ (~25\%~ số điểm): ~N, M\leq 100~ và các ô biên của 2 lãnh địa trùng nhau.
• Subtask ~3~ (~25\%~ số điểm): ~N, M\leq 100~.
• Subtask ~4~ (~25\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

6 6
0 0 1 0 0 0
0 1 0 1 1 0
1 0 2 2 3 0
0 3 1 1 3 0
0 2 0 0 2 0
0 2 2 2 2 0

Sample Output 1

7

Một trò chơi đánh golf trên smartphone được mô phỏng là một lưới ô vuông có kích thước ~R~ dòng và ~C~ cột. Cho biết vị trí ô chứa bóng, vị trí ô chứa hố cần đánh bóng vào và vị trí của ô có vật cản. Tại mỗi lần chơi, người chơi có thể đánh quả bóng theo một trong bốn hướng (trên, dưới, trái, phải), quả bóng có thể di chuyển không quá ~K~ ô liên tiếp và không thể đi qua ô có vật cản.

Yêu cầu: Hãy tính số lần đánh bóng ít nhất để đưa được bóng vào hố.

Dữ liệu vào từ tệp văn bản GOLF.INP:

• Dòng đầu tiên gồm ba số nguyên dương ~R, C~ và ~K~ ~(R \times C \le 10^6; \ K \le 10^6)~;
• ~R~ dòng tiếp theo, mỗi dòng chứa ~C~ kí tự thuộc bốn loại kí tự sau:
  • . là vị trí ô trống;
  • # là vị trí ô có vật cản;
  • S là vị trí của bóng, có duy nhất một kí tự S trong bảng;
  • G là vị trí của hố, có duy nhất một kí tự G trong bảng.

Dữ liệu đảm bảo luôn có cách đưa bóng vào hố.

Kết quả ghi ra tệp văn bản GOLF.OUT:

Gồm một số nguyên duy nhất là số lần đánh bóng ít nhất cần thực hiện.

Ví dụ

Input

2 5 1
S#...
...#G

Output

7

Input

2 5 10
S#...
...#G

Output

5

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm không có kí tự # trong bảng;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~R \le 2~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~R, C, K \le 10^2~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~K \ge \max(R, C)~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.