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

Еще в Галактике есть небольшая планета Сарк и ее колония Флорина, которые по богатству могут соперничать с Трантором. Все потому, что Флорина — единственная планета в Галактике, где растет кырт. Кырт — растение, чем-то похожее на земной хлопок, однако кыртовые нити обладали великолепными физическими свойствами, их использовали для изготовления различной техники, а еще из кырта шили дорогую одежду. Так маленькая планета Флорина обеспечивала кыртом сотни тысяч, а то и миллионы миров.

Такие объемы поставок предполагают ведение подробной отчетности. Отдел статистика Сарка попросил вас составить отчет о различии поставок кырта для ткани и кырта для технических нужд на $$$n$$$ планет. Документы о самих поставках вам найти не удалось, однако есть два других статистических отчета. Каждый отчет представляет собой двоичную строку длины $$$n$$$. В первом отчете $$$i$$$-й символ равен $$$1$$$, если на $$$i$$$-ю планету поставляются оба вида кырта, и $$$0$$$ в противном случае. Во втором отчете $$$i$$$-й символ равен $$$1$$$, если на $$$i$$$-ю планету поставляется хотя бы один вид кырта, и $$$0$$$ в противном случае. На основании этих данных предоставьте отчет, в котором $$$1$$$ будет соответствовать тем планетам, куда поставляется только один из двух видов кырта.

В космопорте Сарка было полученно странное сообщение. Представитель Межзвездного Космоаналитического Бюро утверждал, что Флорине угрожает огромная опасность, что она в скором времени будет уничтожена, и просил разрешения на посадку в порту. Впрочем, к сообщению не отнеслись серьезно. Космоанализ — это очень сложный и запутанный раздел астрофизики, а космоаналитики зачастую отличались нестандартным образом мышления. Порой случалось, что погрузившись в работу, они теряли рассудок и нуждались в психиатрической помощи. Может быть, такое мнение о космоаналитиках — не более чем стереотип, однако было решено встретить прибывшего с каретой "скорой помощи".

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

Для этого начальник космопорта решил узнать, с какой частотой может получать сообщение с корабля устройство приема. С корабля передается сообщение, закодированное двоичной строкой $$$s$$$, $$$s_i =$$$ '$$$0$$$', если в $$$i$$$-ю наносекунду приема сообщение принималось, или '$$$1$$$', если в этот момент были помехи. Гарантируется, что приемник распознал начало и конец сообщения, то есть первый и последний символы строки равны '$$$0$$$'. Начальник космопорта проводит $$$m$$$ проверок, пытаясь принимать сообщение с ограничением частоты $$$k_i$$$ — максимальным временем между приемами частей сообщения. Более формально, устройство может принимать шум, вызванный помехами, строго меньше $$$k_i$$$ наносекунд подряд, иначе сообщение не будет получено полностью. Для каждого $$$k_i$$$ начальник хочет узнать, можно ли принять все части сообщения, не испорченные помехами, соблюдая описанные условия.

В Межзвездном Космоаналитическом Бюро очень удивились, узнав, что сообщение от космоаналитика на Сарке получено не было. Более того, самого космоаналитика нигде не могли найти... Не могли найти в течении целого года.

Через несколько недель на Флорине, неподалеку одной из кыртовых фабрик Валлона Марч нашла человека, потерявшего память. Его подвергли психозондированию, уничтожив часть его воспоминаний и спрятав остальные в глубинах сознания. Управляющий фабрикой, резидент Мирлин Теренс, разрешил Валлоне взять найденыша себе на попечение, добился для нее дополнительного пайка и талонов на одежду — сделал все, чтобы двое взрослых (из них один незарегистрированный) могли прожить на жалованье одного. Валлону такое положение вполне устраивало: красавицей она не была, поэтому пока остальные девушки нянчили собственных детей, Валлона занималась Риком — так назвали умалишенного (и поверьте, забот с ним поначалу было не меньше).

