Безумный ученый Майк только что завершил сборку новой установки для поиска внеземного разума! Он так торопился запустить ее в первый раз, что подключил провода питания не глядя и принялся за опыты. Впоследствии Майк заметил, что эти провода переплелись между собой и что их теперь придется распутывать.

Установку питают два провода: «плюс» и «минус», которые идут по полу от стены (слева) до самой установки (справа). Как в стене, так и в установке на одинаковой высоте имеется по два контакта, к которым в каком-то порядке подключены провода. Провода считаются запутанными, если есть места, где один провод проходит над другим. Например, на картинке ниже таких мест четыре (вид сверху):

Майк знает, в какой последовательности провода проходят друг над другом. Он также заметил, что слева провод «плюс» всегда подключен к верхнему контакту (так, как на картинке). Майк хотел бы распутать провода, не отсоединяя их от контактов и не трогая саму установку. Определите, удастся ли ему это сделать. Считайте, что провода можно передвигать как угодно, что провода могут произвольно растягиваться, но не могут рваться.

Для лучшего понимания задачи рекомендуется прочитать пояснения ко всем тестовым примерам.