Tại Vietnam Game Awards ~2024~, VNGGames một lần nữa được vinh danh nhà phát hành game xuất sắc của năm sau khi trải qua ~2~ vòng thi và nhận được hơn ~38000~ lượt bình chọn từ cộng đồng. Để đáp lại tình cảm từ người hâm mộ, trong lễ trao giải VNGGames đã công bố một trò chơi mini dành cho người hâm mộ của mình. Tại đây VNGGames sẽ thách đố người hâm mộ tìm ra con số ~X~ đã bị mã hoá thành giá trị ~C \equiv X^3 \pmod N~ với ~N~ là một giá trị lớn, có giá trị bằng tích của ~p_1, p_2, p_3, ..., p_K~. Trong đó các giá trị ~p_i~ là những số nguyên tố.

Là một fan hâm mộ nhiệt thành của VNGGames, bạn rất hứng thú với mini game này và quyết tâm trở thành người có thể tìm ra ~X~ trong thời gian ngắn nhất. Lúc này, với tư duy lập trình đã có của mình, bạn dự định sẽ viết chương trình để máy tính có thể giúp bạn tìm ra số ~X~ trong thời gian nhanh nhất có thể.

Input

Chương trình của bạn sẽ lấy Dữ liệu đầu vào (Input) từ những thông tin VNGGames đã cho bạn bao gồm:

• Dòng đầu tiên cho số nguyên dương ~K~, là số lượng ~p_i~.
• Dòng tiếp theo chứa ~K~ số nguyên ~p_i~
• Dòng cuối cùng cho số ~C \pmod N~

Output

• Bạn sẽ viết chương trình yêu cầu máy tính cho dữ liệu đầu ra (Output) là giá trị ~X~ tìm được.

Constraints

• ~3 \leq K \leq 100~
• ~10^6 \leq p_i \leq 10^9~, ~p_i~ là số nguyên tố.
• ~X \leq 10^6 \ll N~
• ~C \lt N~

Sample input

3
1108819 1108823 1108867
1881365963625

Sample output

12345

Giải thích ví dụ

• Ta có ~N = 1108819\times 1108823\times 1108867 = 1363334245757698079~
• Ta thấy được với ~X = 12345~ thỏa được ~C \equiv X^3 \pmod N~

Mô tả đề bài

Cuộc thi bơi lội hằng năm tại Làng Xì Trum được tiếp tục tổ chức trong năm nay, mục tiêu rèn luyện sức khỏe cho các Xì Trum và cũng tăng cường sự gắn kết giữa các thành viên trong Làng.

Tí Vua người đứng đầu Làng đã chọn ra đường bơi có chiều dài là ~N~, Tí Cô Nương sẽ là người thi đầu tiên và cô đang đứng tại vị trí xuất phát của hồ. Với mỗi sải bơi Tí Cô Nương có thể bơi được độ dài là ~K~, và sau khi thực hiện sải bơi thứ ~i~ độ mệt mỏi của Tí Cô Nương sẽ cộng thêm ~i~. Theo bạn sau khi bơi được đến đích thì Tí Cô Nương có tổng độ mệt mỏi là bao nhiêu?

Giới hạn: ~ 1 \le K \le N \le 10^9 ~

Input

Gồm 1 dòng duy nhất chứa 2 số nguyên ~N~ và ~K~ ( ~1 \le K \le N \le 10^9~ )

Output

In ra tổng độ mệt mỏi sau khi bơi của Tí Cô Nương.

Sample Input

10 3

Sample Output

10

Giải thích ví dụ:

Tí Cô Nương sẽ cần bơi ~4~ sải để có thể đến được đích. Sải thứ nhất cộng thêm ~1~ độ mệt mỏi,..., sải thứ tư cộng thêm ~4~ độ mệt mỏi. Vậy tổng độ mệt mỏi của Tí Cô Nương sau khi bơi đến đích là ~1 + 2 + 3 + 4 = 10~.

Trong trường học tiểu học đang diễn ra lễ tổng kết, các giáo viên đang sắp xếp các học sinh của mình thành một hàng có chiều cao tăng dần.

Có ~N~ học sinh đang hiện đã được xếp thành một hàng theo thứ tự chiều cao tăng dần. Hiện đang có ~Q~ học sinh đến trễ, nên khi cứ có một học sinh mới tới thì giáo viên phải xếp học sinh đó vào trước các học sinh cao hơn.

Tuy nhiên, vì để phát quà thuận lợi, giáo viên cần biết rõ vị trí của các học sinh trong hàng. Vì vậy, khi có một học sinh mới vào hàng, hãy giúp giáo viên tìm vị trí của học sinh mới vào đó trong hàng nhé.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~N, Q~ ~(1 \le N, Q \le 5 \cdot 10^5)~ - là số học sinh ban đầu và số học sinh được thêm vào sau đó.
• Dòng thứ ~2~ gồm ~N~ số nguyên dương ~H_1, H_2, \dots H_N~ ~(1 \le H_i \le 10^9)~ - chiều cao của ~N~ học sinh được xếp ban đầu.
• ~Q~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương ~X~ ~(1 \le X \le 10^9)~ - là chiều cao của học sinh đến sau.

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ gồm một số nguyên dương là vị trí của học sinh thứ ~i~ được thêm vào hàng.

Constraints

• Subtask 1 (gồm ~50\%~ số điểm): ~N, Q \le 1000~.
• Subtask 2 (gồm ~50\%~ số điểm): ~N, Q \le 5 \cdot 10^5~.

Sample Input

8 5
2 3 3 5 5 7 7 9
9
5
2
5
3

Sample Output

9
6
2
8
5

Notes

Với trường hợp ví dụ:

• Hàng được xếp ban đầu như sau: 2 3 3 5 5 7 7 9
• Lần lượt các học sinh đến sau là:
  • Học sinh thứ nhất: 2 3 3 5 5 7 7 9 9. Vị trí thứ 9.
  • Học sinh thứ hai: 2 3 3 5 5 5 7 7 9 9. Vị trí thứ 6.
  • Học sinh thứ ba: 2 2 3 3 5 5 5 7 7 9 9. Vị trí thứ 2.
  • Học sinh thứ tư: 2 2 3 3 5 5 5 5 7 7 9 9. Vị trí thứ 8.
  • Học sinh thứ năm: 2 2 3 3 3 5 5 5 5 7 7 9 9. Vị trí thứ 5.

Trò chơi Đấu Trường Chân Lý do VNGGames phát hành đạt giải thưởng Game của năm tại đêm trao giải Vietnam Game Awards 2024.

Để ăn mừng cho những thành công đạt được, VNGGames tổ chức các trò chơi giải trí cho thành viên trong team. Ban Tổ Chức sẽ giao nhiệm vụ cho các đội chơi, mỗi đội chơi gồm 2 người. Nhiệm vụ cụ thể như sau:

Có ~n~ nhiệm vụ, được đánh số từ ~1~ đến ~n~. Nhiệm vụ ~i~ thuộc loại ~t[i]~.

• Nếu nhiệm vụ ~i~ được giao cho người đã hoàn thành nhiệm vụ ngay trước đó cùng loại thì thời gian thực hiện là ~b[t[i]]~.
• Nếu không, thời gian thực hiện là ~a[t[i]]~.

Mục tiêu của đội chơi là phân chia công việc sao cho phải hoàn thành tất cả nhiệm vụ trong thời gian sớm nhất. Các bạn hãy tính toán xem thời gian tốt nhất để một đội chơi có thể hoàn thành tất cả nhiệm vụ là bao nhiêu.

Lưu ý:

• Nhiệm vụ phải được hoàn thành theo thứ tự đề cho.
• Trong quá trình thực hiện nhiệm vụ, không ai được nghỉ quá ~d~ nhiệm vụ liên tiếp.
• Mỗi nhiệm vụ chỉ cần một trong hai người hoàn thành.

Input

Gồm nhiều test cases. Dòng đầu tiên là một số nguyên ~T~, số lượng test cases ~(T \le 10)~.
Dòng đầu tiên của mỗi test case là ~n, k~ và ~d~ ~(1 \le n, k, d \le 5000)~ lần lượt là số nhiệm vụ, số loại nhiệm vụ và khoảng nghỉ tối đa của một người.
Dòng thứ ~2~ trong mỗi test case là ~n~ số nguyên ~t_1,t_2,\cdots,t_n~ ~(1\le t_i \le k)~ là loại của nhiệm vụ thứ i.
Dòng thứ ~3~ trong mỗi test case là ~k~ số nguyên ~a_1,a_2,\cdots,a_k~ ~(1\le a_i \le 10^9)~ là thời gian để người đó hoàn thành công việc loại ~i~ trong trường hợp thứ 2.
Dòng thứ ~4~ trong mỗi test case là ~k~ số nguyên ~b_1,b_2,\cdots,b_k~ ~(1\le b_i \le a_i)~ là thời gian để người đó hoàn thành công việc loại ~i~ trong trường hợp đầu tiên.

Output

Mỗi dữ liệu được ghi trên một dòng là thời gian ngắn nhất mà một đội chơi có thể hoàn thành xong nhiệm vụ của mình.

Sample Input

1
4 3 4
1 3 1 3 
4 7 8 
2 7 7 

Sample Output

21

Subtask

• ~20\%~ số test có ~n \le 20, T = 1~.
• ~50\%~ số test tiếp theo có ~d = n~.
• ~30\%~ giới hạn đề bài.

Giải thích

2 người ~A~ và ~B~ sẽ làm thứ tự như sau: ~ABAB~ thì thời gian để hoàn thành là: ~4 + 8 + 2 + 7 = 21~.

Mô tả đề bài

Hiện tại, VNG đang trong quá trình phát triễn một trò chơi tiêu diệt quái vật. Luật của trò chơi có thể được phát biểu như sau:

"Với mỗi màn chơi, có ~N~ quái vật được xếp thành một hàng và được đánh số từ ~1~ đến ~N~ từ trái sang phải. Quái vật thứ ~i~ có chỉ số sức mạnh là ~A~_~i~. Người chơi sẽ đóng vai một vị anh hùng đi tiêu diệt quái vật và chỉ có thể thắng được màn chơi khi đã tiêu diệt được toàn bộ quái vật có trên hàng. Ban đầu, chỉ số sức mạnh của vị anh hùng này là ~1~. Bắt đầu màn chơi, vị anh hùng được phép chọn đối đầu với một quái vật bất kì trên hàng. Sau khi tiêu diệt được quái vật đầu tiên, vị anh hùng này buộc phải đối đầu với lần lượt các quái vật phía bên phải anh ta (di chuyển tấn công dần đến quái vật thứ ~N~). Sau khi tiêu diệt được hết tất cả các quái vật phía bên phải, anh ta quay lại và tấn công lần lượt các quái vật phía bên trái trái (di chuyển tấn công dần về quái vật đầu tiên) tất nhiên là không phải đối đầu lại với các quái vật đã bị tiêu diệt. Anh hùng chỉ có thể đánh thắng một quái vật khi anh ta mạnh bằng hoặc hơn quái vật đó. Sau khi tiêu diệt được một quái vật, sức mạnh của vị anh hùng sẽ gia tăng một lượng bằng với sức mạnh của quái vật vừa bị tiêu diệt. Màn chơi kết thúc khi tất cả các quái vật bị tiêu diệt (khi đó người chơi sẽ chiến thắng) hoặc vị anh hùng bị quái vật đánh bại (vị anh hùng đối đầu với một quái vật có sức mạnh lớn hơn anh ta) (khi này người chơi sẽ thua cuộc)."

Nhà phát hành mong muốn rằng với tất cả các màn chơi đều có cách để người chơi giành chiến thắng. Nhưng hiện tại các màn chơi được tạo ra một cách ngẫu nhiên, bạn hãy giúp nhà phát hành kiểm tra lại các màn chơi này đã hợp lệ hay chưa nhé!

INPUT

• Mỗi test gồm nhiều testcase, dòng đầu tiên chứa số nguyên T là số lượng testcase (~T ≤~ ~10~).
• Dòng đầu tiên của mỗi testcase chứa số nguyên dương ~N~ là số lượng số có trong dãy (~N ≤~ ~2⋅10~^~5~).
• Dòng tiếp theo chứa các số nguyên dương ~A~_~i~ (~1 \le i ≤ N~, ~A~_~i~ ~≤~ ~10~^~13~).

OUTPUT

• Gồm ~T~ dòng, dòng thứ ~i~ chứa "YES" (không có dấu ngoặc kép) nếu đó là một màn chơi hợp lệ, "NO" (không có dấu ngoặc kép) đó là màn chơi không hợp lệ.

SAMPLE INPUT

2
5
10 7 1 2 4
5
10 1 1 2 4

SAMPLE OUTPUT

YES
NO

Giải thích ví dụ

• Ở testcase đầu tiên, người chơi có thể xuất phát với việc chọn tiêu diệt quái vật ở vị trí 3. Sau đó tiêu diệt lần lượt các quái vật còn lại theo luật của trò chơi, chỉ số sức mạnh của nhân vật anh hùng sẽ thay đổi như sau: 1 (sẵn có) -> 2 (tiêu diệt quái vật 3) -> 4(tiêu diệt quái vật 4) -> 8 (tiêu diệt quái vật 5) -> 15 (tiêu diệt quái vật 2) -> 25(tiêu diệt quái vật 1).

• Ở testcase thứ hai, không có bất kì lựa chọn xuất phát nào có thể tiêu diệt được toàn bộ quái vật trên hàng.