Через некоторое время к Рику начала постепенно возвращаться память, и пусть он ничего не помнил о своем прошлом, он уже работал на фабрике. И вот сегодня утром по дороге на свое рабочее место Рик столкнулся с Валлоной. Столкнулся в прямом смысле этого слова, потому что людей на фабрике было много, и все куда-то ужасно спешили, что сильно затрудняло перемещение. Фабрика представляет собой $$$n$$$ помещений, соединенных $$$n - 1$$$ двусторонними коридорами таким образом, чтобы между любыми двумя помещениями существовал ровно один путь. Рик подумал: а что если утром сделать движение по всем коридорам односторонним, чтобы избежать подобных столкновений? Идея может и неплохая, но при этом из некоторых помещений нельзя будет добраться в удаленные части фабрики. А самому Рику, Валлоне, да и остальным рабочим надо было попасть в определенные места. Рику известно про $$$m$$$ человек, что с утра они должны дойти из помещения $$$s_i$$$ в помещение $$$f_i$$$, поэтому коридоры на их пути надо ориентировать таким образом, чтобы возможность перемещения из начала пути $$$s_i$$$ в конец $$$f_i$$$ не пропадала.

Сознание Рика еще не до конца прояснилось, поэтому он просит вас узнать, можно ли ориентировать все коридоры требуемым способом?

Флорина была единственной планетой во всей Галактике, где выращивали кырт. И дело не в том, что местные власти исправно следили за порядком, запрещали продажу кырта и ловили всех контрабандистов. Напротив, семена кырта свободно продавались, причем по выгодной цене. Только вот ни на одной другой планете кырт не рос, а из его семян вырастал обычный бесполезный хлопок. Перепробовали все: брали образцы почвы Флорины, строили искусственные источники света, повторяющие спектр флоринианского солнца, заражали почву различными бактериями — но это не помогало. Химики клялись, что кырт — просто разновидность целлюлозы. Однако когда их спрашивали, почему именно здесь целлюлоза становится кыртом, они лишались дара речи. Все объяснения сводились к тому, что кырт — это кырт, потому что он кырт.

Кырт находил себе применение везде — в нитяных крестах оптических инструментов, в гиператомных моторах, однако большая его часть шла на изготовление великолепной ткани, из которой шили самые лучшие одеяния в Галактике. Но кырта требовалось очень много, и поэтому большая часть Флорины была занята полями и фабриками.

Вам предлагается помочь оптимизировать работу одной из таких фабрик. Фабрика находится посреди большого кыртового поля, в точке $$$O$$$. Также есть $$$n$$$ пунктов сбора, где специальные машины собирают кырт, после чего его везут на фабрику. При этом, чтобы при транспортировке машины не сталкивались, на любой прямой, проходящей через фабрику, расположено не более двух пунктов сбора. Для оптимизации этого процесса вам предложено выбрать две пары пунктов сбора, таких что отрезки, соединяющие каждую пару, пересекаются в точке $$$O$$$, чтобы заменить машины, перевозящие кырт с этих пунктов, на две прямые транспортные линии и одну кольцевую. Чтобы была возможность построить кольцевую линию, необходимо, чтобы выбранные четыре пункта находились на одной окружности. Поэтому вам требуется ответить на вопрос: найдутся ли четыре пункта, удовлетворяющие названному условию и лежащие на одной окружности?

Доктор Селим Джунц из Межзвездного Космоаналитического Бюро вот уже как одиннадцать месяцев находился на Сарке. Он прибыл сюда, чтобы расследовать исчезновение своего коллеги, и обратился к саркитским властям, однако все поиски не давали никаких результатов. Тогда Селим начал подозревать: а вдруг от него что-то скрывают?

Селим много лет работал с Риком, и поэтому уверен, что тот не мог отступиться от своей идеи и улететь далеко. Остается два варианта — либо он сел на какой-либо другой планете в ближайшем пространстве, либо его силой удерживают на Сарке. Найти друга в одиночку на целой планете, а может и двух, не представлялось возможным, поэтому Селим решил начать поиски с обнаружения энергетического спектра корабля Рика.

