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)~.

Công việc này chưa bao giờ là dễ dàng. Một vài ô đã bị địch cài bom và không biết khi nào sẽ phát nổ. Bạn chỉ biết rằng loại bom này có sức công phá là ~r~, có nghĩa là nếu bom ở ô ~(i,j)~, khi nó phát nổ thì các ô ~(u,v)~ thỏa mãn ~|i-u| + |j-v| \le r~ sẽ bị tàn phá (ô ~(i,j)~ và ~(u,v)~ đều nằm trong bảng). Những ô ~(u,v)~ như vậy gọi là những ô bị ảnh hưởng bởi bom.

Đây là tài liệu mật, tất nhiên chỉ huy của bạn không muốn nhận một sự rủi ro nào, 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 sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. 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) =~ +, đây là ô có bom, như đã nói, các ô nằm cách ô này khoảng cách không quá ~r~ (kể cả chính nó) sẽ không thể đ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 ~3~ số nguyên ~n,m,r~, miêu tả kích thước bảng và vùng ảnh hưởng của bom.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.
• Dữ liệu luôn đảm bảo ô chứa kí tự ~S~ và ~T~ không bị ảnh hưởng bởi ô chứa bom nào.
  
  

Output

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

Constraints

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

Subtasks

• ~20\%~ số điểm: Không có ô nào có ~c(i,j) = *~ hoặc ~c(i,j) = +~.
• ~20\%~ số điểm: ~r = 0~.
• ~30\%~ số điểm: ~n,m \le 100~.
• ~30\%~ số điểm: Không có ràng buộc gì thêm.
  
  

Sample Test 1

Input:

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

Output:

5

Sample Test 2

Input:

3 4 0
S.+T
*.*.
*...

Output:

7

Sample Test 3

Input:

4 4 1
S..*
*...
+.*.
.T..

Output:

8

Cho cây ~n~ đỉnh gồm ~n-1~ cạnh có gốc tại đỉnh ~1~. Đỉnh thứ ~i~ có giá trị là ~a_i~.

Đối với mỗi đỉnh ~u~, ta cần phải tính độ đẹp của đường đi xuất phát từ gốc là đỉnh ~1~ tới ~u~. Độ đẹp trên đường đi này được tính như sau:

• Ta có thể chọn tối đa một đỉnh ~v~ bất kì thuộc đường đi từ ~1~ tới ~u~, sau đó gán giá trị ~a_v = 0~.
• Tiếp theo, tính giá trị ~X =~ ước chung lớn nhất theo giá trị của các đỉnh thuộc đường đi từ ~1~ tới ~u~.
• Độ đẹp của đường đi từ ~1~ tới ~u~ là cách thay đỉnh tốt nhất (hoặc có thể giữ nguyên giá trị các đỉnh) sao cho giá trị ~X~ thu được là lớn nhất.

Với mỗi ~u~ từ ~1~ tới ~n~, bạn cần tính được độ đẹp của đường đi ~(1,u)~, lưu ý các truy vấn ở đây là độc lập, nghĩa là bạn không thay đổi thực sự một giá trị nào cả.

Input

