Cho một mảng nguyên ~a[1..n]~ thỏa mãn:

• ~a[1]~ là giá trị nhỏ nhất của mảng,
• ~a[n]~ là giá trị lớn nhất của mảng,
• với mọi ~2 \le i \le n~, ta có ~|a[i] - a[i-1]| = 1~.

Bạn được cho thêm một tham số ~k~ và biết chắc rằng tồn tại ít nhất một vị trí ~id~ sao cho ~a[id] = k~. Nhiệm vụ của bạn là tìm ra một vị trí như vậy bằng cách thực hiện tối đa 16 lượt hỏi.

Cách Thức Giao Tiếp

1. Máy chấm sẽ in lên dòng đầu tiên:

2. ~n~ ~k~ với ~1 \le n \le 10000~.

3. Mỗi lượt, bạn chỉ in một số nguyên ~id~ sao cho ~1 \le id \le n~, rồi flush output.

4. Ngay sau đó, máy chấm sẽ phản hồi một trong ba chuỗi:

5. BIGGER (tức là ~a[id] < k~)
6. SMALLER (tức là ~a[id] > k~)
7. HOLA (tức là ~a[id] = k~)

Khi nhận HOLA, bạn có thể dừng chương trình (thành công).

1. Nếu bạn hỏi quá 16 lượt mà vẫn chưa gặp HOLA, chương trình của bạn sẽ bị coi là sai.

Ví dụ minh hoạ

Giả sử mảng ẩn là [2,3,4,5,6,7] và k = 5. Máy chấm in: ~6~ ~5~

Lần lượt bạn có thể làm:

Bạn đã tìm ra vị trí ~id=4~ chỉ trong 3 lượt hỏi.

Lưu ý:

• Luôn flush sau mỗi lần in (ví dụ dùng endl).
• Giới hạn tối đa 16 lượt hỏi.

Hôm nay lớp Cam có một trò chơi trong giờ Toán. Cô giáo nghĩ trong đầu một số nguyên ~X~ trong khoảng ~1~ đến ~10^6~. Các bạn học sinh cần tìm được số bí mật X với ít nhất các câu hỏi có dạng: "Ước chung lớn nhất của một số ~X~ với một số ~Y~ là bao nhiêu?". Bạn nào dùng càng ít câu hỏi thì điểm càng cao.

Các bạn hãy giúp cam viết một chương trình, sử dụng các câu lệnh được cung cấp để tìm ra số bí mật ~X~ mà hết ít câu hỏi nhấ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à bạn đọ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 câu lệnh:

  • ucln Y (~Y~ là một số nguyên dương bất kì ~1 \le Y \le 10^{18}~): máy sẽ in ra ước chung lớn nhất của X và Y.
  • traloi x (~x~ là một số nguyên dương): là số bí mật ~X~ mà bạn đã xác định được. Chương trình bắt buộc phải in ra traloi 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 trả lời với đáp án không chính xác, chạy quá thời gian quy định, sử dụng quá ~1000000~ câu hỏi 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 số câu hỏi bạn sử dụng tăng lên.

Example

• Giả sử số bí mật ~X~ cần tìm là ~300000~, quá trình nhập xuất có thể diễn ra như sau:

  >> ucln 100000
  << 100000
  >> ucln 200000
  << 100000
  >> ucln 500000
  << 100000
  >> ucln 900000
  << 300000
  >> traloi 300000
  

Bài Toán Giao Tiếp (Interactive Problem)

Cửa hàng TINAMS gồm ~n~ món đồ, món đồ thứ ~i~ có giá ~p_i~. Các món đồ đều có giá đôi một phân biệt với nhau.

Bạn đã đỗ đội tuyển và muốn mua toàn bộ các món đồ trong cửa hàng. Chủ cửa hàng nhận ra bạn là một khách VIP nên đưa cho bạn một voucher khuyến mãi như sau: bạn sẽ được miễn phí ~k~ món đồ, và phải trả tiền cho ~n- k~ món đồ còn lại. Tuy nhiên, điều thú vị ở đây là, bạn sẽ không biết giá trị của các món đồ, mà chỉ biết về các tham số ~n~ và ~k~ tương đương với số lượng món đồ và số món đồ được miễn phí.