Благодаря современным технологиям и качественному оборудованию Селим через несколько часов уже имел результат анализа, закодированный строкой $$$s$$$ из символов латинского алфавита. Однако программного обеспечения, чтобы его расшифровать, у Селима не было, а людям с Сарка он не доверяет, поэтому он просит вас определить результат. Результатом анализа является число подпоследовательностей этой строки вида $$$f_i$$$ для какого-либо $$$1 \leq i \leq 26$$$:

• $$$f_1 = $$$ "$$$a$$$";
• $$$f_i = f_{i-1} + c_i + f_{i-1}$$$, где $$$'+'$$$ — операция конкатенации, а $$$c_i$$$ — $$$i$$$-й символ латинского алфавита, $$$2 \leq i \leq 26$$$.

Прошел почти год с момента, как Рик оказался на Флорине, однако его сознание никак не прояснялось. Воспоминания о прошлом были спрятаны в глубинах его разума, а может и вовсе утеряны. Однако сегодня что-то случилось. Рик вспомнил: у него была работа. Он анализировал Ничто. Наверное, Ничто — это космос, а значит Рик в прошлом был космоаналитиком. А еще Рик вспомнил, что все жители Флорины должны были погибнуть, но он не знал, почему.

Резидента Мирлина Теренса заинтересовала эта информация, поэтому он взял Рика с собой в библиотеку Верхнего города. Может быть, какая-нибудь литература по космоанализу могла бы вернуть ему память? Теренс не знал, что пропавшего космоаналитика активно ищут, а потому в библиотеке был получен приказ сообщать о любых посетителях, которые спросят о такой литературе. Библиотекарь отследил запросы наших героев в поисковой системе и поспешил вызвать патрульных.

Тем временем Теренс предложил Рику ознакомиться с книгой известного автора Врийта "Трактат об инструментальном космоанализе". Рику книга определенно показалось знакомой, особенно его привлекла строка $$$s$$$. Смысла самой строки, он, к сожалению, не понимал, однако в ее частях он видел что-то знакомое. Чтобы разобраться подробнее, Рик решил изучить все подстроки $$$s$$$. Однако изучать равные подстроки не было смысла, а остальные стоило как-либо систематизировать. Например, расставить их по длине и в алфавитном порядке. Поэтому Рик попросил вас узнать, сколько у данной строки существует пар подстрок $$$s_1$$$ и $$$s_2$$$ равной длины, таких, что $$$s_1 \lt s_2$$$ лексикографически.

Поиски книг о космическом анализе привлекли много внимания, и двое патрульных попытались задержать Рика и Мирлина Теренса. К счастью, на помощь к ним пришла Валлона, и, оглушив нейрохлыстом патрульных, наши герои сбежали обратно в Нижний город. Незамедлительно за ними был выслан целый отряд патрульных, но в Нижнем городе нашелся человек, котрый был готов спрятать беглецов от патрульных. Транторианский агент Матт Хоров укрыл Рика и Валлону в своей пекарне, а Теренс тем временем отправился домой — отсутствие резидента в течение дня могли заметить, а привлекать лишнее внимание Теренс не хотел.

На следующее утро Матт решил отправить Рика и Валлону с Флорины, где им угрожала опасность, на какую-нибудь другую планету. Хоров выдал им поддельные паспорта и билеты на корабль до Вотекса, но оставалась нерешенная проблема — огромное количество патрульных в Верхнем городе. Но Матт Хоров мог использовать других агентов, чтобы доставить Рика и Валлону в космопорт.

Чтобы не привлекать излишнего внимания, Матт решил, что поднимутся они не у самого космопорта, а в каком-либо из $$$8$$$ кварталов Верхнего города, затем проедут по некоторым из этих кварталов, вероятно, не по одному разу, а затем из последнего посещенного квартала отправятся прямо в космопорт. Сопровождать Рика и Валлону будут некоторые из $$$n$$$ агентов Хорова. Для каждого агента известно, из каких кварталов в какие он может перемещаться. Путешествие проходит следующим образом: Рик с Валлоной поднимаются в одном из кварталов, где их встречает первый агент. За один доступный ему переезд он добирается до некоторого следующего квартала, где его ждет второй агент, который везет их до следующего квартала, и так далее до последнего квартала перед космопортом.

