시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB86675.000%

문제

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

Д'Артаньян решил подарить Констанции на День Святого Валентина замечательное колье с бриллиантами. Посчитав все свои сбережения, он выяснил, что у него есть ровно $2a+1$ монета, половина из которых золотые, а половина --- серебряные (то есть у него либо $a$ золотых и $a+1$ серебряная монета, либо наоборот). Однако Д'Артаньян точно помнил, что у него было четное число монет, то есть видимо кто-то подложил ему еще одну монету, которая наверняка фальшивая. Д'Артаньян знает, что настоящие серебрянные и золотые монеты весят одинаково, а фальшивая может весить по-разному: если она золотая, то она весит меньше настоящей, а если серебрянная, то больше.

К счастью, у мушкетера нашлись чашечные весы, с помощью которых он может брать две кучки монет, класть их на левую и правую чаши весов и узнавать, какая из кучек монет тяжелее (или что они весят одинаково). Времени у Д'Артаньяна мало, поэтому он успеет провести только $t$ взвешиваний. Помогите ему отыскать фальшивую монету.

인터랙션

В самом начале программа жюри сообщает вашей программе три натуральных числа $a$, $b$, $t$ ($|a-b|=1$) --- количество золотых и серебряных монет соответственно и количество ходов, за которое надо найти фальшивую монету. Золотые монета имеют номера от 1 до $a$, серебрянные - от $a+1$ до $a+b$.

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

  • Если вы уверены, что знаете номер фальшивой монеты, в единственной строке выведите $0$ $x$, где $x$ --- номер фальшивой монеты, и завершите программу;
  • Если нет, ваша программа сообщает программе жюри две последовательности чисел в двух разных строках. В первой строке записаны номера монет, которые следует положить на левую чашу весов в формате $k$ $a_1$ $a_2$ $\ldots$ $a_k$. Во второй строке записаны номера монет, которые следует положить на правую чашу весов в том же формате.
  • программа жюри сообщает вашей программе:
    • <<<>>, если монеты на левой чаше имеют вес меньше монет на правой;
    • <<=>>, если вес чаш одинаковый;
    • <<>>>, если монеты на левой чаше имеют вес больше монет на правой
  • После этого действия выше выполняются заново

예제 입력 1

1 2 2
=

예제 출력 1

1 1
1 3
0 2

예제 입력 2

2 1 2
<

예제 출력 2

1 1
1 2
0 1

힌트

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

  • В языке Pascal: flush(output);
  • В C/C++: fflush(stdout);
  • В Java: System.out.flush();
  • В Python: sys.stdout.flush();

Кроме этого, не забывайте после каждой выведенной строки ставить перевод строки.

채점 및 기타 정보

  • 예제는 채점하지 않는다.