Ở trường học Bedao nọ, hiệu trưởng illya có kế hoạch nâng cao thành tích môn Tin học của nhà trường nên đã quyết định mở lớp Chuyên tin dành cho những học sinh đạt kết quả cao trong kì thi đầu vào. Kì thi đầu vào ghi nhận có ~N~ học sinh tham gia, học sinh thứ ~i~ có số điểm môn Toán là ~a_i~ và có số điểm môn Tin là ~b_i~. Để đảm bảo lớp học chất lượng nhất có thể, hiệu trưởng illya đã các bước sàng lọc như sau:

• ~A~ học sinh có số điểm Toán cao nhất sẽ được nhận vào lớp.
• Đối với các học sinh chưa được nhận vào lớp, thì ~B~ học sinh có số điểm Tin cao nhất sẽ được nhận vào lớp.
• Đối với các học sinh chưa được nhận vào lớp, thì ~C~ học sinh có tổng số điểm Toán và Tin cao nhất sẽ được nhận vào lớp.
• Đối với các học sinh chưa được nhận vào lớp lúc này sẽ không được nhận vào lớp nữa.

Tuy vậy, hiệu trưởng illya lại rất đặc cách những bạn học sinh có số thứ tự nhỏ, cụ thể nếu hai học sinh có số điểm bằng nhau thì học sinh có số thứ tự nhỏ hơn sẽ được nhận. Là một nhân viên IT xuất sắc của nhà trường, bạn hãy giúp illya lập danh sách các học sinh được nhận vào lớp Chuyên tin nhé!

Input

• Dòng đầu tiên gồm ~4~ số nguyên ~N~ ~(1 \leq N \leq 1000)~, ~A~, ~B~, ~C~ ~(0 \leq A, B, C \leq N~ và ~1 \leq A + B + C \leq N)~.
• Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N~ lần lượt là số điểm Toán của học sinh thứ ~1, 2, \dots, N~ ~(0 \leq a_i \leq 100)~
• Dòng thứ ba gồm ~N~ số nguyên ~b_1, b_2, \dots, b_N~ lần lượt là số điểm Tin của học sinh thứ ~1, 2, \dots, N~ ~(0 \leq b_i \leq 100)~

Output

• Gồm danh sách các học sinh được nhận vào sắp xếp theo số thứ tự của các học sinh, mỗi dòng là một số thứ tự của một học sinh.

Sample Input

7 0 0 3
40 70 80 60 50 30 45
84 35 90 77 56 78 20

Sample Output

1
3
4

Note

Ở kì thi đầu vào lần này, ta sẽ lấy ~C = 3~ người có tổng điểm môn Toán và Tin cao nhất, từ đó ta sẽ có danh sách tổng điểm như sau: ~[124, 105, 170, 137, 106, 108, 65]~.

Từ danh sách này ta sẽ chọn ra được ~3~ tổng điểm cao nhất là ~[124, 170, 137]~ tương ứng với học sinh thứ ~1~, ~3~ và ~4~.

Đợt tuyển tình nguyện viên lần thứ ~2~ của VNOI đã diễn ra thành công và tốt đẹp. Những TNV được chọn ra đều là những gương mặt ưu tú nhất, để kiểm tra khả năng của TNV, các admin đã chuẩn bị một bài kiểm tra như sau:

Admin có ~n~ công việc, các công việc được đánh số từ ~1~ đến ~n~ tương ứng với độ khó lần lượt ~a_1, a_2, a_3, \dots, a_n~. Có ~m~ tình nguyện viên, mỗi tình nguyện viên cũng được đánh số từ ~1~ đến ~m~ tương ứng với khả năng làm được công việc độ khó lần lượt là ~b_1, b_2, b_3, \dots, b_m~. Các TNV đều là những người hăng hái ai cũng muốn chọn công việc có độ khó cao nhất (nhưng không vượt quá khả năng của mình) . Các TNV lần lượt từ trái sang phải đi nhận từng công việc, mỗi công việc chỉ được chọn ~1~ lần , nếu không có công việc nào phù hợp với khả năng của mình thì TNV đó sẽ được nghỉ.

