Это интерактивная задача.
Кира загадал некое положительное целое число \(n\), а Хаято требуется его угадать.
Изначально Кира дает Хаято значение \(\mathrm{cnt}\) — количество единичных битов в двоичной записи \(n\). Для того чтобы угадать \(n\), Хаято может делать лишь операции одного типа: выбрать некоторое целое число \(x\) и вычесть его из \(n\). Обратите внимание, что после каждой операции число \(n\) изменяется. Кира не любит плохих запросов, поэтому если Хаято попробует вычесть число \(x\) большее, чем \(n\), то он проиграет Кире. После каждой операции Кира сообщает обновленное значение \(\mathrm{cnt}\) — количество единичных битов в двоичной записи обновленного значения \(n\).
У Киры не так много терпения, поэтому Хаято должен угадать изначальное значение числа \(n\) за не более чем \(30\) запросов.
Так как Хаято учится в начальной школе, он просит вашей помощи — напишите программу, которая угадывает число \(n\). Кира — честный человек, поэтому он зафиксирует значение \(n\) изначально и не станет как-то менять начальное число в зависимости от запросов Хаято.
Протокол взаимодействия
Для угадывания \(n\) вы можете не более \(30\) раз произвести описанную операцию. Для этого выведите строку в формете «- x» (\(1 \le x \le 10^9\)).
После этой операции из \(n\) вычитается число \(x\), и поэтому значение \(n\) изменяется. Если число \(x\) оказалось больше, чем текущее число \(n\), то такой запрос считается некорректным.
После каждой операции считайте одно неотрицательное целое число \(\mathrm{cnt}\) — количество единичных битов в двоичной записи текущего \(n\) после совершения операции.
Когда вы узнаете число \(n\), выведите одну строку следующего формата: «! n» (\(1 \le n \le 10^9\)).
После этого переходите к решению следующего набора входных данных или завершите программу, если таких нет.
Если ваша программа сделает более \(30\) операций для одного набора входных данных, вычтет число \(x\) большее, чем \(n\), или сделает некорректный запрос, то ответом на запрос будет -1, после получения такого ответа ваша программа должна немедленно завершится, чтобы получить вердикт Неправильный ответ. Иначе она может получить любой другой вердикт.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Чтобы сделать взлом, используйте следующий формат.
Первая строка должна содержать одно целое число \(t\) (\(1 \leq t \leq 500\)).
Каждый набор входных данных должен содержать одно целое число \(n\) (\(1 \leq n \leq 10^9\)) на отдельной строке.
Примечание
К примеру, количество единичных битов в числе \(6\) это \(2\), потому что двоичное представление \(6\) это \(110\). Для \(13\) количество единичных битов \(3\), так как \(13_{10} = 1101_2\).
В первом примере \(n = 1\), поэтому на вход дается число \(1\). После вычитания из \(n\) единицы оно становится нулевым, поэтому и количество единичных битов у него \(0\).
В третьем примере \(n = 3\), которое в двоичном представлении выглядит как \(3_{10} = 11_2\), следовательно на вход даётся количество единиц, то есть \(2\). После вычитания числа \(2\) мы имеем \(n = 1\), поэтому количество единичных битов теперь \(1\). После вычитания из \(n\) единицы оно становится равно нулю.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
0
1
1
0
2
1
0
|
- 1
! 1
- 1
- 1
! 2
- 2
- 1
! 3
|