Bitek has found a treasure – a chest with a certain positive integer number of coins $x$. Bajtosia, considering the dimensions of the chest, cleverly deduced that the number of coins inside does not exceed $n$. However, she would like to know exactly how many there are. Bitek does not want to tell her, but he has agreed to play a game with her. Bajtosia can provide him with a positive integer $m$, and he will answer one of two questions: What is the integer part of the division of the number of coins in the chest by $m$? What is the remainder of the division of the number of coins in the chest by $m$?

Note that Bitek chooses which question to answer and communicates to Bajtosia both the chosen question and the answer to that question.

Bitek is too busy thinking about how to invest his money, so he has agreed to answer only a few questions. Will you help Bajtosia, despite this, to skillfully ask questions and determine the number of coins?

Interaction

This is an interactive task. Write a program that will ask Bitek questions on behalf of Bajtosia and guess $x$ using the provided library. To use the library, include the following in your program: C++: #include "skalib.h" Python: from skalib import daj_ograniczenie, zapytaj, odpowiedz

Your program will be compiled/run using the command: C++: g++ -O3 -static ska.cpp skalib.cpp -std=c++20 Python: python3 ska.py

To learn the upper bound on the number of coins in the chest determined by Bajtosia, you can call the function: C++: unsigned long long daj_ograniczenie() Python: daj_ograniczenie() -> int

To ask Bitek questions, call the function: C++: std::pair<char, unsigned long long> zapytaj(unsigned long long m) Python: zapytaj(m : int) -> tuple[str, int]

Each call to this function yields one of two possible answers: a pair ('/', w), meaning that $\lfloor x/m \rfloor = w$ (the integer part of dividing $x$ by $m$ is equal to $w$), a pair ('%', w), meaning that $x \equiv w \pmod m$ (the remainder of dividing $x$ by $m$ is equal to $w$).

To tell Bajtosia how many coins are in the chest, call the function: C++: void odpowiedz(unsigned long long x) Python: odpowiedz(x : int) -> ()

with the determined value of $x$. After calling this function, you must terminate the program immediately.

Your program must not open any files or use standard input and output. It may use standard diagnostic output (stderr), but remember that this consumes valuable time.

Examples

Test 0 in SIO corresponds to the case where $n = 100$ and $x = 48$.

Subtasks

To achieve the maximum score, the zapytaj function may be called at most four times. However, it is possible to obtain a partial score even if this limit is exceeded (see the table below).

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

Let $q$ denote the number of calls to the zapytaj function. Points for a test are awarded according to the table below.

If the zapytaj function is called with a parameter equal to 0, or the parameter $x$ of the odpowiedz function is different from the expected one, your program will receive a "Wrong Answer" verdict and 0 points for the test.

In some tests, the library may be adaptive – i.e., it does not fix the value of $x$ at the beginning and does not fix how it will react to every possible question. You can assume that at any moment of the interaction, there exists at least one number $x$ consistent with the answers given so far.

Note

In the Files and tests section in SIO, you can find an example implementation of the library. This implementation gives every second answer as '%' and every other as '/'. The library used to check solutions may choose different answers to questions.

Note: In this task, trial runs in SIO and the ocen script on computers are not available.

Hint: In C++, the standard compiler provides a 128-bit signed integer type named __int128. Please note that values of this type cannot be read or written in the standard way.