Cho các số nguyên ~X~, ~Y~, ~a~, ~b~, ~c~, ~d~, trong đó ~a~, ~b~, ~c~, ~d~ là các giá trị khác nhau và một trong 4 số là kết quả của phép tính ~X+Y~.

Yêu cầu: Đưa ra một trong 4 chữ cái A, B, C hoặc D ứng với kết quả đúng của phép tính ~X+Y~ là ~a~, ~b~, ~c~ hoặc ~d~.

Input

• Dòng đầu gồm hai số nguyên ~X~, ~Y~ (~1 \le X, Y \le 10^6~);
• Dòng thứ hai gồm bốn số nguyên ~a~, ~b~, ~c~, ~d~ (~1 \le a, b, c, d \le 2 \times 10^6~).

Output

Ghi một trong 4 chữ cái A, B, C hoặc D ứng với kết quả đúng.

Sample Input 1

5 3
6 10 8 9

Sample Output 1

C

Hôm nay là sinh nhật lần thứ ~T~ của cô chủ cửa hàng online OShop. Nhân dịp này, cửa hàng đã áp dụng chính sách khuyến mãi như sau: Nếu các đơn hàng có giá trị lớn hơn ~K~ và đồng thời giá trị đó chia hết cho ~T~ thì sẽ được miễn phí giao hàng.

Trong ngày, cửa hàng nhận được ~N~ đơn hàng có giá trị lần lượt là ~a_1, a_2, ..., a_N~.

Yêu cầu: Hãy giúp cửa hàng liệt kê giá trị của các đơn hàng được miễn phí giao hàng và số lượng các đơn hàng được áp dụng chính sách đó.

Input

• Dòng đầu gồm ba số nguyên dương ~N~, ~K~, ~T~ (~N \le 1000~; ~K \le 10^8~; ~T \le 50~);
• Dòng thứ hai gồm ~N~ số nguyên ~a_i~ (~1 \le a_i \le 10^8~; ~i=1..N~), cho biết giá trị từng đơn hàng.

Output

• Dòng đầu: Ghi giá trị các đơn hàng được miễn phí giao hàng theo thứ tự xuất hiện trong danh sách ban đầu, nếu không có đơn nào thỏa mãn điều kiện thì in ra từ "KHONG";
• Dòng thứ hai: Ghi một số nguyên cho biết số lượng các đơn hàng được miễn phí giao hàng.

Sample Input 1

6 90 20
50 120 80 200 90 95

Sample Output 1

120 200
2

Giải thích: Có 2 giá trị đơn hàng lớn hơn 90 và chia hết cho 20 là 120, 200.

Sample Input 2

6 50 27
50 30 90 80 60 70

Sample Output 2

KHONG
0

Giải thích: Không có đơn hàng nào thỏa mãn điều kiện khuyến mãi.

Cửa hàng X tổ chức sự kiện tri ân khách hàng bằng hình thức như sau: Mỗi khách hàng khi mua sản phẩm tại cửa hàng sẽ nhận được một mã dự thưởng ~T~ là một số nguyên có 6 chữ số. Hôm nay, cửa hàng công bố mã trúng thưởng ~S~ (cũng là một số nguyên có 6 chữ số). Khách hàng sẽ nhận được một phần quà có giá trị tương ứng với quy tắc mà cửa hàng đưa ra như sau:

• Nếu mã dự thưởng trùng khớp với mã trúng thưởng theo đúng thứ tự từng chữ số thì giá trị của phần quà là 2000;
• Nếu mã dự thưởng và mã trúng thưởng chỉ sai lệch chữ số đầu tiên, các chữ số còn lại đều trùng khớp với nhau thì giá trị phần quà là 50;
• Nếu mã dự thưởng trùng khớp chữ số đầu tiên so với mã trúng thưởng, nhưng lại bị sai một chữ số duy nhất ở một trong 5 chữ số còn lại thì giá trị phần quà là 6;
• Các trường hợp còn lại không trúng thưởng thì không có quà (giá trị là 0).

Yêu cầu: Cho biết mã trúng thưởng ~S~ của cửa hàng và mã dự thưởng ~T~. Hãy xác định giá trị của phần quà mà khách hàng có thể nhận được.

Input

• Dòng đầu gồm một số nguyên ~S~, là mã trúng thưởng được cửa hàng công bố;
• Dòng thứ hai gồm một số nguyên ~T~, là mã dự thưởng của khách hàng.

Output

Ghi một số nguyên cho biết kết quả theo yêu cầu của bài toán.

Sample Input 1

123456
923456

Sample Output 1

50

Giải thích: Hai mã chỉ lệch nhau ở hàng trăm nghìn (~1 \ne 9~).

Sample Input 2

123456
123956

Sample Output 2

6

Giải thích: Hai mã trùng khớp ở hàng trăm nghìn, nhưng lệch nhau ở hàng trăm (~4 \ne 9~).

Sample Input 3

123754
123457

Sample Output 3

0

Giải thích: Có 2 vị trí lệch nhau ở hàng trăm (~7 \ne 4~) và hàng đơn vị (~4 \ne 7~) không có giải thưởng.

