Hôm nay bạn được học về tổ hợp tuyến tính. Trước khi kết thúc buổi học, thầy giáo ra một câu đố như sau:

Cho dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Một số nguyên dương ~x~ được gọi là đẹp nếu tồn tại một bộ ~n~ số nguyên không âm ~v_1, v_2, ..., v_n~ thỏa mãn ~x = a_1 \cdot v_1 + a_2 \cdot v_2 + \cdots + a_n \cdot v_n~.

Gọi ~b~ là tập hợp tất cả các số đẹp sắp xếp theo thứ tự tăng dần. Thầy giáo có ~q~ câu hỏi, mỗi câu hỏi thầy giáo yêu cầu học sinh tìm giá trị của số thứ ~k~ trong dãy ~b~.

Hãy lập trình để giải quyết bài toán.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ (~1 \le n \le 3 \cdot 10^5~) — độ dài của dãy ~a~ và ~q~ (~1 \le q \le 3 \cdot 10^5~) — số câu hỏi của thầy giáo.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6, \sum_{i = 1}^n a_i \le 10^6~).

~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~k~ mô tả các câu hỏi của thầy giáo ~(1 \leq k \leq 10^9)~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ là đáp án cho câu hỏi thứ ~i~.

Subtask

• ~5\%~ số test có ~n = 1~.

• ~10\%~ số test khác có ~1 \leq a_1, a_2, ...,a_n \leq 10~.

• ~15\%~ số test khác có ~k \leq 5000~ trong mọi câu hỏi.

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

Sample Input 1

3 8
5 3 11
1
2
8
9
6
5
14
23

Sample Output 1

3
5
12
13
10
9
18
27

Trong máy tính có 2 số ~N~ và ~C~. Bạn được cho biết trước số ~N~, nhưng số ~C~ bị giấu đi. Nhiệm vụ của bạn là đoán được số ~C~.

Để giúp bạn đoán được số ~C~, bạn được quyền giao tiếp với máy tính không quá ~64~ lần. Trong mỗi lần, bạn sẽ gửi cho máy tính một số nguyên từ ~1~ đến ~N~; tuy nhiên bạn không thể gửi cùng một số trong hai lượt khác nhau. Sau mỗi lần bạn gửi con số, hệ thống sẽ trả về một trong hai xâu ~YES~ hoặc ~NO~. Ở lượt đầu tiên, máy tính sẽ gửi ngẫu nhiên cho bạn một trong hai xâu này. Kể từ lượt thứ 2 trở đi, máy sẽ trả về ~YES~ khi và chỉ khi chênh lệch của số được gửi lần này và số được gửi ở lần ngay trước đó không bé hơn ~C~, và ~NO~ nếu ngược lại. Cụ thể, nếu bạn gửi số ~X~ trong lần thứ ~i - 1~ và số ~Y~ trong lần thứ ~i~, bạn sẽ nhận về ~YES~ ở lượt thứ ~i~ khi và chỉ khi ~|X - Y| \geq C~ và sẽ nhận về ~NO~ nếu ~|X - Y| < C~.

Trong nhiệm vụ này, mỗi test ~T~ thử nghiệm riêng biệt, để qua được một test bạn phải đoán đúng giá trị ~C~ trong các thử nghiệm đó.

Tương tác

Đây là bài toán tương tác. Mỗi test gồm ~T~ test con.

• Đầu tiên, bạn cần đọc vào giá trị ~T~.
• ~T~ test sẽ được thực hiện tuần tự, trong đó ở mỗi test:
  • Bạn đọc vào số nguyên ~N~
  • Truy vấn ? X: chương trình sẽ trả lời YES nếu chênh lệnh giữa hai phần tử trong 2 lần gửi gần nhất lớn hơn hoặc bằng C và NO trong trường hợp ngược lại. Các giá trị của ~X~ trong các lần gọi hàm phải đôi một phân biệt, nếu không, bạn sẽ nhận được kết quả Wrong Answer. Trong mỗi test con, bạn được hỏi truy vấn này không quá ~64~ lần.
  • Trả lời = C: đưa ra giá trị ~C~ cần tìm. Bạn chỉ được trả lời một lần với mỗi test con.