Sau ~m~ lượt, có thể còn lại những công việc không được chọn bởi ai cả, nhiệm vụ của bạn là tìm công việc có độ khó cao nhất, nếu không còn lại công việc nào thì in ra ~-1~.

Input

Gồm ~3~ dòng chứa ~2~ số nguyên ~n~ và ~m~ ~(1 \le n, m \le 10^{6})~.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, a_3, \dots, a_n~ ~(1 \le a_i \le 10^{9})~ tương ứng là độ khó của từng công việc.

Dòng thứ ba gồm ~m~ số nguyên dương ~b_1, b_2, b_3, \dots, b_m~ ~(1 \le b_i \le 10^{9})~ tương ứng là năng lực của từng TNV.

Output

Gồm một số nguyên duy nhất là yêu cầu của bài toán.

Subtask

• ~20\%~ số test có ~1 \le a_i \le 5000~
• ~80\%~ số test còn lại không có điều kiện gì thêm

Sample Input

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

Sample Output

8

Note

Quy trình chọn việc từ trái qua phải như sau :

• Người ~1~ có khả năng làm công việc có độ khó cao nhất là ~3~ chọn công việc thứ ~3~ có độ khó cao nhất nhưng không vượt quá khả năng của mình ~(2 \le 3)~ , loại công việc thứ ~3~ ra khỏi danh sách.

Danh sách công việc còn lại có thể chọn là ~[1, 8, 4]~.

• Người ~2~ có khả năng làm công việc có độ khó cao nhất là ~3~ chọn công việc thứ ~1~ có độ khó cao nhất nhưng không vượt quá khả năng của mình ~(1 \le 3)~ , loại công việc thứ ~1~ ra khỏi danh sách.

Danh sách công việc còn lại có thể chọn là ~[8, 4]~.

• Người ~3~ có khả năng làm công việc có độ khó cao nhất là ~6~ chọn công việc thứ ~4~ có độ khó cao nhất nhưng không vượt quá khả năng của mình ~(4 \le 6)~ , loại công việc thứ ~4~ ra khỏi danh sách.

Danh sách công việc còn lại có thể chọn là ~[8]~.

• Ba người còn lại không thể chọn được công việc nào vì công việc có thể chọn còn lại vượt quá khả năng của ~3~ người đó.

Vậy công việc lớn nhất còn lại là ~8~.

~Naot~ rất thích chơi bắn tàu. ~lành~ cũng thích chơi bắn tàu. Hai người rất thích bắn tàu với nhau và nghiễm nhiên trở thành "kỳ phùng địch thủ" của nhau. Bạn là trợ thủ đắc lực thiết kế tàu cho ~Naot~, hãy giúp anh ấy tạo nên một chiếc chiến hạm nhé!

Trong tựa game mô phỏng bắn tàu anh đang chơi, người chơi phải thiết kế con tàu bằng một dãy số nguyên dương có độ dài ~n~. Là một người đam mê dãy đối xứng, ~Naot~ quyết định thiết kế một "chiến hạm" với các đặc tính sau:

• Vì muốn thiết kế một con tàu "ngon ngọt", ~Naot~ sẽ không quan tâm đến cấu hình đầu tiên của con tàu để cho "chiến hạm" của mình trông ngây thơ nhất có thể.

• ~Naot~ là một người chơi bắn tàu lão làng thấu hiểu đối thủ, anh có thể đoán trước được ~lành~ có thể sẽ nhắm vào ~m~ vị trí trên con tàu, với thông tin này ~Naot~ muốn rằng ở lần đầu tiên con tàu mình bị bắn vào bất cứ vị trí nào trong ~m~ vị trí anh đoán trước thì dãy biểu diễn con tàu sẽ ghép ~n-1~ vị trí còn lại (giữ nguyên vị trí tương đối) sao cho thành một dãy đối xứng. Nói cách khác, với mỗi vị trí dự đoán, loại bỏ vị trí đó ra khỏi dãy và nhận được một dãy đối xứng độ dài ~n-1~.

