Серёжа участвует в телевизионном шоу «Сражение предсказателей», в очередном выпуске которого задачей участников является угадывание цвета шаров, доставаемых ведущим из непрозрачной урны. Он уже выяснил с помощью спиритического ритуала, что в урне лежат шары n различных цветов, причём шаров i-го цвета в ней лежит в точности a_i штук. Ведущий планирует наугад доставать шары по одному, пока урна не станет пустой, а Серёжа должен перед каждым доставанием назвать цвет шара, который достанет ведущий. К сожалению, духи предков отказываются помогать ему, поэтому придётся полагаться на интуицию. Серёжа хотел бы угадать цвет как можно большего количества шаров в худшем случае и теперь задаётся вопросом, как много раз ему удастся угадать наверняка.

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

Король выяснил, что всего существует n драконов, для победы над i-ым из которых требуется армия из a_i солдат, причём в процессе сражения b_i из них будут убиты. Теперь он хотел бы определить, какое наименьшее количество солдат ему нужно собрать, чтобы убить всех драконов. Королю не принципиально, в каком порядке убивать этих драконов: главное, чтобы ни один из них не остался в живых.

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

Входными данными в каждой такой задаче является целое число x, из которого требуется извлечь квадратный корень, и простое число p, по модулю которого это требуется сделать. Правильным ответом на такую задачу является квадратный корень из x по модулю p, то есть такое целое число s, что s·s и x дают один и тот же остаток от деления на p. Иными словами, число должно нацело делиться на p. Нужно заметить, что иногда для заданного x подходящего квадратного корня s не существует.

Чтобы автоматизировать процесс составления задач на эту тему, Миша решил написать программу, которая для заданного простого числа p находит квадратные корни по модулю p из всех целых чисел x от 0 до включительно, либо сообщает, что соответствующего квадратного корня не существует.

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

Карта временно безопасного участка местности представляет собой клетчатое поле, состоящее из n горизонтальных рядов по m квадратов в каждом, причём база находится в c-м квадрате r-го ряда. Сара уже оценила, что для постройки стены в квадрате, находящемся в i-м ряду на j-й позиции, требуется a_i, j единиц времени. Сара считает, что если в некотором квадрате построена стена, то зорки не смогут пройти через него. Требуется построить стены так, чтобы зорки не смогли добраться до базы из-за пределов клетчатого поля, перемещаясь по клеткам, имеющим общую сторону, и не заходя при этом на клетки со стеной. На постройку всех стен должно быть затрачено как можно меньше единиц времени, учитывая, что стены строятся последовательно одна за другой, а между постройками стен в разных клетках время не тратится. Само собой, нельзя строить стену в клетке, в которой находится база Сары.

Сара задумалась, в каких именно клетках нужно построить стену, чтобы она удовлетворяла указанным требованиям. К счастью, в её отряде нашёлся программист, который взялся решить эту задачу.

В одном самарском вузе прошёл отбор на международные соревнования по фигурному программированию, но тренерский штаб, входящий в состав жюри, никак не может определиться, сколько лучших команд отобрать для участия в следующем этапе. В фигурном программировании тестирующая система не определяет точно количество баллов, набранных участником, а определяет лишь отрезок, в котором это количество баллов лежит. Жюри вправе поставить участнику любое количество баллов из этого отрезка. Всего в отборе участвовали n команд, i-я из которых набрала количество баллов, лежащее на отрезке от l_i до r_i включительно. Жюри хотело бы отправить в следующий этап как можно больше команд, но по правилам для этого они все должны набрать максимальное количество баллов среди всех участников. Какое же наибольшее количество команд можно отправить в следующий этап соревнования при таких условиях?

В одной далёкой-далёкой галактике великая галактическая империя развалилась после смерти императора, и постепенно набирает силы новая коррумпированная галактическая республика. Но злобные ситхи не дремлют: они создали своё сопротивление под названием «Последний орден» и планируют выбрать себе предводителя с помощью честного турнира.

Всего в турнире будут участвовать n оставшихся в живых ситхов, i-ый из которых характеризуется тремя положительными целыми числами: мастерством владения мечом a_i, мастерством владения Силой b_i и степенью психической уравновешенности c_i. Все характеристики всех ситхов попарно различны. Турнир состоит из серий поединков один на один, в каждом из которых принимает участие пара различных ситхов. В таком поединке выигрывает тот ситх, у которого по меньшей мере две из трёх характеристик превышают соответствующие характеристики его противника.

Проблема в том, что турниры ситхов никогда не были направлены на определение самого сильного ситха, способного победить остальных: они были нужны, чтобы выявить самого слабого ситха, который не может выиграть ни одного боя, и в достаточной степени поглумиться над этим неудачником. Похоже, что в этот раз такой ситх станет главой Последнего ордена, так что неплохо бы заранее оценить, кто из участников может им стать.

