Bạn được cung cấp một số nguyên dương \(N\) \((N \le 10^6)\). Bạn phải in ra hai số nguyên tố \(A\) và \(B\) thỏa mãn \(A+B=N\).

Nhưng nhiệm vụ của bạn đâu đơn giản như thế phải không :)), bạn sẽ phải giao tiếp với máy chấm để in ra hai số \(A\) và \(B\) này.

Tương tác

Đây là bài toán interactive.

Bạn được phép giao tiếp với máy không quá \(128\) lần, mỗi lần bạn sẽ nhập vào hai số nguyên dương \(A\) và \(B\), trong trường hợp:

• \(A+B=N\) và \(A,B\) là các số nguyên tố: máy chấm sẽ tự thoát chương trình, bạn \(AC\) bài toán.
• \(A+B\ne N\), máy chấm sẽ in ra a + b khac n.

Sample

Và chương trình của bạn sẽ Accepted vì số lần nhập \(A,B\) dưới \(128\) lần.

Đây là bài toán giao tiếp với máy chấm (Interactive problem)

cuom1999 có một con số \(n\) bí mật. Điều duy nhất bạn biết về con số này là \(1 \leq n \leq 2 \times 10^9\). cuom1999 và bạn sẽ chơi một trò chơi như sau: Bạn sẽ được chọn một số bất kỳ và nói cho cuom1999 nghe số đó. cuom1999 sẽ cho bạn biết con số của bạn lớn hơn, nhỏ hơn, hay bằng \(n\). Hãy đoán xem \(n\) là số nào trong không quá \(31\) câu hỏi.

Cách Thức Giao Tiếp

Mỗi lượt, bạn sẽ in ra một số \(x\) trên một dòng (\(1\leq x \leq 2 \times 10^9\)). Máy tính sẽ đọc \(x\) và in ra màn hình một chuỗi tương ứng với các trường hợp sau:

• "BIGGER" nếu \(n > x\)
• "SMALLER" nếu \(n < x\)
• "HOLA" nếu \(n = x\).

Lưu ý:

