477. Вперёд в прошлое

Док Браун случайно проговорился Марти Макфлаю, что одно событие в прошлом имело роковые последствия для его семьи. Марти хочет отправиться в день, когда произошло это событие, чтобы предотвратить его и изменить будущее. Док опасается, что это может нарушить пространственно-временной континуум, и отказывается назвать Марти роковую дату. Но Марти очень настойчив, и тогда Док, в надежде, что тот не справится, предлагает Марти сыграть в игру, чтобы вычислить эту дату. Условия игры такие:

1. Док в тайном блокноте выписал множество разных дат, расположив их в хронологическом порядке. Он ни под каким предлогом не показывает этот блокнот Марти.

2. Оказалось, что дата, куда хочет отправиться Марти, расположилась ровно в середине списка. Причём список имеет нечётную длину. Обо всём этом Док рассказал Марти.

3. Каждый день Марти отправляет Доку письмо, где пишет предполагаемую нужную ему дату. Док получает письмо, смотрит на дату, открывает свой тайный блокнот и считает количество событий, которые произошли до этой даты включительно, а затем пишет Марти ответную записку, где указывает это число.

4. Пункты 2–3 повторяются, пока Марти не определит точную дату события.

Марти очень хочет как можно скорее отправиться в прошлое и помочь своей семье. При этом Док установил ему предельное количество попыток $N$, за которые Марти должен угадать нужную дату. Марти просит вас написать компьютерную программу, которая поможет ему в этом.

Эта задача немного необычна: в ней вам предстоит реализовать интерактивное взаимодействие с тестирующей системой. Это означает, что вы можете делать запросы и получать ответы в онлайн-режиме.

Для чтения ответов тестирующей системы программа должна использовать стандартный ввод.

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

Известно, что все даты Дока находятся в промежутке $[01.01.1970...31.12.2020]$ и что существует алгоритм, позволяющий угадать дату за требуемое количество попыток. Все даты заданы в формате $dd.mm.yyyy$. В таком же формате их необходимо задавать в запросах к тестирующей системе.

В следующих строках на вход вашей программе будут подаваться строки, содержащие информацию об ответе Дока. $i$-я из этих строк является ответом системы на ваш $i$-й запрос.

Ваша программа должна выводить запросы к тестирующей системе и обрабатывать ответы от неё. После вывода каждой строки программа должна выполнить операцию $flush$. Ответ на запрос программа сможет прочесть из стандартного ввода.

Доступные ответы системы:

• $? \thinspace K$

  — ответ тестирующей системы, означающий, что до посланной проверяемой даты находятся $K$ дат ($0 \le K \le 20000$).

• $!$

  — ответ тестирующей системы, означающий, что превышено количество попыток $N$ угадать нужную дату.

Для запросов к тестирующей системе программа должна использовать стандартный вывод.

Доступные запросы системы:

• $? \thinspace M$

  — проверить, является ли дата $M$ ($01.01.1970 \le M \le 31.12.2020$) нужной датой.

• $! \thinspace M$

  — указать, что дата $M$ ($01.01.1970 \le M \le 31.12.2020$) является нужной. После того как ваша программа вывела данную команду, следует завершить работу.

Приложение должно отвечать тестирующей системе непрерывно одной из описанных команд, пока либо дата не будет угадана, либо приложение не получит команду $!$ на завершение от тестирующей системы. Если приложение перестанет отвечать, а дата не будет угадана, вы получите ошибку Presentation Error или Time Limit Exceeded.

Обратите внимание, что ввод/вывод в задаче — стандартный, то есть с экрана на экран. При написании решения для интерактивной задачи важно помнить, что если вы что-то вывели, то без специального указания в программе эти данные могут на самом деле попасть во внутренний буфер и не быть выведенными немедленно. После вывода очередного запроса обязательно используйте функции очистки потока, чтобы часть вывода не осталась в каком-нибудь буфере. Например, на Java, Kotlin вызывайте $System.out.flush()$. В языках Swift, Objective C можно применять $fflush(stdout)$. Подробнее Для языка Dart необходимо вызвать stdout.flush() из dart:io.