Constants

~1 \leq C \leq N \leq 10^{18}, 1 \leq T \leq 1000~

Subtask

• Subtask 1 (9 điểm): ~N \leq 64~
• Subtask 2 (13 điểm): ~N \leq 125~
• Subtask 3 (21 điểm): ~N \leq 1000~`
• Subtask 4 (24 điểm): ~N \leq 10^9~
• Subtask 5 (33 điểm): ~N \leq 10^{18}~

Ví dụ

Trong bài toán này, có một số nguyên chưa biết ~x~ với ~1 \le x \le 10^9~. Nhiệm vụ của bạn là biến nó thành số nguyên ~n~ được cho trong input. Bằng cách sử dụng một CPU, bạn có thể gửi lệnh để thực hiện một trong các thao tác sau:

Các lệnh

* ~S(n)~ là hàm trả về tổng các chữ số của số nguyên không âm ~n~. Ví dụ: ~S(123) = 1 + 2 + 3 = 6~.

Bạn phải biến ~x~ thành ~n~ với càng ít thao tác càng tốt!

Input

Mỗi input gồm nhiều test case.

• Dòng đầu chứa số nguyên ~t~ (~1 \le t \le 100~) — số lượng test case.
• Mỗi test case gồm một dòng chứa một số nguyên ~n~ (~1 \le n \le 10^9~).

Chấm Điểm

Gọi ~x~ là ~min~ số lệnh của từng case bạn dùng trong một test.

• Nếu ~5 \le x \le 7~, bạn nhận được ~30\%~ điểm của test đó.
• Nếu ~x = 4~, bạn nhận được ~70\%~ điểm của test đó.
• Nếu ~x~ nhỏ hơn ~4~, lệnh của bạn sẽ được so sánh với số lệnh của ban giám khảo, nếu ~x~ không lớn hơn giá trị của ban giám khảo, bạn nhận được toàn bộ số điểm, ngược lại nhận được ~90\%~ điểm của test.

Interaction

Với mỗi test case, quá trình tương tác bắt đầu bằng việc đọc số nguyên ~n~.

Gửi lệnh

Bạn in ra một dòng theo đúng định dạng của một trong các lệnh sau:

• ~add~ ~y~: cộng số nguyên ~y~ (~-10^{18} \le y \le 10^{18}~) vào ~x~.
  Jury trả ~1~ nếu ~x + y~ nằm trong ~[1, 10^{18}]~ (thành công), và khi đó cập nhật ~x \leftarrow x + y~. Nếu không, trả ~0~ và ~x~ không đổi.

• ~mul~ ~y~: nhân ~x~ với số nguyên dương ~y~ (~1 \le y \le 10^{18}~).
  Jury trả ~1~ nếu ~x \cdot y~ nằm trong ~[1, 10^{18}]~ (thành công), và khi đó cập nhật ~x \leftarrow x \cdot y~. Nếu không, trả ~0~ và ~x~ không đổi.

• ~div~ ~y~: chia ~x~ cho số nguyên dương ~y~ (~1 \le y \le 10^{18}~).
  Jury trả ~1~ nếu ~y~ chia hết ~x~ (thành công), và khi đó cập nhật ~x \leftarrow x / y~. Nếu không, trả ~0~ và ~x~ không đổi.

• ~digit~: thay ~x~ bằng tổng chữ số của nó.
  Jury luôn trả ~1~ và cập nhật ~x \leftarrow S(x)~.

Lưu ý: lệnh phân biệt hoa/thường.

Trả lời

Khi bạn tin rằng ~x = n~, in ra:

• ~!~

Jury sẽ trả:

• ~1~ nếu ~x~ đúng bằng ~n~,
• ~-1~ nếu không đúng.

Lệnh ~!~ không tính vào giới hạn ~7~ lệnh.

Lỗi và kết thúc

• Nếu bạn dùng hơn ~7~ lệnh cho một test case, hoặc in ra lệnh không hợp lệ, jury sẽ trả ~-1~.
• Sau khi nhận ~-1~, chương trình của bạn phải kết thúc ngay lập tức để nhận verdict Wrong Answer.

Flush output

Sau mỗi lần in lệnh, bạn phải xuống dòng và flush output, nếu không sẽ bị Idleness limit exceeded.

Ví dụ:

• C/C++: ~fflush(stdout)~ hoặc ~cout.flush()~
• Java: ~System.out.flush()~
• Python: ~sys.stdout.flush()~
• Rust: ~std::io::stdout().flush()~

Ghi chú

Interactor là non-adaptive: số nguyên bí mật ~x~ không thay đổi trong suốt quá trình tương tác.

Người ngoài hành tinh quyết định tới thăm các em học sinh của HNAms. Tuy nhiên vì ngôn ngữ bất đồng nên các em không hiểu những người ngoài hành tinh muốn nói gì. Vì vậy các em phải mang theo từ điển của mình ra để cho họ xem. Sau đó các em sẽ đoán xem là họ muốn nói đến từ nào trong từ điển. Từ điển cũng chỉ gồm ~26~ chữ cái thường từ ~a~ đến ~z~. Tuy nhiên vì không thể giải thích được với nhau nên hiện tại bước đầu giao tiếp vẫn là đoán từ và các câu hỏi để đoán từ phải vô cùng đơn giản. Người ngoài hành tinh chỉ có thể hiểu các câu hỏi sau:

1. Có bao nhiêu kí tự ~C~ trong từ đó?
2. Kí tự tại vị trí ~X~ là kí tự gì?

Nhiệm vụ của các bạn là viết một chương trình, sử dụng các câu lệnh được cung cấp để thực hiện khảo sát từ điển trong một bộ dữ liệu vào và đưa ra từ mà người ngoài hành tinh muốn nói là từ gì.

Input

• Dòng đầu tiên là số nguyên dương ~N~ (~1 \le N \le 10^6~) là số từ trong từ điển.
• ~N~ dòng tiếp theo mô tả từ điển chỉ gồm danh sách các từ đôi một khác nhau, trong đó mỗi từ nằm trên một dòng và chỉ gồm các chữ cái in thường từ ~a~ đến ~z~ dài tối đa ~50~ kí tự.

Interaction

Để tương tác với máy chấm, hãy in mỗi lệnh trên từng dòng. Câu trả lời sẽ được máy chấm in ra trên một dòng khác, và em đọc vào. Lưu ý flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc cout << endl;

Các lệnh được sử dụng:

• count c (~c~ là một kí tự bất kì từ a đến z): máy sẽ in ra số lượng kí tự c trong từ cần tìm. Chi phí sử dụng hàm count c 1 lần là 1 đơn vị.
• getpos x (~x~ là một số nguyên dương): máy sẽ in ra kí tự tại vị trí x trong từ cần tìm (từ trái sang phải, xâu được đánh số từ 1). Nếu ~x~ lớn hơn độ dài của từ, máy sẽ in ra kí tự #. Chi phí sử dụng hàm getpos x 1 lần là 10 đơn vị.
• answer s (~s~ là một xâu kí tự): là từ mà em đã xác định được. Chi phí sử dụng thủ tục answer() là 0 đơn vị. Chương trình bắt buộc phải gọi thủ tục answer() một lần duy nhất, nếu không sẽ bị 0 điểm. Thủ tục này khi được gọi sẽ tự động thoát chương trình bằng câu lệnh exit.

Scoring

• Với mỗi test, nếu chương trình của bạn gọi thủ tục answer() với đáp án không chính xác, chạy quá thời gian quy định, sử dụng quá 1000 đơn vị hoặc gặp các lỗi dẫn tới dừng chương trình, bài làm sẽ nhận 0 điểm cho test đó. Số điểm cho mỗi test sẽ giảm dần khi chi phí bạn sử dụng tăng lên.

Sample Input 1

7
cat
can
mic
man
tiger
hello
world

Sample Output 1

Giả sử từ người ngoài hành tinh muốn nói là cat. Các hoạt động nhập xuất có thể diễn ra như sau:

>> getpos 4
<< #
>> count c
<< 1
>> count a
<< 1
>> count n
<< 0
>> answer cat

Explaination

• Độ dài của từ cat là ~3~ nên khi hỏi độ dài bằng ~4~ vượt quá độ dài ~3~, máy in ra dấu #
• Trong từ cat có 1 kí tự c nên máy in ra ~1~
• Trong từ cat có 1 kí tự a nên máy in ra ~1~
• Trong từ cat không có kí tự n nên máy in ra ~0~
• Như vậy bạn đã trả lời đúng với chi phí sử dụng là ~13~. Chương trình khi in ra answer cat sẽ đưa đáp án đồng thời thoát chương trình chạy của bạn.

Bạn đang tìm một vị trí trong đất để đặt một con giun, thú cưng của mình, Maximus. Khu vực tìm kiếm là một vùng hình hộp có kích thước ~N \times M \times K~ được chia thành lưới ba chiều gồm các ô hình lập phương. Các ô trong hộp được gắn nhãn ~(x, y, z)~, tương ứng với tọa độ của chúng ~(1 \leq x \leq N, 1 \leq y \leq M, 1 \leq z \leq K)~. Mỗi ô có độ ẩm nhất định ~H [x, y, z]~ là một số nguyên trong phạm vi ~1 ... 10^9~. Bạn có thể đo độ ẩm của bất kỳ ô nào bằng một cảm biến đặc biệt.

Maximus rất thích những nơi ẩm ướt, vì vậy bạn cần phải đưa nó vào một ô có độ ẩm ước ít nhất cũng bằng các ô lân cận, nếu không, nó sẽ bỏ đi và bạn sẽ khó tìm thấy nó. Nói cách khác, bạn cần đặt Maximus ở ô ~(x, y, z)~, sao cho

~H [x, y, z] \geq max (H [x + 1, y, z], H [x - 1, y, z], H [x, y + 1, z], H [x, y - 1, z], H [x, y, z + 1], H [x, y, z - 1])~

trong đó một giá trị được coi là 0 khi nó nằm ngoài hộp (vì Maximus muốn ở trong hộp). Tuy nhiên, số lượng ô có thể rất lớn, vì vậy bạn không thể đo độ ẩm của tất cả các ô. Do đó, bạn chỉ có thể do một số lượng ô nhất định

Tương tác

Đầu tiên, bạn cần đọc vào bốn số nguyên ~N, M, K, Q~. Trong đó ~N, M, K~ là kích thước hình hộp và ~Q~ là số truy vấn bạn được hỏi. Sau đó bạn được phép hỏi chương trình các câu như sau:

• ? x y z: chương trình sẽ in ra giá trị ~H[x, y, z]~, lưu ý rằng bạn không được hỏi quá ~Q~ truy vấn này.
• ! x y z: vị trí bạn chọn cho Maximus. Lưu ý rằng bạn chỉ được trả lời một lần duy nhất và chương trình sẽ dừng lại sau đó. Câu trả lời cần thỏa mãn điều kiện đề bài.

Sau mỗi truy vấn bạn cần dùng endl hoặc flush.

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask 1 (10 điểm) ~M = K = 1, N = 1000000, Q = 10000~
• Subtask 2 (22 điểm) ~M = K = 1, N = 1000000, Q = 35~
• Subtask 3 (12 điểm) ~K = 1, N = M = 200, Q = 4000~
• Subtask 4 (19 điểm) ~K = 1, N = M = 1000, Q = 3500~
• Subtask 5 (14 điểm) ~N = M = K = 100, Q = 10000~
• Subtask 6 (23 điểm) ~N = M = K = 500, Q = 15000~

Điểm tối đa của bài là ~100~ điểm. Để đạt được điểm của một subtask, bạn cần làm đúng tất cả test trong subtask đó.

Ví dụ