Чтобы сбежать от возможной погони, Матт хочет рассмотреть разные маршруты. Он уже придумал $$$m$$$ планов, каждый состоит из стартового квартала $$$s_i$$$, конечного квартала $$$t_i$$$, а также чисел $$$l_i$$$ и $$$r_i$$$ — Рика и Валлону будут сопровождать агенты с $$$l_i$$$-го по $$$r_i$$$-го включительно, в порядке следования их номеров. Таким образом, в квартале $$$s_i$$$ их встречает $$$l_i$$$ агент и перемещается с ними в некоторый следующий квартал, где их поджидает $$$l_{i+1}$$$ агент, который помогает им переместиться в другой квартал, и так далее. Наконец $$$r_i$$$ агент должен доставить Рика и Валлону в квартал $$$t_i$$$. При этом Матт выбирал агентов обдуманно, по этому никакой из отрезков $$$[l_i; r_i]$$$ не вложен в другой. Формально, не существует таких $$$i$$$ и $$$j$$$, таких что $$$l_i \lt l_j \leq r_j \lt r_i$$$.

Для каждого из планов Матт хочет узнать число различных путей, которыми данные агенты могут доставить из стартового квартала в конечный, по модулю $$$998244353$$$. Пути считаются различными, если существует номер $$$l \leq k \leq r$$$, такой что после поездки с $$$k$$$-м агентом по этим путям Рик с Валлоной добрались бы до разных кварталов. Обратите внимание, что для запутывания следов они могут посещать один квартал несколько раз, в том числе подряд.

Кырт был основным источником дохода для всего Сарка, выводя его экономику на второе место в Галактике, разумеется, после Трантора, под контролем которого была не одна сотня тысяч других планет. Его физические характеристики поражали: он мог сиять на солнце любым цветом или всем спектром сразу, был невосприимчив ко многим химическим веществам, а по прочности ему уступали любые сорта стали. Однако ученым никак не удавалось понять, чем вызваны столь необычные свойства.

Сэмия Файфская, дочь великого сквайра Файфа, хоть и была высокородной дамой, тоже интересовалась этим вопросом. Другие аристократки относились пренебрежительно к увлечению наукой, однако Сэмию это ничуть не волновало. Вот уже пять лет она подробно изучала свойства кырта, планету, где он рос, и людей, которые его выращивали. Она настояла на том, чтобы полететь на Флорину, хотела провести несколько месяцев на полях и на фабрике. Но новости о нападении на патрульных уже дошли до Сарка, и отец приказал Сэмии вернуться домой ради её же безопасности.

Конечно, возвращаться Сэмии совсем не хотелось. Она понимала, что как только нарушители порядка будут пойманы, а их преступления расследованы, отец разрешить Сэмии вернуться. Но она еще не провела серию особенно важных экспериментов с кыртом, откладывать которые было нельзя. Предстояло провести $$$n$$$ опытов, для каждого из которых нужно было специальное оборудование. Чтобы настроить оборудование для $$$i$$$-го эксперимента, требовалось $$$t_i$$$ минут, и столько же, чтобы убрать это оборудование из лаборатории. К счастью, лаборантов у Сэмии достаточно, поэтому заниматься оборудованием от прошлого эксперимента и готовить новое можно параллельно. Таким образом, если подряд проводятся эксперименты с номерами $$$i$$$ и $$$j$$$, то между ними должно пройти $$$\max(t_i, t_j)$$$ времени. Времени до эвакуации осталось немного, поэтому она может поменять местами эксперименты, чтобы провести их быстрее. Время на подготовку к первому эксперименту, а также на приведение лаборатории в порядок в конце можно не учитывать. Сами опыты занимают пренебрежимо мало времени — Сэмии достаточно провести измерения, а расчетами и вычислениями она сможет заняться и на Сарке.

