Trong tiệc tất niên cuối năm, gia đình Alice chuẩn bị một bàn tiệc lớn để chào đón mọi người. Trên bàn có ~N~ đĩa thức ăn được bày biện đẹp mắt thành một hàng, được đánh số từ ~1~ tới ~N~ từ trái sang phải. Đĩa thứ ~i~ (~1 \leq i \leq N~) có độ hấp dẫn là một số nguyên dương ~A_i~.

Với một đoạn gồm ~M~ đĩa ở vị trí liên tiếp của bàn tiệc có độ hấp dẫn tương ứng là dãy (~B_1, B_2, ..., B_M~), Alice định nghĩa độ đa dạng của dãy đó là số lượng dãy khác nhau có thể nhận được bằng cách thực hiện không quá một phép đảo ngược trên dãy. Một phép đảo ngược là việc chọn một cặp chỉ số ~(L, R)~ với ~1 \leq L < R \leq M~ và thực hiện đảo ngược dãy (~B_L, B_{L + 1}, ..., B_{R - 1}, B_{R}~) thành dãy ~(B_R, B_{R - 1}, ..., B_{L + 1}, B_L~), các phần tử còn lại giữ nguyên. Hai dãy (~X_1, X_2, ..., X_M~) và (~Y_1, Y_2, ..., Y_M~) được xem là khác nhau nếu tồn tại chỉ số ~i~ (~1 \leq i \leq M~) sao cho ~X_i \neq Y_i~. Ví dụ, dãy (~3, 1, 3~) có độ đa dạng bằng ~3~ vì có thể tạo được 3 dãy khác nhau với không quá một phép đảo ngược: (~3, 1, 3~), (~1, 3, 3~), (~3, 3, 1~).

Trong buổi tiệc, có ~Q~ vị khách lần lượt tới tham dự. Vị khách thứ ~j~ (~1 \leq j \leq Q~) đến và lấy chiếc đĩa thứ ~p_j~ để dùng bữa. Sau khi một chiếc đĩa được lấy ra, những chiếc còn lại giữ nguyên vị trí ban đầu và tạo thành các đoạn con ngăn cách bởi các vị trí trống do các đĩa đã được lấy đi. Alice tính độ đa dạng của mỗi đoạn con và muốn biết độ đa dạng lớn nhất trong số chúng.

Yêu cầu: Sau khi mỗi vị khách nhấc một chiếc đĩa đi, hãy tính độ đa dạng lớn nhất trong các đoạn con còn lại.

Input

Vào từ file văn bản TET.INP:

• Dòng đầu chứa hai số nguyên ~N~ và ~Q~ (~1 \leq Q < N \leq 2 \times 10^5~).

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ (~1 \leq A_i \leq 10^9~ với mọi ~i = 1, 2, ..., N~).

• Dòng thứ ~j~ trong số ~Q~ dòng tiếp theo chứa một số nguyên dương ~p_j~ (~1 \leq p_j \leq N~). Dữ liệu đảm bảo các giá trị ~p_j~ là khác nhau.

Output

Ghi ra file văn bản TET.OUT:

• Gồm ~Q~ dòng, mỗi dòng một số nguyên duy nhất là kết quả tìm được sau khi vị khách tương ứng nhấc một chiếc đĩa đi.

Scoring

Sample Input 1

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

Sample Output 1

9
2
2

Notes

• Sau khi lấy đĩa thứ ~2~, thu được hai đoạn con là (~4~) và (~3, 1, 3, 2, 1~), với độ đa dạng lần lượt là ~1~ và ~9~.

• Sau khi lấy đĩa thứ ~5~, thu được ba đoạn con là (~4~), (~3, 1~), và (~2, 1~), với độ đa dạng lần lượt là ~1~, ~2~ và ~2~.

• Sau khi lấy đĩa thứ ~6~, thu được ba đoạn con là (~4~), (~3, 1~), và (~1~), với độ đa dạng lần lượt là ~1~, ~2~ và ~1~.