• Dòng đầu chứa số nguyên ~n~ ~( n \le 2 \times 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương miêu tả dãy ~a~ ~(1 \le a_i \le 2 \times 10^5)~
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~ ~(1≤u,v≤n; u≠v;)~ mô tả một cạnh của cây nối hai đỉnh ~u_i~ và ~v_i~.

Output

• In ra ~n~ số nguyên dương là độ đẹp của đường đi ~(1,u)~ với ~u \in [1,n]~

Subtask

• Subtask ~1~: ~n \le 2000 ~. ~(50\%)~
• Subtask ~2~: Không có giới hạn gì thêm. ~(50\%)~

Sample Input 1

3
6 2 3
1 2
1 3

Sample Output 1

6 6 6

Mùa tuyển sinh đã đến, là một người đã cố gắng suốt cả năm qua nên AP đang phải đau đầu để chọn trường cho mình. Ting ting tiếng chuông điện thoại của AP kêu lên và AP nhận được một tin nhắn từ Hogwarts báo nhập học, AP đồng ý ngay. Đời không như mơ, để bước vào ngôi trường pháp thuật trứ danh này AP phải qua một bài kiểm tra của thầy hiệu trưởng như sau:

AP được phù phép dịch chuyển đến một mỏm đá, trước mặt AP là những hòn đảo được đánh số từ ~1~ đến ~n~ có diện tích là ~w_i~, giữa những hòn đảo có ~m~ cây cầu được xây sắn bằng phép thuật, cây cầu thứ ~j~ nối hai đảo ~u_i~ và ~v_j~ lại với nhau. Thầy hiệu trưởng muốn qua bài thi này để đánh giá khả năng sử dụng thần chú của AP với đề bài là hai thần chú:

• ~C~ ~i~ ~W~ có tác dụng thay đổi kích thước của hòn đảo thứ ~i~ thành diện tích ~W~
• ~D~ ~j~ có tác dụng xóa đi cầy cầu thứ ~j~ (nếu lúc này nó vẫn tồn tại) nối hai hòn đảo ~u_i~ và ~v_j~.

Sau mỗi thao tác thay đổi như thế, thầy hiệu trưởng muốn biết tổng diện tích lớn nhất của những hòn đảo đến được với nhau. Vốn trí nhớ AP không được tốt và AP cũng khá lười để trả lời những câu hỏi của thầy khi thực hiện một đống phép thuật nên AP cần bạn hơn bao giờ hết. Hãy giúp AP trả lời câu hỏi của thầy hiệu trưởng để vượt qua bài kiểm tra nha.

Input:

• Dòng thứ nhất gồm ~3~ số nguyên ~n,m,q~ ~(n,m,q \le 3*10^5)~
• Dòng thứ hai cho biết diện tích ban đầu của ~n~ hòn đảo lần lượt là ~w_1,w_2,...,w_n~ ~(w_i \le 10^9)~
• ~m~ dòng tiếp theo cho biết thứ tự và thông tin các cây cầu được xây sẵn, cây cầu thứ ~j~ nối giữa hai hòn đảo là ~u_i~ và ~v_j~.
• ~q~ dòng tiếp theo cho biết thầy hiệu trưởng yêu cầu AP sử dụng thần chú ~C~ ~i~ ~W~ hoặc ~D~ ~j~.

Output

• ~q~ dòng được in ra là câu trả lời cho yêu cầu của thầy hiệu trưởng, vì thầy hiệu trưởng là một người thông thái cho nên khi đặt câu hỏi cho AP thì luôn có câu trả lời cho câu hỏi đó.

Subtask

• Có ~30\%~ số test chứa ~n,m,q \le 5000~.
• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

6 6 8
8 2 1 8 3 7 
4 3
4 2
3 4
6 1
4 3
4 3
D 5
D 4
C 5 8
D 3
C 2 8
C 5 1
C 6 1
D 2

Sample Output 1

15
11
11
11
17
17
17
9

Hành tinh Marvelous Land gồm ~N~ thành phố, được kết nối với nhau bởi ~M~ tuyến đường hai chiều. Giữa hai thành phố chỉ có tối đa một tuyến đường nối chúng và không có tuyến đường nào nối một thành phố tới chính nó. Các thành phố được đánh số từ 1 tới ~N~. Trong đó có 2 thành phố là trung tâm kinh tế quan trọng là thành phố 1 và thành phố ~N~. Tuyến đường thứ ~i~ cho phép đi lại giữa hai thành phố ~u_i~ và ~v_i~ với ~t_i~ đơn vị thời gian. Một ngày nọ, người dân Marvelous Land khảo sát các con đường và nhận thấy cần nâng cấp mạng lưới đường hiện có, hoặc xây thêm một số tuyến đường hai chiều. Điều cần quan tâm nhất là tổng thời gian ngắn nhất để đi lại giữa 2 thành phố trung tâm kinh tế. Trước khi quyết định nâng cấp mạng lưới đường đi, cần xác định các tuyến đường trọng yếu là những tuyến đường mà không thể không đi qua khi muốn đi từ thành phố 1 tới thành phố ~N~ với tổng thời gian ngắn nhất.

Yêu cầu: Hãy viết chương trình đếm số lượng tuyến đường trọng yếu.

Input

• Dòng đầu chứa hai số nguyên ~N~ và ~M~ (~1 \le N \le 10^5, 1 \le M \le 2 × 10^5~), số thành phố và số tuyến đường.
• ~M~ dòng tiếp theo, mỗi dòng ghi ba số nguyên, dòng thứ ~i+1~ ghi số ~u_i, v_i, t_i~ (~1 \le u_i, v_i \le N, 1 \le t_i \le 10^6~) là các thông tin của tuyến đường thứ ~i~.

Output

• Ghi ra duy nhất một số nguyên là số tuyến đường trọng yếu.

Subtask

• 50% số điểm của bài tương ứng với các test có ~N \le 1000~ và ~M \le 1000~

Sample Input 1

8 9
1 2 3
1 3 1
2 4 4
3 4 7
5 4 9
8 6 5
8 7 4
6 5 2
7 5 3

Sample Output 1

3

Cho bảng số ~A~ kích thước ~n*m~, các hàng được đánh số từ trên xuống dưới, các cột được đánh số từ trái sang phải. Ô giao giữa hàng ~i~ cột ~j~ là ô ~(i,j)~ và có giá trị ~a(i,j)~. Hai ô có thể di chuyển tới nhau nếu chúng chung cạnh. Một đường đi sẽ bao gồm các ô sao cho hai ô liên tiếp chung cạnh, và nó có giá trị bằng tổng giá trị các ô trên đường đi.

Cho ~q~ truy vấn, truy vấn thứ ~i~ sẽ cho bạn hai ô ~(x,y)~ và ~(u,v)~ trong bảng. Kết quả của một truy vấn chính là giá trị của đường đi có trọng số nhỏ nhất giữa hai ô đã cho. Hãy in ra kết quả của từng truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~, ~(1 \le n \le 7; 1 \le m \le 5000)~.
• Tiếp theo là ~n~ dòng, mỗi dòng gồm ~m~ số nguyên không âm miêu tả bảng ~A~ ~n*m~, ~(0 \le a(i,j) \le 10^5)~ .
• Dòng tiếp theo là số nguyên dương ~q~, ~(q \le 30000)~.
• Ở ~q~ dòng tiếp theo mỗi dòng miêu tả một truy vấn, truy vấn thứ ~i~ có dạng ~x_i, y_i, u_i, v_i~ miêu tả ô ~(x_i,y_i)~ và ~(u_i,v_i)~. (Các ô đều nằm trong bảng).

Output

• In ra ~q~ dòng là kết quả của ~q~ truy vấn.

Sample Test

Input:

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

Output:

5
9

Xe buýt là một phương tiện giao thông phổ biến tại thành phố mà Alice sinh sống bởi tính tiện dụng và giá cả hợp lý của nó. Thành phố có ~n~ bến xe buýt được đánh số từ ~1~ tới ~n~ và có ~m~ tuyến xe buýt hai chiều, mỗi tuyến đang được điều hành bởi một trong hai công ty vận tải ~A~ hoặc ~B~. Cụ thể, tuyến thứ ~i~ ~(1 \le i \le m)~ di chuyển giữa hai bến ui và vi với giá vé do công ty quản lý quy định là ~w_i~.

Lưu ý là giữa hai bến có thể có nhiều hơn một tuyến xe buýt. Hai công ty ~A~ và ~B~ đều có chính sách giảm giá vé cho những ai thường xuyên đi bằng xe buýt. Cụ thể, mỗi ngày công ty ~A~ sẽ chỉ thu số tiền bằng với giá vé lớn nhất trong tất cả các tuyến được điều hành bởi công ty ~A~ mà khách hàng đã đi trong ngày. Để cạnh tranh, công ty ~B~ cũng có chính sách tương tự: khách hàng sẽ chỉ phải trả số tiền bằng giá vé lớn nhất trong tất cả các tuyến thuộc công ty ~B~ mà người đó đã đi trong ngày.

Nhà Alice ở gần bến xe buýt ~s~ và nơi làm của Alice ở gần bến xe buýt ~t~ nên hàng ngày Alice đều phải đi lại giữa hai bến này thông qua các tuyến xe buýt.

Yêu cầu: Bạn hãy giúp Alice xác định số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~.

Input:

• Dòng đầu tiên chứa bốn số nguyên dương ~n, m, s~ và ~t~ ~(n, m \le 50000; s, t \le n; s \neq t)~;
• Dòng thứ ~i (1 \le i \le m)~ trong ~m~ dòng tiếp theo chứa bốn số nguyên dương ~c_i, u_i, v_i, w_i~ ~(u_i, v_i \le n; u_i \neq v_i; w_i \le 10^9)~ mô tả tuyến xe buýt thứ i trong đó ~c_i = 1~ nếu tuyến này được điều hành bởi công ty ~A~ hoặc ~c_i = 2~ nếu tuyến này được điều hành bởi công ty ~B~.

Các số trên cùng một dòng cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn tồn tại cách đi lại giữa hai bến xe buýt ~s~ và ~t~ thông qua ~m~ tuyến xe.

Output:

• In ra một số nguyên duy nhất là số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo được việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~ cho Alice.

Subtask

• Subtask ~1~ ~(30\%)~: tất cả xe buýt đều được điều hành bởi công ty ~A~.
• Subtask ~2~ ~(30\%)~: ~n,m \le 5000~
• Subtask ~3~ ~(40\%)~: không ràng buộc gì thêm.

Sample Input 1

6 7 1 4
1 1 2 4
2 2 3 7
1 3 4 6
2 1 6 5
1 6 5 5
2 5 4 8
2 2 5 2

Sample Output 1

12

Explanation 1

Để đi từ ~1~ tới ~4~, Alice đi tuyến ~(1,2)~ của công ty ~A~ và hai tuyến ~(2,5)~ và ~(5,4)~ của công ty ~B~. Khi đó Alice cần trả cho công ty ~A~ ~4~ và công ty ~B~ ~8~ đơn vị tiền.

Một công ty có ~n~ văn phòng được đánh số từ ~1~ đến ~n~. Công ty này muốn lắp đặt một vài đường dây liên lạc hai chiều giữa các văn phòng, sao cho giữa mọi cặp văn phòng ~i, j~ (~i \neq j~) tồn tại ít nhất một đường liên lạc giữa chúng.

Có ~k~ nhà mạng cung cấp tổng cộng ~m~ đường dây liên lạc, trong đó đường dây thứ ~i~ kết nối văn phòng ~u_i~ và văn phòng ~v_i~, được vận hành bởi nhà mạng ~c_i~ và mất chi phí ~p_i~ đồng† để lắp đặt (lưu ý mỗi cặp văn phòng có thể có đường dây của nhiều nhà mạng).

Ngoài ra, để tăng tính cạnh tranh, cả ~k~ nhà mạng đều đang tổ chức chương trình tri ân khách hàng; cụ thể, nếu tổng chi phí lắp đặt mà công ty trả cho nhà mạng thứ ~j~ vượt quá ~s_j~ đồng, nhà mạng ~j~ sẽ giảm giá 50 % cho phần chi phí chênh lệch, nghĩa là công ty sẽ chỉ phải trả
~ x_j - \frac{\max(0,\,x_j - s_j)}{2} ~ đồng, với ~x_j~ là tổng chi phí trước khi áp dụng khuyến mãi.

Hãy tìm cách dựng mạng lưới liên lạc sao cho tổng chi phí là nhỏ nhất có thể. Vì ta có thể chứng minh là tổng chi phí nhỏ nhất nhân 2 là một số nguyên, bạn cần in ra tổng chi phí nhỏ nhất nhân 2.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, m, k~ (~2 \le n \le 1000~, ~n - 1 \le m \le 5\cdot 10^5~, ~1 \le k \le 10~) — số lượng văn phòng của công ty, số lượng đường dây có thể lắp đặt, và số lượng nhà mạng.
• Tiếp theo là ~m~ dòng, mỗi dòng gồm bốn số nguyên dương ~u_i, v_i, c_i, p_i~ (~1 \le u_i, v_i \le n~, ~u_i \neq v_i~, ~1 \le c_i \le k~, ~1 \le p_i \le 10^9~), mô tả đường dây thứ ~i~.
• Dòng cuối cùng gồm ~k~ số nguyên dương ~s_1, s_2, \dots, s_k~ (~1 \le s_j \le 10^9~), mô tả chi tiết chương trình tri ân khách hàng của ~k~ nhà mạng.

Đảm bảo tồn tại ít nhất một cách dựng mạng lưới liên lạc kết nối tất cả ~n~ văn phòng.

Output

In ra một số nguyên là tổng chi phí nhỏ nhất để dựng mạng lưới liên lạc nhân 2.

Sample Input 1

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

Sample Output 1

13

Sample Input 2

5 7 3
1 5 3 100
1 2 1 5
4 5 1 5
1 3 2 7
2 3 3 10
1 2 2 4
4 5 2 4
5 20 100

Sample Output 2

225