Фальшивая монета

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

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

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

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

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

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