Сэмия просит вас узнать, в каком порядке нужно провести эксперименты, чтобы суммарно они заняли как можно меньше времени?

Наши герои добрались до космопорта, однако незамеченными им остаться не удалось — почти у самого космопорта они наткнулись на отряд патрульных. Рик с Валлоной чудом смогли сбежать, а сопровождавшему их агенту повезло намного меньше. Но вот они показывают свои недавно полученные паспорта и получают пропуск на корабль до Вотекса, уже ожидающий их на взлетной площадке. Однако теперь их ищут, и сложившиеся обстоятельства требовали отчаянных действий. Неподалеку от их корабля оказался другой, поменьше, на который можно было легко проникнуть. Этот корабль проветривали между полетами, чтобы избавиться от излишков сжатого кислорода, поэтому на корабле не было ни души. Рик и Валлона пробрались внутрь, и затаились в грузовом отсеке. Надо же было из всех кораблей попасть именно на корабль Сэмии Файфской, дочери самого влиятельного человека на всем Сарке!

Тем временем Рик продолжал вспоминать разные моменты из своего прошлого. Ему пришла в голову задача, которую он встретил несколько лет назад. Дано натуральное число $$$n$$$, и на доске изначально написано $$$n \times n$$$. Затем $$$k$$$ раз проделывают следующую операцию: вместо каждого вхождения $$$n \times n$$$ записывается $$$n$$$ раз число $$$n$$$. Далее между парами этих чисел ставят скобки, объединяя первое со вторым, третье с четвертым, и так далее. Если число $$$n$$$ нечетно, то последнее его вхождение в этой записи не заключается в скобки. Затем внутри этих скобок ставится символ "$$$\times$$$", а между скобками или перед последним числом $$$n$$$ — обыкновенное умножение "$$$\cdot$$$".

После $$$k$$$-й итерации данного процесса, все оставшиеся вхождения "$$$\times$$$" так же заменяются на "$$$\cdot$$$". Рика интересует, сколько символов умножения будет написано на доске после выполнения всех вышеперечисленных операций?

Мирлин Теренс тщетно пытался спасти Рика и Валлону от агентов Трантора. Переодевшись патрульным, он разыскивал их по всему Верхнему городу, однако никак не мог напасть на их след. Встреча произошла уже недалеко и космопорта, но тут завязалась перестрелка между Теренсом и агентом, а Рик и Валлона, не узнав Мирлина, сбежали, и уже летели на космическом корабле до Сарка. Теренс понимал, что не может лететь вслед за ними на корабле — его тут же узнают. Однако у многих зажиточных граждан Верхнего города были космические яхты, путешествие на которой вызвало бы намного меньше подозрений. Конечно, Теренс к этим гражданам не относился и ключей от яхты не имел, но форма патрульного, оружие и полумрак ночных улиц помогли их раздобыть.

Теренс все еще должен был оставаться незамеченным, и потому ему стоило избегать встречи с патрульными. Квартал рядом с портом состоит из $$$n$$$ перекрестков, соединенных $$$m$$$ дорожками с односторонним движением, для каждой дорожки известно, за какое время ее можно преодолеть. Посреди ночи по кварталу ходили всего двое патрульных, которые сейчас находятся на перекрестках $$$s_1$$$ и $$$s_2$$$. По рации, отобранной у патрульного, Теренс узнал, что они должны обойти $$$k$$$ перекрестков $$$p_1, p_2, ... p_k$$$ в заданном порядке (один перекресток может встречаться в этом списке несколько раз). Обходить они будут по одному, то есть на каждом из заданных перекрестков может побывать один из патрульных. Они действуют следующим образом: сначала какой-либо из патрульных доходит до перекрестка $$$p_1$$$ и сообщает об этом напарнику. После этого какой-либо патрульный начинает свое движение до перекрестка $$$p_2$$$. Так происходит, пока патрульные не осмотрят перекресток $$$p_k$$$, после чего их смена заканчивается. Если в какой-то момент патрульным необходимо проверить перекресток $$$i$$$, и какой-то из патрульных как раз находится на этом перекрестке, они переходят к проверке следующего перекрестка. При необходимости патрульные могут находиться на одном перекрестке. Патрульные хотят как можно быстрее закончить свою работу, а потому выбирают пути и разделяют между собой перекрестки таким образом, чтобы обход занял минимальное время.

