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

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm ~n~ đỉnh và ~n-1~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~, đỉnh thứ ~i~ có trọng số là ~w_i~.

Chắc hẳn các bạn đều biết khái niệm về cây con, giả sử ta có một cây có gốc là ~1~ như sau:

• Cây con có gốc là ~2~ sẽ bao gồm các đỉnh : ~\{2,6,5,4\}~.
• Cây con có gốc là ~3~ sẽ bao gồm các đỉnh : ~\{3\}~.

Ta định nghĩa ~S(root,a)~ là tổng trọng số các đỉnh trong cây con gốc ~a~ khi gốc của cây là ~root~. Hay ~S(root,a) = \sum_u^{u \in subtree(a)} w[u]~ khi gốc của cây là ~root~.

Bạn cần trả lời ~q~ câu hỏi, mỗi câu hỏi có dạng như sau:

• ~a~ ~b~ : Hãy in ra ~S(a,b)~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~ ~(n,q \le 2 \times 10^5)~ miêu tả số đỉnh và số truy vấn.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~w~ ~(1 \le w_i \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~u_i~ và ~v_i~ miêu tả cạnh ~(u_i,v_i)~ của cây ~(1 \le u_i,v_i \le n)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~a_i,b_i~ ~(1 \le a_i,b_i \le n)~ miêu tả truy vấn tương ứng.

Output:

• Với mỗi truy vấn, in ra đáp án tương ứng.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~n,q \le 2000~
• Subtask ~2~ (~25\%~ số điểm): ~a_i = 1~ với mọi truy vấn.
• Subtask ~3~ (~25\%~ số điểm): ~b_i = 1~ với mọi truy vấn.
• Subtask ~4~ (~25\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

10
6
12
3

Explanation 1

Đối với hai truy vấn đầu tiên, gốc của cây bằng ~1~.

• ~S(1,2) = w[2] + w[6] + w[5] + w[4] = 10~
• ~S(1,6) = w[6] + w[5] = 6~

Đối với truy vấn thứ ba, gốc của cây bằng ~4~:

• ~S(4,2) = w[2] + w[6] + w[5] + w[1] + w[3] = 12~

Đối với truy vấn thứ tư, gốc của cây bằng ~2~

• ~S(2,1) = w[1] + w[3] = 3~

Cho một cây gồm ~n~ đỉnh gồm ~n-1~ cạnh. Cạnh thứ ~i~ có dạng ~(u_i,v_i, w_i)~, kết nối đỉnh ~u_i~ với đỉnh ~v_i~ và có độ dài là một số nguyên dương ~w_i~.

Gọi ~D(u,v)~ là khoảng cách giữa hai đỉnh ~u~ và ~v~ trên cây (được tính bằng tổng trọng số trên cạnh mà đường đi từ ~u~ tới ~v~ đi qua). Ta có hàm ~S(i)~ là tổng khoảng cách từ ~i~ tới tất cả các đỉnh trên cây:

• ~S(i) = \sum_{u=1}^{n} D(i,u)~.

Với mỗi đỉnh ~u~ trên cây, bạn được phép thử gán giá trị của một cạnh bất kì trên cây bằng ~0~ (tức là gán một giá trị ~w_i = 0~), sao cho giá trị ~S(u)~ mới, ta tạm gọi là ~S(u)'~ là nhỏ nhất có thể. Lưu ý rằng, mỗi lần thử là độc lập với nhau, ta không thực sự gán cạnh nào bằng ~0~ trong cây gốc cả.

Để tránh biến bài toán quá khó, với mỗi lần thử, các bạn không cần in ra ~S(u)'~, mà chỉ cần in ra độ chênh lệch giữa hai giá trị cũ và mới, nói cách khác in ra ~S(u) - S(u)'~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 3 \times 10^5)~
• ~n-1~ dòng sau, dòng thứ ~i~ gồm ba số nguyên dương ~(u_i,v_i,w_i)~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^6)~ miêu tả cạnh thứ ~i~ của cây.

Output:

• Gồm một dòng gồm ~n~ số nguyên, số thứ ~i~ là ~S(i)~ nhỏ nhất thu được nếu ta thử gán tối ưu nhất có thể.

Subtask:

• Subtask ~1~ (~20\%~ số điểm): ~n \le 200~.
• Subtask ~2~ (~20\%~ số điểm): ~u_i = i, v_i = i+1~ ~\forall i \in [1,n-1]~.
• Subtask ~3~ (~20\%~ số điểm): ~w_i = 1~ với mọi ~i~ và ~n \le 2000~.
• Subtask ~4~ (~20\%~ số điểm): ~w_i = 1~ với mọi ~i~.
• Subtask ~5~ (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

6 8 6 6 30 15

Explanation 1

Đối với đỉnh ~1~, giả sử ta gán cạnh ~(3,5) = 0~, ta sẽ giảm được ~S(1)~ đi một lượng là ~6~ của ~D(5,1)~.

Đối với đỉnh ~2~, giả sử ta gán cạnh ~(1,2) = 0~, ta sẽ giảm được ~S(2)~ đi một lượng là ~8~.

Với đỉnh ~5~, cách gán tối ưu nhất là gán ~(3,5) = 0~.

Với đỉnh ~6~, ta gán ~(2,6) = 0~ để thu được kết quả là giảm đi ~15~ đơn vị.

Cho đồ thị đầy đủ gồm ~N~ đỉnh. Một đồ thị đầy đủ được định nghĩa là một đồ thị vô hướng gồm ~N~ đỉnh và ~\frac{N \times (N - 1)}{2}~ cạnh.

Các đỉnh được đánh số từ ~1~ đến ~N~. Đỉnh thứ ~i~ có trọng số là ~a_i~.

Trong đồ thị này, có sẵn ~M~ cạnh phân biệt có trọng số bằng ~0~. Cạnh thứ ~i~ nối hai đỉnh ~u_i~ và ~v_i~.

Các cạnh còn lại, tức cạnh nối hai đỉnh ~x~ và ~y~, sẽ có trọng số là:

~|a_x - a_y|~

Với mọi đỉnh ~i~, hãy tìm độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~i~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N, M~
  ~(N \le 3 \times 10^5, M \le \min(\frac{N \times (N - 1)}{2}, 10^5))~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_i~
  ~(a_i \le 10^9, 1 \le i \le N)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~, mô tả cạnh ~(u_i, v_i)~ có trọng số bằng ~0~.

Output

• Gồm ~N~ dòng, dòng thứ ~i~ chứa một số nguyên là độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~i~.

Sample Input

7 3
4 9 1 10 5 7 15
1 5
5 7
2 7

Sample Output

0
0
3
1
0
2
0

Ràng buộc

Mrtee đang nghiên cứu về tổ kiển, mô hình đó được mổ phong trên một lưới ô vuông ~n×m~ bao gồm ~k~ ô ~(x_i,y_i)~. Các ô này có cấu trúc giống dạng cây, với hai ô kề cạnh bất kì có thể di chuyển tới nhau, và hai ô bất kì cũng có thể đi tới nhau theo một đường đi duy nhất. Mrtee đang quan tâm đến việc xét một hình chữ nhật ~(x_1,y_1,x_2,y_2)~ và nếu ta chỉ xét các ô thuộc tổ kiến nằm bên trong hình chữ nhật này thì sẽ có bao nhiêu thành phần liên thông.

Sẽ có ~q~ truy vấn có dạng như vậy.

Yêu cầu: cho dữ liệu về tổ kiến và ~q~ truy vấn, mỗi truy vấn là một hình chữ nhật, hãy đếm số thành phần liên thông trong hình chữ nhật đó.

Input

• Dòng đầu chứa hai số nguyên ~n,m~ (~1≤n,m≤2⋅10^5~ )
• Dòng thứ hai chứa số nguyên ~k,q~ (~2≤k≤2⋅10^5,1≤q≤2⋅10^5~).
• ~k-1~ dòng tiếp theo, mỗi dòng chứa ~f_i,x_i,y_i~ mô tả ô (~x_i,y_i~) thuộc tổ kiến kết nối với ô (~x_i+1,y_i~ ) nếu ~f_i= h~, hoặc kết nối với ô ~(x_i,y_i+1)~ nếu ~f_i=v~ (~1≤x_i≤n,1≤y_i≤m~). Dữ liệu đảm bảo các ô này tạo thành một cây.
• ~q~ dòng tiếp theo mỗi dòng chứa bốn số ~x_1,y_1,x_2,y_2~ (~1≤x_1≤x_2≤n,1≤y_1≤y_2≤m~). Các ô (~x,y~) được coi là nằm trong hình chữ nhật thỏa mãn ~x_1≤x≤x_2,y_1≤y≤y_2~.

Output

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

Subtask

• 20% số test có ~n,m,k,q≤100~
• 20% số test có ~n,m,k,q≤3000~
• 30% số test có ~n,m≤3000,k,q≤10^5~
• 30% số test còn lại không có ràng buộc gì thêm.

Example

Input 1

4 3
8 5
h 1 1
v 2 1
v 1 1
h 3 1
v 2 2
h 2 1
h 1 3
3 3 4 4
3 2 4 3
1 2 3 3
1 1 4 4
1 1 4 3

Output 1

0
0
2
1
1

Tuấn sống trên một cái cây khổng lồ cùng bộ lạc của mình.

Cái cây này được biểu diễn bởi một cây gồm ~N~ đỉnh và ~N - 1~ cạnh. Mỗi đỉnh ~i~ có một màu ~c_i~.

Trong một bước di chuyển, Tuấn có thể đi từ đỉnh hiện tại ~u~ sang một đỉnh ~v~ nếu thỏa mãn một trong hai điều kiện sau:

• Có cạnh nối trực tiếp giữa ~u~ và ~v~.
• Hai đỉnh ~u~ và ~v~ có cùng màu, tức là ~c_u = c_v~.

Có ~Q~ câu hỏi, mỗi câu hỏi gồm hai đỉnh ~a~ và ~b~. Với mỗi câu hỏi, hãy tìm số bước ít nhất để Tuấn di chuyển từ đỉnh ~a~ đến đỉnh ~b~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N, Q~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~c_1, c_2, \ldots, c_N~, trong đó ~c_i~ là màu của đỉnh ~i~.
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~, mô tả một cạnh nối giữa hai đỉnh ~u~ và ~v~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a, b~, mô tả một truy vấn.

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ là đáp án của truy vấn thứ ~i~.

Ràng buộc

• ~1 \le c_i \le 10^5~
• ~1 \le Q \le 10^5~
• ~1 \le u, v, a, b \le N~

Subtask

Sample Input

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

Sample Output

2
1
2
2

Giải thích ví dụ

Cây có ~5~ đỉnh với màu lần lượt là:

~c = [1, 2, 1, 2, 2]~

• Truy vấn từ ~3~ đến ~5~: có thể đi ~3 \to 1 \to 5~, mất ~2~ bước.
• Truy vấn từ ~1~ đến ~2~: có cạnh trực tiếp ~1 - 2~, mất ~1~ bước.
• Truy vấn từ ~4~ đến ~3~: có thể đi ~4 \to 2 \to 3~, mất ~2~ bước.
• Truy vấn từ ~1~ đến ~4~: có thể đi ~1 \to 2 \to 4~, mất ~2~ bước.

Bài đồ thị siêu cơ bản nên đề bài vô cùng ngắn gọn:

Quân có một đồ thị đầy đủ, vô hướng, có trọng số gồm ~n~ đỉnh. Trọng số của đỉnh thứ ~i~ là ~a_i~. Trọng số của cạnh nối giữa đỉnh ~u~ và đỉnh ~v~ là ~\frac{a_u + a_v}{gcd(a_u, a_v)}~. Cảm giác bài chưa đủ khó nên Quân vẽ thêm ~m~ cạnh nối nữa. Cạnh thứ ~i~ nối giữa hai đỉnh ~u_i~ và ~v_i~, và có trọng số là ~w_i~.

Hãy tính độ dài đường đi ngắn nhất từ đỉnh ~1~ tới mỗi đỉnh còn lại.

Input

• Dòng đầu chứa hai số nguyên không âm ~n, m~ ~(1 \le n \le 10^5, 0 \le m \le 10^4)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^5)~.
• ~m~ dòng cuối cùng, dòng thứ ~i~ chứa ba số nguyên dương ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^5)~.

Output

• In ra ~n~ số nguyên không âm, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 1000~
• Subtask ~2~ (~20\%~ số điểm): Dãy ~a~ đôi một giống nhau
• Subtask ~3~ (~20\%~ số điểm): ~m = 0; \ a_i \le 50 \ \forall i \in [1, n]~
• Subtask ~4~ (~20\%~ số điểm): ~m = 0~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

3 1
1 2 3
2 3 1

Sample output 1

0 3 4

Vùng đất Ams có ~n~ thành phố tạo thành cấu trúc cây. Bạn đang chơi game nhập vai ở vùng đất này. Thành phố thứ ~i~ có NPC sẽ đưa cho bạn nhiệm vụ cấp độ ~a_i~.

Thành phố tân thủ là thành phố ~1~, có NPC phát nhiệm vụ cấp độ thấp nhất: cấp độ ~1~. Thành phố đích đến là thành phố ~n~, có NPC phát nhiệm vụ cấp độ cao nhất: cấp độ ~m~. Mỗi ngày, bạn có thể di chuyển từ thành phố hiện tại tới một thành phố kề nó.

Để vượt qua trò chơi, bạn cần tìm một lộ trình để hoàn thành tất cả ~m~ cấp độ nhiệm vụ của NPC, cụ thể như sau:

• Với mỗi cấp độ từ ~2~ đến ~m-1~, bạn cần chọn ra một thành phố có NPC cung cấp nhiệm vụ cấp độ đó. Gọi các thành phố mà bạn muốn đến để hoàn thành các nhiệm vụ đó lần lượt là ~u_2, u_3, …, u_{m-1}~. Đồng thời, gọi ~u_1 = 1, u_m = n~.
• Di chuyển từ ~u_1~, đi đến ~u_2~, rồi đến ~u_3~, …, cuối cùng đến ~u_m~ để lần lượt hoàn thành các nhiệm vụ ở các thành phố này.
• Để di chuyển giữa hai thành phố, bạn luôn lựa chọn sử dụng cách đi tốn ít thời gian nhất (đường đi ngắn nhất giữa hai thành phố đó trên cây). Bạn có thể đi qua thành phố có nhiệm vụ cấp cao để di chuyển giữa các thành phố cấp độ thấp hơn, tuy nhiên khi đó bạn vẫn chưa được tính là hoàn thành nhiệm vụ cấp cao.
• Thời gian hoàn thành của lộ trình này là tổng số ngày để di chuyển giữa các thành phố.

Có rất nhiều cách chọn ra lộ trình các thành phố ~u_1, u_2, …, u_m~ như vậy để hoàn thành trò chơi. Là một người nghiện game ham học hỏi, Quân muốn khám phá hết các cách hoàn thành trò chơi. Do đó, Quân nhờ bạn tính xem, tổng thời gian để hoàn thành của tất cả các lộ trình hoàn thành được trò chơi là bao nhiêu. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le m \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le m; \ a_1 = 1; \ a_n = m)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ ~(1 \le u, v \le n)~ mô tả các cạnh của cây.

Output:

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

Subtask:

• Subtask ~1~ (~20\%~ số điểm): ~n \le 20~
• Subtask ~2~ (~20\%~ số điểm): ~n \le 100~
• Subtask ~3~ (~20\%~ số điểm): ~n \le 5000~
• Subtask ~4~ (~20\%~ số điểm): Cây có dạng đường thẳng
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

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

Sample Output 1

24

Explaination

Số màu đỏ ở dưới mỗi thành phố là cấp độ của nhiệm vụ ở thành phố đó. Các lộ trình để hoàn thành trò chơi:

• ~1 → 2 → 3 → 6~. Thời gian di chuyển: ~dist(1, 2) + dist(2, 3) + dist(3, 6) = 2 + 1 + 1 = 4~
• ~1 → 2 → 4 → 6~. Thời gian di chuyển: ~dist(1, 2) + dist(2, 4) + dist(4, 6) = 2 + 2 + 2 = 6~
• ~1 → 5 → 3 → 6~. Thời gian di chuyển: ~dist(1, 5) + dist(5, 3) + dist(3, 6) = 3 + 2 + 1 = 6~
• ~1 → 5 → 4 → 6~. Thời gian di chuyển: ~dist(1, 5) + dist(5, 4) + dist(4, 6) = 3 + 3 + 2 = 8~

Vậy đáp án là ~4 + 6 + 6 + 8 = 24~