• Chuỗi mà máy in ra màn hình không có dấu "
• Nếu các bạn in ra một output không hợp lệ (không phải là một số, số ngoài đoạn \([1, 2 \times 10^9]\) thì nhiều khả năng bị TLE.
• Sau khi in mỗi số, bạn phải xuống dòng (ví dụ in endl trong C++)
• Khi in ra một dòng, các bạn phải flush output bằng cách cout.flush hoặc dùng endl thay vì \n

Example

Đây là bài toán tương tác với máy chấm.

Thuận và Hiếu đang chơi một trò chơi đoán số với nhau, trong đó Thuận là người đoán và Hiếu là người trả lời.

Ban đầu, Hiếu cho Thuận biết số Thuận cần đoán là một số nguyên \(n\) (\(0 \leq n \leq 10^{18}\)) nào đó. Thuận được phép hỏi Hiếu tối đa \(40\) câu hỏi, mỗi câu hỏi là hai số nguyên \(l,r\), Hiếu sẽ trả lời cho Thuận biết số nguyên \(n\) có nằm trong khoảng \([l,r]\) không, nếu không thì số \(n\) bé hơn \(l\) hay số \(n\) lớn hơn \(r\).

Trong bài toán này, bạn sẽ vào vai Thuận, Hiếu sẽ vào vai máy chấm. Bạn được phép đưa ra tối đa \(40\) câu hỏi dạng như trên để xác định số nguyên \(n\) bí ẩn cần tìm. Hãy giúp Thuận nhé!

Bạn được phép đưa ra tối đa \(40\) truy vấn để xác định số nguyên \(n\).

Interaction

Thí sinh cần cài đặt hàm sau:
void solve()

Thí sinh có thể gọi hai hàm sau:

• std::string ask(long long left, long long right);
• void answer(long long x);

Hàm ask sẽ trả về một std:: string có giá trị:

• left: nếu \(n < l\).
• in: nếu \(l \leq n \leq r\).
• right: nếu \(n > r\).

Bạn được phép gọi hàm này tối đa \(40\) lần.

Hàm answer sẽ đưa ra câu trả lời là \(x\) và hàm này chỉ được gọi một lần duy nhất.

Cài đặt

Thí sinh tạo file header.h với nội dung sau:

#include <bits/stdc++.h>
using namespace std;

string ask(long long left, long long right) {
    cout << "? " << left << " " << right << endl;
    string ans;
    cin >> ans;
    return ans;
}

void answer(long long x) {
    cout << "! " << x << endl;
    exit(0);
}
void solve();

int main() {
    solve();
    return 0;
}

File bài làm của các bạn có nội dung như sau (khi nộp bài, nộp file này):

#include "header.h"
#include <bits/stdc++.h>
using namespace std;

void solve() {
    // code ở đây
}

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(0 \leq n < 40\).
• Subtask \(2\) (\(30\%\) số điểm): \(0 \leq n \leq 10^{9}\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

Trong những ghi chép cổ xưa có những thông tin về một pháo đài cổ ở thành Vinh trên bản đồ phẳng với hệ tọa độ Descartes vuông góc Oxy. Nền pháo đài có dạng hình chữ nhật với các cạnh song song với một trong hai trục tọa độ. Những khảo sát gần đây tại vị trí \((x_0, y_0)\) đã khẳng định chắc chắn vị trí \((x_0,y_0)\) nằm trong pháo đài cổ xưa.

Em được yêu cầu xác định vị trí ban đầu của nền pháo đài cổ bằng một robot hoạt động theo quy trình sau. Tại mỗi bước, em yêu cầu robot đào sâu xuống khảo sát tại một vị trí do em lựa chọn. Robot sẽ báo cáo có tìm thấy dấu vết của pháo đài cổ tại vị trí đó hay không? Vì chi phí của mỗi lần khảo sát khá lớn nên em cần yêu cầu robot khảo sát tại càng ít vị trí càng tốt.

Nhiệm vụ của em là viết một chương trình có tên CITADEL.*, sử dụng các lệnh được cung cấp để thực hiện khảo sát các vị trí, nhận kết quả khảo sát và đưa ra đánh giá về vị trí chính xác của khu pháo đài cổ.

Input

• Hai số \(x_0, y_0\) được cho đầu chương trình.

Interaction

Để tương tác với máy chấm, em 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 ý, nhớ 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:

• find x y

Em chỉ được phép dùng lệnh này tối đa một triệu lần. Máy chấm in ra \(0\) hoặc \(1\):

+ 0 tương ứng với ***không*** tìm thấy dấu vết tại vị trí có tọa độ $(x,y)$. Nói cách khác là vị trí $(x,y)$ nằm phía ngoài nền pháo đài cổ.
+ 1 tương ứng với ***có*** tìm thấy dấu vết tại vị trí có tọa độ $(x,y)$. Nói cách khác là vị trí $(x,y)$ nằm ở phía trong hoặc trên biên nền của pháo đài cổ.
+ Nếu lệnh này được dùng quá một triệu lần, chương trình sẽ bị ngắt và ghi nhận $0$ điểm với test em đang chạy.

• answer x1 y1 x2 y2

Lệnh này chỉ được in ra đúng 1 lần trước khi kết thúc chương trình để cho biết về kết quả mà em xác định được; trong đó \((x_1, y_1)\) là tọa độ góc trái dưới của nền pháo đài, \((x_2, y_2)\) là tọa độ góc phải trên của nền pháo đài.

Chương trình bắt buộc phải in lệnh answer một lần duy nhất, nếu không sẽ bị 0 điểm. Sau khi em in ra lệnh này, chương trình sẽ được ngắt.

Scoring

Bài thi của em được chấm trên \(20\) test, mỗi test tối đa \(5\) điểm.

• Trong các test \(1,2,3,..,6\): tọa độ của pháo đài có giá trị tuyệt đối không vượt quá \(200\)
• Trong các test \(7,8,9,...,13\): tọa độ của pháo đài có giá trị tuyệt đối không vượt quá \(2 \times 10^5\)
• Trong các test còn lại \(14,14,15,...,20\): tọa độ của pháo đài có giá trị tuyệt đối không vượt quá \(2 \times 10^9\)

Với mỗi test, nếu chương trình của em in ra lệnh answer với các tham số không chính xác, chạy quá thời gian quy định 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 đó. Ngược lại, bài làm sẽ nhận được số điểm trong khoảng từ \(1\) đến \(5\) cho test đó phụ thuộc vào số lần sử dụng lệnh find nhiều hay ít.

Example

3 1
1
0
0
1
1
1
0
0
0

find 3 -1
find 3 -2
find -4 -1
find -1 1
find -3 1
find 8 2
find 9 3
find 9 1
find 7 3
answer -3 -1 8 2

Biết được việc các thí sinh thi Tin học trẻ giải được bài XEPHINH, người ngoài hành tinh rất yêu quý đất nước Việt Nam. Họ quyết định trở lại để đến thăm chúng ta. 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.

Example

7
cat
can
mic
man
tiger
hello
world

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:

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

??? warning "Note"

    - Độ 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.

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
  ```