Мирлин Теренс решил, что проще всего проникнуть в порт во время смены патрульных. Поэтому он спрашивает вас: сколько времени патрульные будут совершать обход, если они выбирают свои пути оптимально?

Мирлин Теренс успешно добрался до космопорта Верхнего города, раздобыл ключи от космической яхты, с легкостью проник внутрь. Но в яхтах Теренс совсем не разбирался и водить их не умел, поэтому агент отдела безопасности Сарка Маркис Генро быстро разоблачил самозванца, и скоро корабль с преступником приземлится в одном из космопортов столицы.

Однако Теренс является важной фигурой в истории пропавшего космоаналитика, и поэтому Людиган Эбл, представитель Транторианской империи на Сарке не может допустить попадания Теренса в руки правительства. Однако взять его еще на Флорине у агентов Эбла не получилось, поэтому осталась последняя возможность — перехватить его в одном из космопортов.

В главном городе Сарка есть $$$m$$$ космопортов, но Эбл точно не знает, в каком из них приземлится корабль Теренса. У него есть $$$n$$$ агентов, которых можно отправить совершать перехват. Для каждого агента Эбл выберет один из космопортов, куда он отправится. Можно отправить более одного агента в один космопорт, однако нельзя полагаться на волю случая, и в каждом космопорте должен находиться хотя бы один агент.

Корабль будет в пути еще несколько часов, и Эбл хочет продумать разные варианты проведения операции. Его интересует, сколько существует способов распределить агентов таким образом, чтобы все космопорты были под контролем. Он понимает, что это число может оказаться очень большим, поэтому его интересует остаток от деления числа способов на $$$998244353$$$.

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

После вывода очередной строки не забывайте очищать буфер потока вывода после каждого запроса. Для этого можно, например, воспользоваться командами fflush(stdout), cout.flush(), либо выполнять перевод строки при помощи endl в C++, system.out.flush() в Java, flush(output) в Pascal или sys.stdout.flush() в Python.

Сарком управлял совет Великих сквайров. В совете состояло пятеро саркитов, и самый богатый и влиятельный из них, сквайр Файф, взял на себя ответственность разобраться в истории космоаналитика. Волей случая к нему попал и Рик, который оказался космоаналитиком, а Селим Джунц и Людиган Эбл из посольства Трантора были готовы с ним сотрудничать. Сквайра интересовало одно — кто же мог совершить столь ужасное преступление?

Еще раньше Великому сквайру поступали анонимные письма, в которых сообщалось, что Флорина должна погибнуть. Шантажист требовал отдать значительную долю кыртовых полей Файфа за эту информацию. Сквайр подозревал, что если преступник смог похитить космоаналитика, прятать его целый год от властей и при этом шантажировать самого главного человека на всем Сарке, он тоже должен быть Великим сквайром. И больше всего подозрений вызывал у него сквайр Стин.

Тут неожиданно Рик вспомнил, что во время разговора с похитителем, тот сообщил размер его владений на Флорине — $$$k$$$ квадратных километров. В архиве хранятся данные о площади земель $$$s_i$$$, контролируемых сквайром Стином, в $$$n$$$ моментов времени. Файфу известно, что все $$$s_i$$$ различны, а так же что до некоторого момента эти площади увеличивались, а потом начали убывать. Более формально, существует такое $$$1 \leq t \leq n$$$, что для любого $$$1 \lt i \leq t$$$ $$$s_{i - 1} \lt s_{i}$$$ и для любого $$$t \lt j \leq n$$$ $$$s_{j - 1} \gt s_j$$$. Чтобы подтвердить свою правоту, Великому сквайру нужно узнать, в какой момент времени площадь владений Стина в точности равнялась $$$k$$$, и он просит вас помочь ему. Вы можете по моменту времени $$$i$$$ узнать размер владений сквайра Стина $$$s_i$$$. Небольшая сложность состоит в том, что времени у Файфа мало, а направление запроса в архив происходит достаточно долго. Поэтому у вас есть возможность задать не более 80 таких запросов. Сквайр не сомневается в своем в успехе, и гарантирует вам, что искомое $$$s_i$$$ существует.