• Trò chơi đương nhiên sẽ cung cấp ~n~ loại nguyên liệu thiết kế tàu, các nguyên liệu được thể hiện dưới dạng các số nguyên dương không quá ~n~. ~Naot~ quan niệm rằng càng nhiều nguyên liệu lắp tàu thì "chiến hạm" của mình càng mạnh, anh quyết định chọn cách thiết kế tàu sử dụng nhiều loại nguyên liệu nhất. Nói cách khác số lượng giá trị phân biệt trong dãy là lớn nhất.

Dãy đối xứng là dãy khi viết ngược lại vẫn bằng dãy ban đầu.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ (~1 \le m \le n \le 10^6~).

Dòng thứ hai chứa ~m~ số nguyên dương đôi một phân biệt không quá ~n~ là các vị trí trên con tàu có nguy cơ bị bắn cao nhất.

Output

Gồm một dòng duy nhất chứa ~n~ số nguyên dương không quá ~n~ là cấu hình "chiến hạm" thỏa mãn các đặc tính mà ~Naot~ mong muốn. Nếu có nhiều đáp án thỏa mãn, hãy in ra một cấu hình bất kỳ.

Subtask

• ~60\%~ số test có ~1 \le m \le n \le 10^4~.

• ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

6 2
2 4

Sample Output 1

1 2 2 3 2 1

Notes

Ở test ví dụ, chúng ta có ~2~ vị trí có nguy cơ bị bắn cao và khi loại bỏ ~2~ vị trí ấy ta lần lượt được ~2~ dãy:

• Với vị trí ~2~ ta được: ~[1, 2, 3, 2, 1]~

• Với vị trí ~4~ ta được: ~[1, 2, 2, 2, 1]~

Cả hai dãy nhận được đều là dãy đối xứng, vì vậy cấu hình trên thỏa mãn hai yêu cầu đầu tiên của ~Naot~ và cũng thỏa mãn yêu cầu cuối cùng với nhiều nguyên liệu nhất.

Cho mảng ~a~ gồm ~a_1,a_2,...,a_n~ là một hoán vị của ~1,2,...,n~ và một số nguyên ~x~.

Ta chọn ~b_i~ là vị trí của giá trị trong mảng ~a~ nhỏ hơn ~a_i~ và có vị trí gần ~i~ nhất. Nếu có ~2~ giá trị cùng nhỏ hơn ~a_i~ và khoảng cách của chúng tới ~i~ là bằng nhau thì chọn vị trí của giá trị lớn hơn trong hai giá trị đó.

Mỗi giây, với mỗi ~i~ từ ~1~ tới ~n~, ta thay ~a_i~ bằng ~a_{b_i}~. Nếu vị trí ~i~ không tồn tại giá trị ~b_i~ thì ~a_i=0~. (Giá trị ~b_i~ không thay đổi qua các giây)

Cho ~q~ truy vấn. Với mỗi truy vấn cho một số nguyên dương ~k~, bạn cần trả lời sau ít nhất bao nhiêu giây thì có ít nhất ~k~ phần tử ~a_i~ trong mảng sao cho ~a_i \le x~.

Ví dụ: ~a = [4, 2, 3, 7, 8, 6, 5, 1]~, ta sẽ có ~b = [2, 8, 2, 3, 4, 7, 8, \emptyset]~ (~\emptyset~ nghĩa là không tồn tại giá trị).

• Sau giây thứ nhất ~a = [2, 1, 2, 3, 7, 5, 1, 0]~.
• Sau giây thứ hai ~a = [1, 0, 1, 2, 3, 1, 0, 0]~.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~n, q, x~ ~(1\le n, q \le5 \times 10^5, 0 \le x \le n)~ - lần lượt là độ dài của mảng ~a~, số truy vấn và hằng số nguyên bất kì.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1\le a_i \le n)~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ là một số nguyên dương ~k~ ~(k \le n)~ thể hiện truy vấn thứ ~i~.

Output

In kết quả trên ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Subtask

• ~20\%~ số test có ~n \le 3000~.
• ~30\%~ số test có ~x = 0~.
• ~30\%~ số test có ~q \le 3~.
• Các test còn lại không có điều kiện gì thêm.

Sample Input 1

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

Sample Output 1

0
0
1
1
1
2
2
3