Ông già Noel có một cây thông khổng lồ để trang hoàng cho đêm Giáng sinh. Trên các cành của cây thông, ông treo ~N~ tấm thiệp trang trí được đánh số từ ~1~ đến ~N~. Tấm thiệp ~i~ (~1 ≤ i ≤ N~) có độ lấp lánh được biểu thị bằng số nguyên không âm ~A_i~. Các tấm thiệp được kết nối với nhau bằng ~N - 1~ đoạn dây. Đoạn dây thứ ~i~ kết nối hai tấm thiệp ~u_i~ và ~v_i~ (~1 ≤ u_i, v_i ≤ N~). Hệ thống dây đảm bảo rằng giữa hai tấm thiệp bất kỳ trên cây luôn tồn tại duy nhất một đường đi trực tiếp kết nối hai tấm thiệp và các đoạn dây. Nói cách khác, các tấm thiệp và các đoạn dây tạo thành một đồ thị dạng cây có ~N~ đỉnh và ~N - 1~ cạnh.

Mỗi thời điểm trong đêm Giáng sinh, ông già Noel sẽ thực hiện một phép thuật. Có ~Q~ thời điểm lần lượt xảy ra đánh số từ ~1~ đến ~Q~. Tại thời điểm ~t~ (~1 ≤ t ≤ Q~), ông thực hiện một phép thuật được mô tả bằng ba số nguyên dương ~x_t, y_t, w_t~ với ý nghĩa: gán ~A_v = A_v \% w_t~ với mọi tấm thiệp ~v~ nằm trên đường kết nối từ tấm thiệp ~x_t~ đến tấm thiệp ~y_t~ (bao gồm cả ~x_t~ và ~y_t~). Sau khi thực hiện phép thuật, ông định nghĩa độ đẹp của cây tại thời điểm ~t~ là tổng độ đẹp của các tấm thiệp trên cây tại thời điểm đó, tức là: ~(A_1~ ~\%~ ~t) + (A_2~ ~\%~ ~t) + ... + (A_N~ ~\%~ ~t)~. Nhắc lại, ~\%~ là phép toán chia lấy dư.

Yêu cầu: Hãy giúp ông già Noel tính độ đẹp của cây sau mỗi lần thực hiện phép thuật.

Input

Vào từ file văn bản PINE.INP:

• Dòng đầu chứa hai số nguyên dương ~N~ và ~Q~ (~1 \le N, Q \le 2 \times 10^5~).

• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~0 \le A_i \le 2 \times 10^5~).

• Dòng thứ ~i~ trong số ~N - 1~ dòng tiếp theo chứa hai số nguyên dương phân biệt ~u_i~ và ~v_i~ mô tả một đoạn dây kết nối trực tiếp hai tấm thiệp ~u_i~ và ~v_i~ trên cây (~1 \le u_i, v_i \le N~).

• Dòng thứ ~t~ trong số ~Q~ dòng tiếp theo chứa ba số nguyên dương ~x_t, y_t, w_t~ mô tả một lần thực hiện phép thuật tại thời điểm ~t~ (~1 \le x_t, y_t \le N; w_t \le 2 \times 10^5~).

• Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản PINE.OUT:

• Gồm ~Q~ dòng, dòng thứ ~t~ chứa một số nguyên là độ đẹp của cây sau khi thực hiện phép thuật tại thời điểm ~t~.

Scoring

Sample Input 1

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

Sample Output 1

0
3
4

Notes

• Ở thời điểm ~t = 1~, dãy ~A~ là ~(2, 1, 4, 4, 3)~. Kết quả là ~(2~ ~\%~ ~t) + (1~ ~\%~ ~t) + (4~ ~\%~ ~t) + (4~ ~\%~ ~t) + (3~ ~\%~ ~t) = 0~.

• Ở thời điểm ~t = 2~, dãy ~A~ là ~(2, 1, 1, 1, 0)~. Kết quả là ~(2~ ~\%~ ~t) + (1~ ~\%~ ~t) + (1~ ~\%~ ~t) + (1~ ~\%~ ~t) + (0~ ~\%~ ~t) = 3~.

• Ở thời điểm ~t = 3~, dãy ~A~ là ~(2, 1, 0, 1, 0)~. Kết quả là ~(2~ ~\%~ ~t) + (1~ ~\%~ ~t) + (0~ ~\%~ ~t) + (1~ ~\%~ ~t) + (0~ ~\%~ ~t) = 4~.

