Это двухпроходная (run-twice) задача; оба запуска являются интерактивными.
Вокруг широкого дуба стоят четыре мудреца. На голове у каждого мудреца надета красная, зелёная или синяя шляпа. Каждый мудрец видит цвета шляп обоих своих соседей, но не видит цвет своей собственной шляпы (шляпа не свисает на глаза) и не видит цвет шляпы мудреца, стоящего напротив него (его загораживает широкий дуб). Каждый мудрец должен, не общаясь с остальными, написать на листке бумаги цвет своей шляпы. Разработайте протокол, при котором хотя бы один из четырёх мудрецов гарантированно угадает цвет своей шляпы.
Протокол взаимодействия
Первая строка содержит два целых числа $t$ и $s$, обозначающих количество наборов входных данных и номер запуска решения ($1 \le t \le 100$; $s \in \{1, 2\}$). Далее следуют описания $t$ наборов входных данных, каждый на отдельной строке.
Если $s = 1$, набор входных данных состоит из четырёх слов $c_1$, $c_2$, $c_3$ и $c_4$, обозначающих цвета шляп участников ($c_i \in \{\texttt{red}, \texttt{green}, \texttt{blue}\}$). В ответ выведите строку с одним целым числом $m$ ($1 \le m \le 4$), обозначающим номер мудреца, который, согласно вашему протоколу, угадает цвет своей шляпы (если таких несколько, выведите любого).
Если $s = 2$, набор входных данных состоит из целого числа $m$ и двух слов $\ell$ и $r$, обозначающих номер мудреца, который должен угадать цвет своей шляпы, а также цвета шляп его левого и правого соседей ($1 \le m \le 4$; $\ell, r \in \{\texttt{red}, \texttt{green}, \texttt{blue}\}$; $\ell = c_{(m+2) \bmod 4 + 1}$; $r = c_{m \bmod 4 + 1}$). В ответ выведите строку со словом $g$ — цветом шляпы $m$-го мудреца. Ответ будет засчитан, если $g = c_m$. Интерактор нечувствителен к регистру, поэтому вы можете выводить каждую букву в любом регистре (верхнем или нижнем).
Чтобы предотвратить передачу информации между наборами входных данных, жюри приняло следующие меры:
- Оба запуска являются интерактивными. Таким образом, вы не получите следующий набор входных данных, пока не выведете ответы на все предыдущие. После вывода каждой строки не забывайте сбрасывать буфер вывода (например, с помощью
fflush(stdout)илиcout.flush()в C++,sys.stdout.flush()в Python илиSystem.out.flush()в Java или Kotlin). В противном случае вы, скорее всего, получите вердикт Idleness Limit Exceeded. - Во время второго запуска жюри может переставить $t$ наборов входных данных в произвольном порядке, который может не совпадать с порядком их следования в первом запуске.
- Во время второго запуска жюри также может добавить фиктивные наборы входных данных, которые не соответствуют ни одному набору из первого запуска. Для таких наборов любой из ответов «
red», «green» или «blue» будет считаться правильным; они нужны лишь для того, чтобы ваша программа не могла легко отличить настоящий набор входных данных от фиктивного и передать информацию между наборами. Таким образом, число $t$ во втором запуске может превышать $t$ в первом запуске. Суммарное количество настоящих и фиктивных наборов не превышает $100$.
Примеры
Входные данные 1
1 1 green red blue red
Выходные данные 1
2
Входные данные 2
4 2 2 blue green 4 red blue 3 red red 4 red blue
Выходные данные 2
blue BLUE blUE Blue