illya là chủ một trang trại huấn luyện chó. Hiện tại, trong trại có ~n~ con chó đã hoàn thành bài các bài huấn luyện và sẵn sàng được nhận nuôi. Mặc dù cùng hoàn thành bài huấn luyện giống nhau, nhưng do nhiều yếu tố: giống loài, độ tuổi, giới tính, v.v nên sức mạnh của các con chó có thể khác nhau. Con chó thứ ~i~ đánh số từ trái sang phải có sức mạnh ~a_i~.

Trong đàn chó của illya, một con chó sẽ thường xuyên đi kiếm cớ gây sự với những con chó có sức mạnh chia hết cho sức mạnh của nó. Độ hổ báo của một con chó trong đoạn từ ~l~ đến ~r~ là số con chó nó sẽ trêu ghẹo trong đoạn từ ~l~ đến ~r~.

illya nhận được một cuộc hẹn của người chăn cừu để đến chọn mua một số con chó để về giúp trông coi đàn cừu. Người chăn cừu cho biết ông sẽ mua ~k~ con chó liên tiếp nhau. Để chất lượng đàn chó gửi đến người chăn cừu là tốt nhất có thể, illya quyết định sẽ cho các con chó trải qua thêm một đợt huấn luyện nữa. Nhưng vì thời gian có hạn, với mỗi dãy liên tiếp ~k~ con chó, illya chỉ có thể chọn ra con chó hổ báo nhất để huấn luyện lại nó, nếu có nhiều con chó cùng độ hổ báo, illya sẽ huấn luyện con có sức mạnh nhỏ nhất.

Với mỗi dãy liên tiếp ~k~ con chó, hãy giúp illya tính sức mạnh của con chó anh sẽ phải huấn luyện lại. Lưu ý một con chó có thể được huấn luyện lại nhiều lần.

Input

• Dòng đầu tiên chứa số 2 nguyên dương ~n~ và ~k~ lần lượt là số lượng con chó trong trang trại của illya và số lượng chó người chăn cừu sẽ mua ~(1 \leq k \leq n \leq 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ lần lượt là sức mạnh của ~n~ con chó ~(1 \leq a_i \leq 10^5)~.

Output

Gồm ~n - k + 1~ số nguyên dương ngăn cách bởi dấu cách, số nguyên dương thứ ~i~ là sức mạnh của con chó con chó cần được huấn luyện lại trong dãy ~k~ con chó liên tiếp bắt đầu từ con chó thứ ~i~.

Subtask

• ~20\%~ số test khác có ~n \leq 3000~.

• ~20\%~ số test khác có ~a_1, a_2, ..., a_n~ là số nguyên tố.

• ~60\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

6 3
1 3 2 6 4 8

Sample Output 1

1 2 2 4

Sample Input 2

7 4
2 6 12 3 9 11 8

Sample Output 2

2 3 3 3

Sample Input 3

7 4
1 3 2 8 3 2 4

Sample Output 3

1 2 2 2

Cho hai dãy ~a~ và ~b~ có cùng độ dài ~n~ và ~q~ truy vấn dạng ~l~ ~r~ ~x~. Với mỗi truy vấn, cần thực hiện một số thao tác như sau:

• Gán ~a_i = x~ với mọi ~i~ mà ~l \leq i \leq r~.

• Hãy cho biết có tồn tại hai số ~i~, ~j~ sao cho ~a_i \ne a_j~ và ~b_i = b_j~ hay không. Nếu có in ra YES, ngược lại, in ra NO.

Input

Dòng đầu tiên chứa hai số ~n~ và ~q~ (~n, q \leq 10^5~).

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3, ..., a_n~ (~1 \leq a_i \leq n~).

Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, b_3, ..., b_n~ (~1 \leq b_i \leq n~).

~q~ dòng cuối cùng, mỗi dòng chứa ba số nguyên ~l~, ~r~, ~x~ miêu tả một truy vấn (~1 \leq l \leq r \leq n~, ~1 \leq x \leq n~).

Output

Đối với mỗi truy vấn, in ra trên một dòng YES nếu tìm được cặp số thỏa mãn, NO trong trường hợp ngược lại.

Subtask

~30\%~ số test có ~n, q \leq 500~.

~30\%~ số test khác có ~n, q \leq 5000~.

Số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

YES
NO