Изначально вам заданы два числа $$$n, k$$$ — количество записей о владениях Стина в архиве и значение площади, которое интересует Файфа ($$$2 \leq n \leq 2 \cdot 10^5, 0 \leq k \leq 10^9$$$). Далее ваша программа может делать запросы вида "? $$$i$$$", в качестве ответа на которые программа жюри будет выводить значения $$$s_i$$$. Все $$$s_i$$$ - целые числа, $$$0 \leq s_i \leq 10^9$$$. Записи в архиве нумеруются с $$$1$$$. Когда ваша программа будет готова дать ответ, она должна вывести "! $$$i$$$", где $$$s_i = k$$$, и завершиться. Если ваша программа сделает больше 80 запросов первого типа, решение получит вердикт "Wrong answer". Если программа не завершится после запроса второго типа или ответ на запрос второго типа будет неверным, решение также получит вердикт "Wrong answer".

В конце концов к Рику вернулась память, виновные в его похищении были арестованы, жители Сарка и Флорины узнали, в чем заключалась его теория, поняли, что она верна, и приняли соответствующие меры... Но мы не будем лишать вас удовольствия прочитать "Космические течения" Айзека Азимова, и узнать окончание этой истории самим. Вместо этого в последней задаче мы предлагаем вам сыграть в игру "Red-7".

Есть колода из 49 карт. На каждой карте написано число от $$$1$$$ до $$$7$$$, также каждая карта имеет один из следующих цветов (в скобках указана буква, которой этот цвет обозначается во входных данных): красный (R), оранжевый (O), желтый (Y), зеленый (G), голубой (B), синий (N) и фиолетовый (P). Все карты уникальны, и в колоде присутствует комбинация каждой цифры с каждым цветом.

У каждого игрока есть карты в руке, карты, выложенные перед ним — его палитра, и общая стопка карт — холст. Изначально у первого игрока есть $$$n$$$ карт в руке и одна на палитре, у второго — $$$m$$$ карт в руке и одна на палитре, а холст пуст, однако считается, что на нем лежит красная карта.

На картах определен строгий порядок старшинства. Первая карта считается старше второй, если на ней написано большее число, или числа равны, но ее цвет идет раньше в последовательности цветов, обозначенной выше. Таким образом, самая старшая карта в игре — красная семерка, а самая младшая — фиолетовая единица. Гарантируется, что в начале игры карта на палитре первого игрока младше, чем карта на палитре второго игрока.

Цвет карты, лежащей верхней на холсте, задает условие, по которому определяется лидирующий игрок. Эти условия таковы: лидирует игрок, у которого

• красный - самая старшая карта;
• оранжевый - больше карт с одинаковым значением;
• желтый - больше карт одного цвета;
• зеленый - больше карт с четным значением;
• голубой - больше карт различных цветов;
• синий - больше карт с подряд идущими значениями (например, $$$4-5-6$$$);
• фиолетовый - больше карт со значением меньше 4.

Игроки делают ходы по очереди. В свой ход игрок должен совершить одно из трех действий:

• выложить одну карту из руки на свою палитру,
• выложить одну карту из руки на холст,
• выложить одну карту из руки на палитру, а затем выложить еще одну карту из руки на холст,

Обратим внимание, что по правилам игрок не может класть на холст карту, если у него на палитре нет ни одной карты, удовлетворяющей условию карты, положенной на холст. Например, если у игрока нет ни одной четной карты на палитре, он не может положить зеленую карту на холст.

Определите, кто выиграет при правильной игре.