D. Битовая угадайка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Кира загадал некое положительное целое число $$$n$$$, а Хаято требуется его угадать.

Изначально Кира дает Хаято значение $$$\mathrm{cnt}$$$ — количество единичных битов в двоичной записи $$$n$$$. Для того чтобы угадать $$$n$$$, Хаято может делать лишь операции одного типа: выбрать некоторое целое число $$$x$$$ и вычесть его из $$$n$$$. Обратите внимание, что после каждой операции число $$$n$$$ изменяется. Кира не любит плохих запросов, поэтому если Хаято попробует вычесть число $$$x$$$ большее, чем $$$n$$$, то он проиграет Кире. После каждой операции Кира сообщает обновленное значение $$$\mathrm{cnt}$$$ — количество единичных битов в двоичной записи обновленного значения $$$n$$$.

У Киры не так много терпения, поэтому Хаято должен угадать изначальное значение числа $$$n$$$ за не более чем $$$30$$$ запросов.

Так как Хаято учится в начальной школе, он просит вашей помощи — напишите программу, которая угадывает число $$$n$$$. Кира — честный человек, поэтому он зафиксирует значение $$$n$$$ изначально и не станет как-то менять начальное число в зависимости от запросов Хаято.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$\mathrm{cnt}$$$ — изначальное количество единичных битов в двоичной записи $$$n$$$.

Загаданное целое число $$$n$$$ удовлетворяет следующему ограничению $$$1 \le n \le 10^9$$$.

Протокол взаимодействия

Для угадывания $$$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$$$) на отдельной строке.

Пример
Входные данные
3

1

0

1

1

0

2

1

0
Выходные данные
- 1

! 1

- 1

- 1

! 2

- 2

- 1

! 3
Примечание

К примеру, количество единичных битов в числе $$$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$$$ единицы оно становится равно нулю.