Có ~N~ chiếc rương kho báu, chiếc rương thứ ~i~ có giá trị là ~C_i~. Ban đầu, có ~K~ chìa khóa. Chiếc chìa khóa thứ ~i~ có thể được dùng để mở một trong hai chiếc rương ~A_i~ và ~B_i~ (lưu ý là không thể dùng chiếc chìa thứ ~i~ để mở cả hai rương ~A_i~ và ~B_i~). Mỗi chiếc rương chỉ có thể được mở khóa một lần, và không nhất thiết phải sử dụng tất cả các chìa khóa.

Cho ~K~ truy vấn, truy vấn thứ ~i~ yêu cầu bỏ đi chiếc chìa khóa thứ ~P_i~ (các chìa khóa không được đánh số lại sau các truy vấn). Sau mỗi truy vấn, hãy cho biết: giả sử ta dùng các chìa khóa còn lại để mở rương, thì với cách mở khóa rương tối ưu, tổng giá trị kho báu lớn nhất thu được từ các rương được mở là bao nhiêu.

Input

Dòng đầu tiên gồm hai số nguyên ~N, K~ (~2 ≤ N ≤ 200000, 1 ≤ K ≤ 200000~) — số rương kho báu, số chìa khóa đồng thời là số truy vấn.

Dòng tiếp theo, gồm ~N~ số nguyên ~C_1, C_2, . . . , C_N~ (~1 ≤ C_i ≤ 10^9~) — giá trị của các rương kho báu.

~K~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~A_i~ và ~B_i~ (~1 ≤ A_i, B_i ≤ N, A_i ̸= B_i~) — mô tả chiếc chìa khóa thứ ~i~ . Dòng tiếp theo, gồm ~K~ số nguyên phân biệt ~P_1, P_2, . . . , P_K~ (~1 ≤ P_i ≤ K~) — mô tả các truy vấn.

Output

In ra ~K~ dòng, dòng thứ ~i~ gồm một số nguyên là tổng giá trị kho báu lớn nhất thu được sau khi thực hiện truy vấn thứ ~i~.

Test mẫu

Input

4 4
9 5 7 2
1 2
2 3
3 1
1 4
4 1 2 3

Output

21
16
9
0

Giải thích: Sau truy vấn thứ nhất, còn lại các chìa khóa 1, 2 và 3. Ta có thể dùng chìa 1 để mở rương 2, chìa 2 để mở rương 3 và chìa 3 để mở rương 1. Tổng giá trị của các rương được mở là 9 + 5 + 7 = 21.

Sau truy vấn thứ hai, còn lại các chìa khóa 2 và 3. Ta có thể dùng chìa 2 để mở rương 3, chìa 3 để mở rương 1. Tổng giá trị của các rương được mở là 9 + 7 = 16.

Sau truy vấn thứ ba, chỉ còn lại chìa khóa 3. Ta dùng chìa khóa này để mở rương 1 với giá trị 9.

Sau truy vấn thứ tư, ta không còn chiếc chìa khóa nào nên không mở được bất kì rương kho báu nào.

Scoring

Subtask 1 (~20\%~ số điểm): ~N, K ≤ 16~

Subtask 2 (~30\%~ số điểm): ~N, K ≤ 2000~

Subtask 3 (~50\%~ số điểm): Không có ràng buộc gì thêm

Trên trục tọa độ ~Ox~ có ~n~ điểm xanh và ~n~ điểm đỏ. Điểm xanh thứ ~i~ có tọa độ ~b_i~, điểm đỏ thứ ~i~ có tọa độ ~r_i~.

Với hai điểm có tọa độ ~x_1~ và ~x_2~, ta định nghĩa khoảng cách giữa hai điểm đó là ~|x_2 - x_1|~.

Hãy tìm khoảng cách nhỏ nhất giữa một cặp điểm xanh và điểm đỏ bất kì trong số các điểm đã cho.

Input

Dòng đầu tiên gồm số nguyên ~n~ (~1 ≤ n ≤ 10^5~) - số điểm xanh và cũng là số điểm đỏ.

Dòng thứ hai gồm ~n~ số nguyên ~b_1, b_2, . . . , b_n~ (~1 ≤ b_i ≤ 10^9~) tọa độ của điểm xanh

Dòng thứ ba gồm ~n~ số nguyên ~r_1, r_2, . . . , r_n~ (~1 ≤ r_i ≤ 10^9~) tọa độ của điểm đỏ

Output

In ra khoảng cách nhỏ nhất giữa một cặp điểm xanh và điểm đỏ bất kì.

Test mẫu

Input

1
2
6

Output

4

Input

2
1 7
10 5

Output

2

Scoring

Subtask 1 (~50\%~ số test): ~n ≤ 1000~

Subtask 2 (~50\%~ số test): Không có giới hạn gì thêm

Bạn đến chơi tại một sòng bạc tên M và bạn bị cuốn vào trò chơi slot machine.

Trò chơi có thể được mô tả như sau: Một máy slot gồm 3 trống quay, mỗi trống quay được chia thành N phần bằng nhau, mỗi phần được in vào đó những biểu tượng khác nhau. Có đúng N biểu tượng, mỗi biểu tượng xuất hiện đúng một lần trên mỗi trống quay. Để đơn giản, chúng ta biểu diễn các biểu tượng bằng các số từ 1 đến N. Hình vẽ bên dưới minh họa 3 trống quay với N = 5.

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

Sau khi nhấn nút, mỗi trống sẽ độc lập quay. Sau khi các trống dừng quay, kết quả của người chơi phụ thuộc vào số lượng các hàng ngang có cả 3 biểu tượng cùng màu. Hãy xác định số lượng hàng tối đa như vậy.

Input

Dòng đầu tiên ghi số nguyên ~N~ là số lượng biểu tượng (~1 ≤ N ≤ 300000~).

Ba dòng tiếp theo, mỗi dòng mô tả các biểu tượng được in trên mỗi trống quay. Mỗi dòng có dạng ~a_1, a_2, . . . , a_N~ (~1 ≤ a_i ≤ N~), các số này phân biệt.

Output

dòng tối đa có ba biểu tượng giống nhau trong cùng 1 lúc

Test mẫu

Input

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

Output

3

Scoring

Subtask 1 (~30\%~ số điểm): ~N ≤ 100~

Subtask 2 (~30\%~ số điểm): ~N ≤ 10000~

Subtask 3 (~40\%~ số điểm): Không có ràng buộc gì thêm

Tính SoD một số nguyên dương sẽ được thể hiện bởi chuỗi công việc sau:

• Bước 1: Tính tổng các chữ số của số đó. • Bước 2: Kiểm tra nếu kết quả là một số có nhiều hơn hai chữ số thì ta sẽ thực hiện lại chuỗi công việc này cho tới khi kết quả là 1 chữ số.

Ví dụ: ~901 → 9 + 0 + 1 = 10 → 1 + 0 = 1~. Do vậy ~SoD(901) = 1~.

Bạn được cho một số nguyên dương ~N~, bạn hãy tính SoD của ~N~ giai thừa (~SoD(N!)~).

Input

Dòng thứ nhất chứa số nguyên ~T~ (~1 ≤ T ≤ 10^5~) - số lượng test.

~T~ dòng tiếp theo mỗi dòng sẽ chứa một số nguyên ~N~ (~0 ≤ N ≤ 10^{18}~)

Output

Gồm ~T~ số nguyên là kết quả của bài toán

Test mẫu

Input

4
1
3
5
13

Output

1
6
3
9

Giải thích Ở 2 ví dụ đầu, ta có thể thấy kết quả của 1! và 3! đều đã là số có một chữ số: 1; 6.

Ở ví dụ thứ ba, SoD(5!) = 1 + 2 + 0 = 3.

Scoring

T sẽ không có ràng buộc cho các subtask.

Subtask 1 (~20\%~ số test): ~0 ≤ N ≤ 10.~

Subtask 2 (~80\%~ số test): Không ràng buộc gì thêm.

Đất nước Avalon có ~N~ ngọn đồi xếp liên tiếp nhau. Quốc vương của Avalon đang muốn tăng cường sức mạnh quân sự của đất nước mình. Một trong những chỉ số được quốc vương quan tâm là mức chênh lệch độ cao lớn nhất giữa hai ngọn đồi liên tiếp, được gọi là độ nguy hiểm.

Quốc vương muốn độ nguy hiểm là nhỏ nhất có thể. Để làm được điều đó, quốc vương có thể thay đổi độ cao của nhiều nhất ~K~ ngọn đồi thành độ cao bất kì nguyên dương. Bạn hãy tính toán giúp quốc vương độ nguy hiểm nhỏ nhất có thể đạt được!

Input

Dòng đầu tiên chứa số nguyên dương ~T~ (~T ≤ 500~) cho biết số bộ test.

Mỗi bộ test được mô tả bằng 2 dòng:

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ (~1 ≤ K ≤ N ≤ 2 × 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~h_i~ (~1 ≤ i ≤ N, 1 ≤ h_i ≤ 10^9~) cho biết độ caoban đầu của N ngọn đồi.

Tổng ~N~ trong tất cả bộ test không vượt quá ~2 × 10^5~

Output

Với mỗi bộ test, in ra một dòng chứa độ nguy hiểm nhỏ nhất có thể đạt được với bộ test đó.

Test mẫu

Input

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

Output

2
0

Scoring

Subtask 1 (~40\%~ số điểm): Tổng N trong tất cả bộ test không vượt quá 5000.

Subtask 2 (~60\%~ số điểm): Không có ràng buộc gì thêm.

Có ~n~ chiếc cột xếp thành 1 hàng với độ cao của các cột lần lượt là ~h_1, h_2, ..., h_n~.

Bây giờ, bạn cần xây một bể chứa nước thoả mãn các điều kiện sau:

• Hai thành của bể nước (thành bên trái và thành bên phải) là 2 trong ~n~ cột có sẵn • Giả sử 2 cột được chọn làm thành bể là cột ~i~ và cột ~j~ thì lượng nước chứa được là: ~min(h_i, h_j) × (|j - i| - 1)~

Do phải làm việc căng thẳng nên nhu cầu về nước của bạn khá lớn. Do đó, bạn muốn chọn cách dựng bể để chứa được nhiều nước nhất có thể.

Input

Dòng thứ nhất ghi số ~n~ là số cột cho sẵn (~2 ≤ n ≤ 10^5~)

Dòng thứ hai ghi ~n~ số ~h_1, h_2, ..., h_n~(~0 ≤ h_i ≤ 10^9~)

Output

Một dòng duy nhất in lượng nước lớn nhất mà bể nước có thể chứa được.

Test mẫu

Input

5
6 3 7 5 2

Output

10

Scoring

Subtask 1 (~50\%~ số test): ~n ≤ 1000~

Subtask 2 (~50\%~ số test): Không có ràng buộc gì thêm