Vào năm mới, ~K~ gia đình tổ chức cắm trại trên một khu đất có dạng hình tròn. Khu đất được biểu diễn trên hệ trục tọa độ Đề-các ~Oxy~ (đơn vị mét), có tâm ở gốc tọa độ ~O(0,0)~ và bán kính ~R = 100~ mét. Trên biên hình tròn, chọn ~K~ điểm phân biệt để làm vị trí cắm trại cho ~K~ gia đình. Các điểm được đánh số từ ~1~ đến ~K~ và được xác định bằng dãy góc ~\alpha_1, \alpha_2, \ldots, \alpha_K~ (~0^\circ \le \alpha_1 < \alpha_2 < \ldots < \alpha_K \le 359^\circ~), ~\alpha_i~ là góc từ tia ~Ox~ ngược chiều kim đồng hồ tới tia nối ~O~ đến điểm thứ ~i~. Cụ thể, điểm thứ ~i~ (~1 \le i \le K~) có tọa độ là ~\left( R \times \cos \frac{\alpha_i \times \pi}{180^\circ}, R \times \sin\frac{\alpha_i \times \pi}{180^\circ} \right)~, trong bài toán này lấy ~\pi = 3.14159265359~.

Alice nhận nhiệm vụ thiết kế đường dây để cấp điện cho tất cả các trại. Cụ thể, máy phát điện đặt ở trại ~1~, cần kết nối trại ~1~ tới ~K-1~ trại còn lại bằng dây điện. Trong quá trình thiết kế, được phép thêm tối đa ~25~ điểm trung gian để đấu nối nhưng các điểm này phải nằm trong hoặc trên biên của mảnh đất hình tròn. Các dây điện có thể đấu nối giữa hai trại, giữa một trại với một điểm trung gian, giữa hai điểm trung gian. Độ dài dây điện nối trực tiếp giữa hai điểm có tọa độ ~(x_1, y_1)~ và ~(x_2,y_2)~ là ~\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}~. Cần thiết kế sao cho với một trại bất kỳ, tồn tại duy nhất một đường dẫn điện trực tiếp hoặc gián tiếp từ trại ~1~ tới trại đó. Giả sử phần dây hao hụt trong quá trình đấu nối là không đáng kể.

Alice đã thiết kế được một phương án có tổng độ dài dây điện sử dụng là ~A~ mét. Cô đã mua đúng ~A~ mét dây điện. Tuy nhiên chưa kịp triển khai thì bản vẽ bị mất. Alice nhờ Bob thiết kế lại một phương án, nếu phương án của Bob có tổng độ dài dây điện cần dùng lớn hơn ~A~ thì họ phải mua thêm cho đủ, ngược lại thì không cần mua thêm.

Yêu cầu: Hãy giúp Bob tìm cách thiết kế sao cho tổng độ dài dây điện cần mua thêm là càng nhỏ càng tốt.

Input

Vào từ file văn bản ~\texttt{CAMP.INP}~:

• Dòng đầu chứa một số nguyên dương ~K~ (~3 \le K \le 10~).

• Dòng thứ hai chứa ~K~ số nguyên không âm ~\alpha_1, \alpha_2, \ldots, \alpha_K~.

• Dòng cuối cùng ghi số thực ~A~ (~0 < A < 2 \times \pi \times R~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản ~\texttt{CAMP.OUT}~:

• Dòng đầu ghi một số tự nhiên ~M~ là số lượng điểm trung gian (~0 \le M \le 25~).

• Nếu ~M > 0~ thì ~M~ điểm này được đánh số thứ tự từ ~K+1~ đến ~K+M~, và ghi ra ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số thực là tọa độ của điểm thứ ~K+i~. Các giá trị tọa độ được ghi ra với độ chính xác đến bốn chữ số sau dấu chấm thập phân.

• Mỗi dòng trong số ~K + M - 1~ dòng tiếp theo ghi hai số nguyên dương ~u~ và ~v~, mô tả một dây điện nối giữa điểm thứ ~u~ và điểm thứ ~v~ (~1 \le u,v \le K+M~).

Scoring

Với mỗi test, gọi ~B~ là tổng độ dài dây điện trong phương án thiết kế của Bob. Số điểm (trên thang điểm ~1~) cho phương án này là:

$$\begin{cases} 1, & \text{nếu } B \le A, \\ 0, & \text{nếu } B > 1.03 \times A, \\ 13 - 12^{\frac{B}{A}}, & \text{nếu } A < B \le 1.03 \times A. \end{cases}$$

Sample Input 1

3
0 120 240
300.0000

Sample Output 1

1
0.0000 0.0000
1 4
2 4
3 4

Notes

Thêm một điểm trung gian có tọa độ ~(0,0)~. Điểm trung gian này nối với ~3~ trại với tổng độ dài là ~300.0000~ mét.

Lưu ý: Checker không chấp nhận in ra số thập phân dạng ~\texttt{-0.0000}~.