Зорки не любят представителей других рас. Зорки любят тяжёлые кривые топоры. Прямо сейчас каждый из них собирается выбрать себе подходящий топор и продемонстрировать окопавшимся неподалёку представителям других рас свою неготовность к мирной культурной ассимиляции. Всего имеется n зорков и m топоров, причём i-й зорк хочет взять топор массой не меньше a_i и кривизной не меньше b_i, а j-й топор имеет массу w_j и кривизну c_j. Зорки не любят задачи по программированию. Зорки любят тяжёлые кривые топоры. Так что решать, какому зорку какой топор нужно выбрать, придётся вам.

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

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

Юрий Мухоморов работает коррумпированным начальником полиции. Каждый день он должен выставлять полицейских на посты в городе так, чтобы местные криминальные группировки всё равно могли совершать преступления. Город представляет собой n площадей, соединённых m улицами, так что j-я улица соединяет a_j-ю и b_j-ю площади. Полицейский, размещённый на некоторой площади, может вести наблюдение как за этой площадью, так и за всеми площадями, соединёнными с этой площадью некоторой улицей. Юрий хочет так расставить полицейских, чтобы по крайней мере одна площадь оказалась не под наблюдением, что позволит организованным преступникам проворачивать на этой площади свои тёмные делишки. Само собой, Юрий не хочет навлекать на себя подозрений, поэтому планирует выставить полицейских на как можно большее количество городских площадей.

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

Как-то раз они посещали невероятно длинную улицу, на которой находятся n архитектурных сооружений, расположенных в ряд одно за другим. Каждый участник клуба сделал по одной фотографии, на которой видно некоторый отрезок улицы, включающий, кроме самих участников и прохожих, несколько последовательно расположенных архитектурных сооружений. Иными словами, если занумеровать все архитектурные сооружения в том порядке, в котором они стоят на этой улице, то на каждой фотографии будут видны несколько архитектурных сооружений, имеющих последовательные номера.

Как-то тренер команд этого вуза по римскому праву краем глаза увидел выставку фотографий с той улицы. Он не обратил внимания, сколько конкретно фотографий на ней было представлено, но заметил, что i-е архитектурное сооружение появлялось на a_i фотографиях. Теперь он хотел бы оценить, какое минимальное количество студентов посещает фотоклуб, учитывая, что ни один участник не мог представить на выставку больше одной фотографии.

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

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

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

В массовой онлайновой многопользовательской ролевой видеоигре «Путь изгнанника» развитие игрового персонажа осуществляется путём приобретения талантов за специальные очки талантов, получаемые в процессе игры. Некоторые таланты зависят от других. Талант можно приобрести, только если у персонажа есть хотя бы один из талантов, от которых он зависит. Также на приобретение таланта тратится одно очко таланта. Один талант имеется у персонажа с самого начала игры.

Школьник Василий решил записать видеоинструкцию по правильному развитию персонажа, следуя которой, можно легко побеждать других игроков и неигровых персонажей. Он уже занумеровал все талантов целыми числами от 0 до n включительно, так чтобы имеющийся с самого начала игры талант имел номер 0. Василий считает, что для правильного развития персонажа необходимо во что бы то ни стало приобрести два различных таланта, имеющие в его нумерации номера a и b, потому что эти таланты недостаточно хорошо сбалансированы и намного сильнее всех остальных. Приобрести эти таланты нужно как можно раньше, поэтому Василий задумался, какое минимальное количество очков таланта необходимо потратить с начала игры, чтобы это сделать.

Специальный агент Адам взламывает калькулятор члена секретной масонской организации иллюминатов, чтобы получить доступ к информации о её лидерах. Он уже выяснил, что всего в организацию входит n человек, каждый из которых имеет свой порядковый номер. Кроме того, у каждого из них есть уровень, представляющий собой целое число от 1 до n включительно. Уровни всех членов этой организации попарно отличаются. Любой иллюминат может командовать другими иллюминатами более низкого уровня, но вынужден подчиняться иллюминатам более высокого уровня. Адам полагает, что утечка информации об иллюминате наивысшего n-го уровня может его дискредитировать, поэтому ему интересен иллюминат с уровнем n - 1, подчиняющийся только иллюминату с наивысшим уровнем.

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

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

Сначала в отдельной строке записано единственное целое число n (2 ≤ n ≤ 1000) — количество иллюминатов.

После этого ваша программа может делать запросы на сравнение двух иллюминатов. Для этого в отдельной строке выведите символ «?» и два целых числа через пробел после него — порядковые номера иллюминатов, которых вы хотите сравнить. В ответ на это в отдельной строке будет записан единственный символ «<», если первый иллюминат имеет уровень меньше, чем второй, символ «>», если первый иллюминат имеет уровень больше, чем второй, либо «=», если указанные иллюминаты имеют одинаковый уровень. Вы можете сделать не более чем таких запросов.

Когда вы узнаете ответ, выведите символ «!» и единственное целое число через пробел — номер иллюмината, имеющего уровень n - 1.