Công ty CT được giao nhiệm vụ tưới cây trên một tuyến đường có trồng ~N~ cây xanh. Hàng ngày, cây xanh thứ ~i~ (~i=1..N~) cần một lượng nước tưới là ~a_i~ và mức độ ưu tiên là ~p_i~. Do hệ thống nước gặp sự cố, trong ngày hôm nay công ty chỉ có thể huy động được lượng nước là ~M~. Biết rằng các cây xanh có độ ưu tiên càng cao (~p_i~ càng nhỏ) thì phải được tưới trước. Cây xanh thứ ~i~ được gọi là tưới đầy đủ nếu được tưới đủ lượng nước ~a_i~.

Yêu cầu: Hãy cho biết số lượng cây xanh nhiều nhất được tưới đầy đủ.

Input

• Dòng đầu gồm số nguyên ~N~ và ~M~ (~1 \le N \le 2 \times 10^5~, ~1 \le M \le 10^9~);
• Dòng thứ hai gồm ~N~ số nguyên ~a_i~ (~1 \le a_i \le 10^6~);
• Dòng cuối cùng gồm ~N~ số nguyên ~p_i~ (~1 \le p_i \le N~).

Output

Ghi một số nguyên cho biết số lượng cây xanh được tưới đầy đủ.

Sample Input 1

6 10
5 1 2 2 1 2
1 2 1 1 3 1

Sample Output 1

3

Giải thích: Ưu tiên tưới các cây ở vị trí 1, 3, 4, mất 9 đơn vị nước. Phần nước còn thừa lại (~10-9=1~) sẽ tưới cho cây ở vị trí 6 (do mức ưu tiên ~p_6=1~ nhưng không được tính vì không tưới đủ lượng nước cây cần (cây thứ 6 cần 2 đơn vị nước).

Subtasks

• 30% số test ứng với 30% số điểm có tất cả ~p_i=1~;
• 30% số test ứng với 30% số điểm có ~1 \le p_i \le 10~;
• 40% số test ứng với 40% số điểm còn lại: Không có ràng buộc gì thêm.

Notes

Bài này có 2 cách hiểu đề:

1. Nếu các cây có ~p_i~ bằng nhau, ta tưới cây có chỉ số ~i~ nhỏ nhất. Đây là cách hiểu theo giải thích ví dụ.
2. Nếu các cây có ~p_i~ bằng nhau, ta tưới cây bất kỳ.

Do đề không ghi rõ ràng, mình đã add checker chấp nhận cả 2 cách hiểu đề này.

Nhóm của An có ~M~ bạn đang cùng nhau thực hiện tiết kiệm tiền để chuẩn bị cho các kế hoạch trong tương lai. Mỗi bạn có một mục tiêu tiết kiệm của riêng mình. Theo tính toán của An, trong ~N~ ngày tới, ngày thứ ~i~ (~1 \le i \le N~) mỗi bạn sẽ có cùng một khoản thu nhập là ~a_i~. Tuy nhiên, để đảm bảo chi phí sinh hoạt và các nhu cầu cá nhân khác, nhóm bạn tự đặt ra một quy tắc nghiêm ngặt: mỗi bạn sẽ thực hiện tiết kiệm vào chỉ những ngày chẵn hoặc chỉ những ngày lẻ (ngày đầu tiên là ngày 1).

Yêu cầu: Với mỗi bạn, hãy xác định thời gian sớm nhất (số ngày ít nhất tính từ ngày đầu tiên) để có thể tích lũy đạt (bằng hoặc nhiều hơn) số tiền theo mục tiêu mà bản thân đã đề ra.

Input

• Dòng đầu gồm hai số nguyên ~N~ và ~M~ (~1 \le N \le 2 \times 10^5~, ~1 \le M \le 10^5~);
• Dòng thứ hai gồm ~N~ số nguyên ~a_i~ cho biết số tiền thu nhập của mỗi bạn ở ngày thứ ~i~ (~1 \le a_i \le 10^6~; ~i=1..N~);
• ~M~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương cho biết mục tiêu (số tiền) cần đạt được của mỗi bạn, các giá trị không vượt quá ~10^9~.

Output

Ghi ~M~ dòng, mỗi dòng ghi một số nguyên cho biết số ngày ít nhất để đạt mục tiêu của mỗi bạn. Nếu với ~N~ ngày mà bạn đó vẫn không thể tích lũy đủ, hãy ghi ra -1.

Sample Input 1

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

Sample Output 1

3
4
-1

Giải thích:

• Bạn thứ 1 đặt mục tiêu với số tiền là 6, bạn thực hiện tiết kiệm vào ngày thứ 1 và thứ 3 (ngày lẻ), được số tiền là ~3+3=6~, mất thời gian 3 ngày;
• Bạn thứ 2 đặt mục tiêu với số tiền là 8, bạn chọn tiết kiệm vào ngày thứ 2 và thứ 4 (ngày chẵn), được số tiền là ~5+4=9~, vượt mục tiêu đề ra, mất thời gian là 4 ngày;
• Bạn thứ 3 đặt mục tiêu với số tiền là 12, dù chọn tiết kiệm vào ngày chẵn hay ngày lẻ đều không thể đạt mục tiêu sau 7 ngày.

Subtasks

• 40% số test ứng với 40% số điểm có ~1 \le N, M \le 1000~;
• 60% số test ứng với 60% số điểm còn lại: Không có ràng buộc gì thêm.