Bạn muốn tối ưu hoa lợi ích của mình, nên muốn chọn các món đồ sao cho tổng số tiền các món đồ bạn phải trả là ít nhất có thể.

Tất nhiên, bạn sẽ được hỏi ông chủ những câu có dạng như sau, bạn được quyền chọn hai số ~x~ và ~y~:

• ~?~ ~x~ ~y~ trong đó ~1\le x,y\le n~.
• Sau mỗi truy vấn bạn dùng ~endl~ để ngắt câu hỏi.
• Máy chấm sẽ đọc truy vấn và in về một số nguyên:
  • Nếu ~p[x] < p[y]~, in về y.
  • Ngược lại (khi ~p[x] > p[y]~), in về x.

Bạn không được trực tiếp đọc hay in giá trị của ~p[i]~ - chỉ so sánh thông qua các truy vấn trên.

Ở bài toán này, điểm số ở từng test của bạn sẽ được chấm bằng một hàm bí mật, chỉ biết rằng, gọi ~C_u~ là số thao tác mà bạn sử dụng, ~C_j~ là số thao tác mà giám khảo sử dụng:

• Nếu ~C_u \le C_j~ bạn sẽ được toàn bộ số điểm của test đó.
• Ngược lại, số điểm mà bạn nhận được sẽ được tính toán sao cho nếu ~C_u - C_j~ càng nhỏ, điểm số càng cao.

Input

1. Khởi đầu: Máy chấm sẽ in lên dòng đầu:

2. ~n~ ~k~ với ~1 \le n \le 10^3~ và ~1 \le k \le n~.

3. Truy vấn: Mỗi lượt bạn in:

4. ~?~ ~x~ ~y~ rồi flush. Máy chấm sẽ phản hồi x hoặc y theo mô tả ở trên.
   Bạn không được dùng quá ~10^6~ truy vấn trong toàn bộ quá trình.

5. Kết thúc: Khi đã xác định được ~k~ vị trí, bạn in:

6. ~!~ ~1~ ~1~ rồi flush.

• Dòng tiếp theo, in ra ~k~ số ~id_1, id_2, ..., id_k~ đôi một phân biệt là các món đồ mà bạn chọn để miễn phí.

Ví dụ minh hoạ

Giả sử các món đồ có giá ẩn là ~p=[2,\,5,\,1,\,4,\,3]~, ~n=5~, và ~k=2~.
Máy chấm in:

• ~5~ ~2~ Bạn có thể thực hiện:

? 1 3 → 3 (vì p[1]=2 > p[3]=1 trả về 3)
? 3 5 → 3 (1 < 3 trả về 3)
? 4 2 → 4 (4 < 5 trả về 4)
? 1 4 → 1 (2 < 4 trả về 1)
! 1 1
2 4

Trong ví dụ này, bạn báo rằng món đồ ~2~ và ~4~ là hai món đồ bạn chọn để miễn phí. Đây là một lựa chọn chính xác.

Lưu ý

• Mỗi truy vấn in đúng cú pháp ? x y rồi endl.
• Tổng số truy vấn không vượt quá ~10^6~.
• Khi hoàn thành, in ! 1 1 rồi dòng chứa đáp án.
• Đáp án bị coi là sai nếu dùng quá nhiều truy vấn hoặc in sai định dạng.

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ụ

Lê là người thắng cuộc trong cuộc thi "Thiết kế thuật toán nén dữ liệu" và được nhận các phần thưởng của Ban tổ chức. Ban tổ chức đã chuẩn bị n món quà, các món quà được đánh số từ ~0~ đến ~n - 1~, món quà thứ ~i~ (~0 \le i < n~) có giá trị là một số nguyên dương ~v_i~ và Lê được chọn lấy một số món quà nhưng tổng giá trị các món quà không được vượt quá ~S~. Để việc chọn các món quà thêm phần thú vị, Ban tổ chức đưa ra cách thức chọn quà như sau:

• Ban tổ chức công khai giá trị của từng món quà nhưng không cho Lê biết giá trị ~S~.

• Lê được thực hiện không quá ~t~ lượt chọn quà, ở lượt thứ ~r~ (~0 \le r < t~), Lê cần đưa ra một dãy số ~p_0,p_1,\ldots,p_{n-1}~ là hoán vị của ~0, 1,\ldots,n- 1~ thể hiện thứ tự ưu tiên chọn các món quà. Khi đó, Ban tổ chức sẽ cho Lê biết số món quà mà Lê có thể nhận được nếu ưu tiên lấy các món quà theo thứ tự đó. Cụ thể, Ban tổ chức sẽ cho Lê biết giá trị ~c~ lớn nhất mà ~v_{p_0}+v_{p_1}+\ldots+v_{p_{c-1}}\le S~ hoặc thông báo ~c = 0~ nếu không lấy được món quà nào.

• Sau khi thực hiện một số lượt không vượt quá ~t~, Lê có thể dừng và được phép chọn các món quà ở một lượt nào đó mà tổng giá trị các món quà ở lượt đó là lớn nhất trong các lượt đã thực hiện.

Yêu cầu: Hãy giúp Lê đưa ra cách chọn quà sao cho tổng giá trị các món quà được nhận là lớn nhất.

Input

Thí sinh cần cài đặt hàm: void run(int n, vector<int> v, int t), trong đó:

• ~n~ là số món quà;

• ~v~ là vector chứa thông tin về giá trị các món quà với ~v[i]~ là giá trị món quà thứ ~i~;

• ~t~ là số lượt cho phép;

Hàm trên có thể gọi đến hàm sau: int select(vector<int> p), trong đó:

• ~p~ là một hoán vị của dãy ~0,1,\ldots,n-1~;

• hàm này trả về số lượng món quà lấy được nếu ưu tiên lấy các món quà theo thứ tự mô tả bởi hoán vị ~p~;

• hàm này không được gọi quá ~t~ lần.

Trong chương trình thí sinh cần phải khai báo thư viện bằng dòng lệnh #include "bonuslib.h" ở đầu chương trình. Ngoài ra, thí sinh được phép khai báo thêm thư viện, xây dựng các hàm, sử dụng biến toàn cục khác nếu cần.

Scoring

Có tất cả ~6~ subtask. Với mỗi test trong mỗi subtask, luôn tồn tại phương án chọn để tổng giá trị bằng đúng và phần trăm số điểm cho mỗi test được tính như sau:

• Thí sinh sẽ nhận được ~0\%~ số điểm nếu:

  • chạy sinh lỗi;

  • tương tác sai quy cách;

  • chạy quá thời gian;

  • hàm select được gọi quá ~t~ lần;

• Ngược lại, gọi ~TS~ là tổng giá trị của các món quà trong cách chọn của thí sinh, ~GK~ là tổng giá trị của các món quà trong cách chọn của giám khảo, khi đó phần trăm số điểm của test là:

  • ~0\%~ nếu ~Q>1~;

  • ~100\%~ nếu ~Q<0~;

  • ~100\%\times (-\log\_{10}(0.9\times Q+0.1))~ nếu ~0\le Q\le 1~;

  với ~Q=2\times n\times \dfrac{GK-TS}{GK}~.

Với mỗi subtask, gọi ~e~ là phần trăm số điểm nhỏ nhất của một test mà thí sinh đạt được trong các test thuộc subtask, ~score~ là điểm của subtask, khi đó, điểm cho subtask được tính bằng ~e\times score~.

Notes

Giả sử có ~4~ món đồ với giá trị tương ứng là ~\{9,3,1,5\}~ và ~t=3~, ~S=8~, hàm run sẽ được gọi với giá trị các tham số tương ứng là run(4,9,3,1,5,3). Dưới đây là một ví dụ cách gọi lần lượt các hàm select: