реализация

Дано число. В этом числе необходимо изменить одну цифру таким образом, чтобы новое число делилось на 3 и было бы максимально возможным. В исходном числе нужно
обязательно изменить одну цифру, даже если исходное число уже делилось на 3. Программа получает на вход одно длинное натуральное число. Длина числа может
достигать 100 цифр.
Программа должна вывести другое натуральное число, удовлетворяющее условиям:
1. Новое число должно отличаться от данного ровно одной цифрой.
2. Новое число должно делиться на 3.
3. Новое число должно быть максимально возможным из всех таких чисел.

Примеры

№	Входные данные	Выходные данные
1	123	723

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

Формат входного файла
В первой строке задается N — количество звезд на небе (3  ≤ N ≤ 300000). В каждой из следующих N строк заданы целые X, Y (|X, Y| ≤  10⁹) — координаты соответствующей звезды.

Формат выходного файла
Выведите ответ к задаче.
 

Примеры

№	Входные данные	Выходные данные
1	3 0 0 1 0 0 1	1
2	4 0 0 1 0 0 1 1 1	4

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

Каждый день на планете Кирнес состоит из h часов. Каждый час состоит из m минут, причём m обязательно чётное. Известно, что на данный момент n товарных поездов отправляются с вокзала ежедневно по разу в день: i-й поезд отправляется в h_i часов и m_i минут.

Поскольку между Кирнесом и Сириусом активный пассажиропоток, то было решено пустить ровно по 2 электрички каждый час. Более того, по всем транспортным нормам необходимо, чтобы промежутки времени между отправлением электричек были равны \( {m \over 2}\)минутам. То есть для любой электрички предыдущая должна была отправиться ровно за \({m \over 2}\) минут до неё, а следующая должна отправиться ровно через \({m \over 2}\) минут после. Кроме этого, электричку надо подать на платформу за k минут до отправки. Пока электричка стоит на платформе, с неё не могут отправляться товарные поезда. При этом разрешается подавать электричку на платформу в ту же самую минуту, когда с неё отправляется предыдущий товарный поезд. А также поезда отправляются настолько быстро, что разрешено отправить электричку и следующий за ней товарный поезд в одну и ту же минуту.

Поскольку электрички отправляются каждый день с интервалом в \({m \over 2}\) минут, то первая электричка отправится с вокзала в 0 часов и t минут, причем t < \({m \over 2}\) . Обратите внимание, что если t < k, то платформа вокзала будет занята и последние k − t минут предыдущего дня.

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

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

Формат входных данных
Первая строка содержит четыре целых числа n, h, m, k (1 ≤ n ≤ 100 000, 1 ≤ h ≤ 10⁹, 2 ≤ m ≤ 10⁹, 1 ≤ k ≤ \({m \over 2}\)) — число товарных поездов, количество часов и минут на планете Кирнес, а также время, которое электричка стоит у платформы. Гарантируется, что число минут m четное.
В следующих n строках вводится по два целых числа hi и mi (0 ≤ h_i < h, 0 ≤ m_i < m) — время отправления i-го поезда, часы и минуты соответственно. Гарантируется, что все товарные поезда отправляются в разное время.

Формат выходных данных
Выведите два числа: минимальное количество отмененных товарных поездов и t — время запуска первой за день электрички в минутах.
Во второй строке через пробел выведите номера отменяемых товарных поездов.

Примеры

№	Входные данные	Выходные данные
1	2 24 60 15 16 0 17 15	0 0
2	2 24 60 16 16 0 17 15	1 0 2

Замечание

В первом примере первую электричку надо отправить в 0:00. Тогда поезд в 16:00 отправится сразу после электрички, а электричку в 17:30 надо будет подать на платформу сразу после отправления товарного поезда в 17:15.
Во втором примере подать электричку на платформу надо за 16 минут до отправления. Сделать это без отмены какого-то товарного поезда не получится: если отправлять электричку в t ∈ [1, 15], то в 16:00 электричка уже должна быть на платформе, а с нее в это время отправляется первый товарный поезд. Если t ∈ {0, [16, 29]}, то второй товарный поезд в 17:15 не сможет уехать с платформы, потому что на ней уже будет стоять следующая электричка.
Если отменить второй поезд, то можно выбрать t = 0, тогда поезда будут отправляться в 0 и 30 минут каждый час, а столкновения с первым товарным поездом не будет. Также можно отменить только первый поезд и выбрать, например, t = 13.
 

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

Как известно, любому таланту надо дать возможность реализоваться, поэтому мама Миши отправила сына на инновационную олимпиаду по ирригации (ИОИ). На этой олимпиаде школьники со всех концов Берляндии соревнуются в умении доставить воду для поливки растений самыми причудливыми способами. Зная список изобретений Миши, несложно догадаться, что проведение подобной олимпиады весьма затратно, поэтому спустя n первых проведений олимпиады было решено ввести правило, по которому будет определяться место проведения соревнования в следующий год. Город для проведения олимпиады выбирается следующим образом: всего в Берляндии есть m городов, пронумерованных от 1 до m, готовых принять соревнование. Каждый год олимпиада проводится в городе, в котором она проводилась наименьшее число раз. Если таких городов несколько, то олимпиада проводится в городе с наименьшим номером среди городов с минимальным числом проведений олимпиады.

Мишина мама очень волнуется за сына, поэтому её интересует, в каком городе будет проходить олимпиада в определённые годы. Единственная информация, которой располагает мама Миши, — места проведения олимпиады в первые n лет. Помогите маме Миши, и она попросит Мишу не залить вашу квартиру.

Входные данные
В первой строке заданы три целых числа n, m и q (1 ≤ n, m ≤ 500000 , 1 ≤ q ≤ 20) — количество проведений олимпиады до введения правила, количество городов в Берляндии, готовых провести олимпиаду, и число лет, про которые маму Миши интересует место проведения олимпиады, соответственно.

В следующей строке содержится n целых чисел a_i (1 ≤ a_i ≤ m) — номера городов, в которых проводилась олимпиада в год i. Обратите внимание, что до принятия правила место проведения олимпиады могло выбираться произвольным образом.

В следующих q строках заданы целые числа k_i (n+1 ≤ k_i ≤ 10¹⁸) — номера годов, для которых маму Миши интересует место проведения олимпиады.

Выходные данные
Выведите q целых чисел. В строке с номером i выведите одно целое число — место проведения олимпиады в год k_i.

Примеры

№	Входные данные	Выходные данные
1	6 4 10 3 1 1 1 2 2 7 8 9 10 11 12 13 14 15 16	4 3 4 2 3 4 1 2 3 4
2	4 5 4 4 4 5 1 15 9 13 6	5 3 3 3

Федот — дизайнер, ему поручена ответственная работа по художественной укладке плитки черного и белого цвета. Его последнее задание — уложить черные и белые плитки в квадрате n × n.

Федот любит свою работу и всегда тщательно готовится к каждому проекту. Федот считает, что два квадрата похожи, если один из них можно получить из другого несколько раз заменив цвета в какой-то строке или столбце на противоположные. Федот заметил, что клиенты никогда не смотрят на всю работу целиком, обычно поле их зрения ограничивается квадратом k × k. Для оценки эскизов он ввел специальную величину — сложность. Она равна числу пар не похожих друг на друга квадратов k × k, которые встречаются в картине.

Методом проб и ошибок Федот установил, что клиентам нравятся картины определенной сложности. Слишком большая сложность похожа на хаос, а слишком малая навевает скуку, считает Федот.

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

Входные данные
Первая строка входного файла содержит два целых числа n и k (1 ≤ k ≤ n ≤ 500). Следуюшие n строк содержат описание эскиза. Каждая из них имеет длину n и состоит из символов b и w, которые соответствуют белому и черному цветам плиток.

Выходные данные
В первой строке выходного файла выведите одно целое число q — сложность картины.

Примеры

№	Входные данные	Выходные данные
1	2 1 bw wb	0
2	3 2 bwb wbb bbw	3

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


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


Поскольку вы не хотите смерти Индианы и хотите получить свою долю сокровищ, вам придется помочь ему!

Входные данные
В первой строке входного файла содержится одно целое число n (1 ≤ n ≤ 100). В следующих n строках описан сам треугольник. Строка входного файла, имеющая номер i + 1, содержит 2i - 1 цифру — содержание i-й строки ключа-треугольника.

Последняя строка содержит слово counterclockwise, если треугольник необходимо повернуть против часовой стрелки, и clockwise в противном случае.

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

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 4 5 6 7 8 9 counterclockwise	9  4 8 7  1 3 2 6 5
2	3 1 2 3 4 5 6 7 8 9 clockwise	5  7 6 2  9 8 4 3 1

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

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

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

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

Входные данные
Для уменьшения размера ввода высоты и стоимости доминошек задаются при помощи блоков.

В первой строке заданы два целых числа n и m (1 ≤ n≤ 250 000, 1 ≤ m ≤ 10⁷ ) — количество блоков и суммарное количество доминошек, которые надо уронить Семёну, соответственно.

Затем следует описание n блоков. Описание каждого блока состоит из трёх строк.

В первой строке описания блока с номером i содержится целое число k_i (1 ≤ k_i ≤ 250000, \(\sum_{i=1}^n {k_i ? 250 000}\) ) — количество доминошек в блоке.

Во второй строке описания блока с номером i содержатся ki целых чисел a_i,j (1 ≤ a_i,j ≤ m) — высоты доминошек в блоке.

В третьей строке описания блока с номером i содержатся ki целых чисел c_i,j (1 ≤ c_i,j ≤ 100000) — стоимости доминошек в блоке.

Далее следует описание последовательности доминошек, которые надо уронить Семёну, в порядке слева направо.

В первой строке описания последовательности задано целое число q (n ≤ q ≤ 250000) — количество блоков в последовательности доминошек, которые надо уронить.

В следующих q строках содержатся пары целых чисел id_i mul_i (1 ≤ id_i ≤ n, 1 ≤ mul_i ≤ 100000), обозначающие, что очередные k_idi в порядке слева направо доминошек — это доминошки блока id_i, чьи стоимости были умножены на число mul_i.

Гарантируется, что \(\sum_{i=1} ^q k_{id_i} = m\) , а также, что каждый блок встречается хотя бы один раз в последовательности доминошек, которые требуется уронить, то есть для всех i от 1 до n найдется j такое, что id_j=i.

Выходные данные
Выведите одно целое число — минимальную суммарную стоимость доминошек, которые надо толкнуть, чтобы все доминошки упали.

Примечание
В первом примере перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 7 влево, она упадёт и заденет доминошку с номером 6. Доминошка 6, падая, заденет доминошку с номером 5, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером 1 вправо, она, падая, заденет доминошки с номерами 2 и 3, а доминошка 3, падая, заденет доминошку 4, таким образом все доминошки упадут.

Во втором примере перед Семёном стоит одна доминошка стоимостью 10000000000.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 7 3 1 2 2 1 2 1 1 3 2 3 2 2 1 3 1 1	5	Перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 7 влево, она упадёт и заденет доминошку с номером 6. Доминошка 6, падая, заденет доминошку с номером 5, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером 1 вправо, она, падая, заденет доминошки с номерами 2 и 3, а доминошка 3, падая, заденет доминошку 4, таким образом все доминошки упадут.
2	1 1 1 1 100000 1 1 100000	10000000000	Перед Семёном стоит одна доминошка стоимостью 10000000000

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

А вам нужно по кадру из этой серии определить, упадет ли наковальня на Тома, если Джерри перережет веревку.

Входные данные
Вам дана ASCII-арт картинка, то есть картинка, нарисованная символами. На ней есть наковальня, привязанная веревкой к потолку, и кот Том. В первой строке даны числа N, M (4≤N≤100, 1≤M≤100 ). Следующие N строк состоят из M символов каждая, и представляют собой саму картинку. Картинка устроена следующим образом:

• Первые K₁ строк в одной и той же позиции X₁ стоит символ «|», в остальных — пробел. Это веревка.
• Следующие K₂ строк в одних и тех же позициях с X₂ по X₃ стоит символ «#», в остальных — пробел. Это наковальня.
• 2×X₁=X₂+X₃, то есть наковальня подвешена за середину.
• Следующие K3 строк содержат только пробелы. Это пустота между наковальней и котом.
• Следующие N − K₁ − K₂ − K₃ строк содержат произвольные символы. Любой символ, кроме пробела — часть кота. Существует хотя бы один непробельный символ.

Числа K₁, K₂, K₃ и N − K₁ − K₂ − K₃  ненулевые.
Выходные данные
Выведите «YES», если при падении наковальня заденет Тома, в противном случае выведите «NO».
 

Примеры

№	Входные данные	Выходные данные
1	13 29 | | | ############# ############# ############# /\_/\ >^.^<.---. _'-`-' )\ (6--\ |--\ (`.`-. --' --' ``-'	YES
2	16 30 | ####### ####### ####### ####### , \)\_ / '. .---._ =P ^ ` '. `--. / \ .-'( \ | (.-' )-..__> , ; (_.--`` (__.-/ / .-.__.-'.' '-...-'	NO

Начались каникулы, и дядя Фёдор, изрядно соскучившись по своим школьным друзьям, пригласил их всех в гости к себе в Простоквашино. После некоторых раздумий n из них согласились приехать. Взяв с собой все необходимые для отдыха на природе вещи, они приехали на вокзал покупать билеты. Выяснилось, что в поездах, идущих до Простоквашино, есть только купейные вагоны. В каждом вагоне всего k₄ четырехместных купе и k₂ — новых двухместных купе. Кроме друзей дяди Фёдора, никто не хочет ехать в Простоквашино, поэтому все места в поезде пока свободны. Друзья решили, что они хотят поехать все в одном вагоне: вместе ведь веселее. Чтобы поездка запомнилась надолго, один из друзей дяди Фёдора, Женя, решил одолжить у папы фотоаппарат «Зенит» и сфотографировать всех участников поездки, сидящих каждый на своем месте в поезде, по одному снимку на купе. Но пленка дорогая, а проявка — это долго и нудно, поэтому Женя попросил купить билеты так, чтобы вся дружная компания занимала как можно меньше купе. Помогите Жене посчитать, сколько в лучшем случае ему понадобится кадров, чтобы сфотографировать всю компанию, то есть посчитайте, сколько минимально купе они должны занять.

Входные данные
В первой и единственной строке вводятся числа n, k₄ и k₂ — количество друзей дяди Фёдора, едущих в Простоквашино, количество четырехместных купе в вагоне и количество двухместных купе в вагоне соответственно (1≤n≤10¹⁸, 0≤k₄≤10¹⁸, 0≤k₂≤10¹⁸).

Выходные данные
Выведите одно целое число — минимальное количество купе, в которых можно разместить всех друзей дяди Фёдора. Если же разместить всех друзей в одном вагоне не получится, выведите −1.

Примеры

№	Входные данные	Выходные данные
1	10 5 3	3

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

По списку всех слов в словаре помогите Вениамину выбрать пароль. Он должен быть такой, чтобы Денису пришлось перебрать как можно больше вариантов, прежде чем он найдет нужный.

Входные данные
В первой строчке вводится N — количество слов в cловаре (1 ≤ N ≤ 103). В следующих N строчках вводятся слова — строки длиной не более 255 символов, состоящие только из маленьких латинских букв. Слова отсортированы в алфавитном порядке.

Выходные данные
Выведите искомый пароль. Если подходящих паролей несколько, выведите тот, который идёт в словаре позже всех остальных.

Примеры

№	Входные данные	Выходные данные
1	7 arhimed computer contest informatics programming python team	python

В Московском метрополитене вновь появляются автоматы для продажи билетов. Вас просят написать программу, которая будет рассчитывать, какую сдачу и какими купюрами и монетами требуется выдать пассажиру.

Входные данные
Вводится сначала стоимость билета, который хочет приобрести пассажир, затем общее количество купюр и монет, которые он опустил в автомат, а затем достоинства каждой из этих купюр и монет. Входные данные записаны в одной строке и разделены пробелами. Известно, что сумма всех купюр больше, чем стоимость билета. Во всех тестовых примерах стоимость билета – натуральное число, не превосходящее 1 000 рублей, количество купюр и монет не более 50, достоинство каждой не превосходит 500 рублей. Общая сумма денег, опущенных в автомат покупателем, превосходит стоимость билета.

Выходные данные
Программа должна вычислить, какими купюрами и монетами можно выдать сдачу, и вывести достоинство каждой из этих купюр или монет в произвольном порядке. Автомат может выдавать сдачу купюрами в 10, 50, 100 и 500 рублей, а также монетами в 1, 2 и 5 рублей. Если решений несколько, требуется выдать одно любое из них. Если решений нет, требуется выдать текст:

Sorry! Our monetary system is not perfect!
Please, choose another way to pay!
Thank you!

Примеры

№	Входные данные	Выходные данные
1	100 1 500	50 100 100 100 50

В космические шахматы играют на бесконечной доске, поэтому клетки нумеруют парой чисел (см. пример и рисунок к нему). Фигуры ходят по обычным правилам. Составьте маршрут шахматного коня из клетки (0; 0) в заданную клетку (x; y).
Напомним, что конь за один ход перемещается на одну клетку по одной оси и на две по другой, то есть, например, из клетки (0; 0) он за один ход может попасть в клетки (1; 2), (2; 1), (-1; 2), (2; -1), (1; -2), (-2; 1), (-1; -2) и (-2; -1).

В качестве ответа Вам нужно вывести любой (не обязательно кратчайший) маршрут с началом в (0; 0) и концом в (x; y), длина которого не больше 10⁵ ходов.

Формат входных данных
Программа получает на вход два целых числа x и y, записанных в отдельных строках, - координаты конечной клетки маршрута коня. Клетка (x; y) не совпадает с началом координат. |x| <= 10⁵, |y| <= 10⁵.

Формат выходных данных
Программа должна вывести последовательность ходов, один ход в отдельной строке. В i-й строке должно быть выведено два числа x_i и y_i через пробел - координаты клетки, в которой окажется конь после i-го хода. Количество ходов не должно превышать 10⁵. Последний ход должен вести в заданную клетку
 

Ввод	Вывод
-2 2	-2 1 0 2 -1 0 -2 2

Рисунок к примеру

Компания ADM представила новый квантовый процессор. Благодаря нему очень быстро можно применять функцию «tripleswap» к некоторому массиву a.

tripleswap(i, j, k, x, y, z) — переставляет элемент, который стоит на позиции i на позицию x, элемент с позиции j на позицию y и элемент с позиции k на позицию z. При этом i, j, k, x, y и z — корректные индексы массива, множество {i,j,k} совпадает с множеством {x,y,z}, а также выполняется условие, что i, j, k различны между собой и x, y, z различны между собой.

Таким, образом, пусть есть массив, содержащий первую перестановку из пяти элементов [1,2,3,4,5]. Если применить к нему tripleswap(1, 5, 4, 5, 1, 4) получится массив [5,2,3,4,1]. При этом, выполнить tripleswap(1, 5, 4, 5, 2, 4) или tripleswap(1, 5, 1, 5, 1, 1) нельзя, так как такие наборы аргументов считаются некорректными.

Вас пригласили протестировать возможности нового процессора. Для первого теста вам дана перестановка из n чисел, нужно отсортировать ее по возрастанию при помощи функции tripleswap, вызвав данную функцию не более, чем n/2 раз (деление целочисленное, 5/2=2).

Входные данные

В первой строке дано одно натуральное число n — размер перестановки (3≤n≤100).

Во второй строке заданы n чисел a_i — элементы перестановки (1≤a_i≤n). Гарантируется, что все a_i попарно различны.

Выходные данные

В первой строке выведите одно число m — число вызов функции tripleswap, которые сортируют данную перестановку требуемым способом.

В каждой из следующих m строк выведите по шесть чисел — аргументы для каждого вызова функции.

Если есть несколько решений, разрешается вывести любое.
 

Ввод	Вывод
5 1 2 3 4 5	0
5 5 4 3 2 1	2 2 4 5 4 5 2 1 2 5 5 1 2

Примечание
В первом тесте последовательность уже отсортирована, поэтому потребуется ноль вызовов данной функции. Во втором тесте изменение элементов массива будет выглядеть следующим образом: [5,4,3,2,1]⇒[5,1,3,4,2]⇒[1,2,3,4,5].

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

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

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

Вам дан журнал событий турникета. Требуется вывести список тех студентов, кому будет сделан выговор

Входные данные
В первой строке задано два числа n и dt — число записей в журнале событий турникета и ограничение времени, выбранное начальником охраны, соответственно (1≤n≤1000, 3≤dt≤1440).
В следующих nn строках даны записи в журнале событий в хронологическом порядке. Запись в журнале состоит из трех частей, разделенных пробелом:

•  Время события в формате hh:mm
•  Фамилия студента, состоящая из не более чем 20 букв латинского алфавита, первая из которых заглавная.
•  Тип события: in, если произошел вход и out, если произошел выход.

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

Выходные данные
В первой строке выведите число нарушителей. После чего выведите фамилии нарушителей в лексикографическом порядке.
 

Ввод	Вывод
6 10 01:23 Petrov in 01:24 Ivanov out 01:25 Petrov out 01:27 Ivanov in 01:32 Petrov in 01:33 Ivanov out	1 Petrov
6 10 01:23 Petrov in 01:24 Ivanov out 01:25 Petrov out 01:27 Ivanov in 01:33 Petrov in 01:34 Ivanov out	0

 

Недавно Вася решил, что все существующие алгоритмы сортировки слишком сложны, и обязательно должен существовать более простой и эффективный алгоритм.
Для начала Вася решил рассмотреть следующий алгоритм: по данному массиву целых чисел a размером n, он создает пустой массив b, а дальше на каждой из n последующих итераций будет брать k-й элемент массива a (или последний, если такого нет), удалять его из a, а затем записывать в конец b. Таким образом, после n итераций Вася планирует в качестве массива b получить отсортированный по возрастанию массив a.
Однако, протестировав на нескольких примерах, Вася понял, что этот алгоритм работает не всегда. Так, например, если исходный массив a=[1,2,3,4] и k=2, то после 4 итераций массив b вовсе не будет отсортированным:
После первой итерации в b добавляется число 2, а массив a равен [1,3,4];
После второй итерации в конец b добавляется число 3, а массив a равен [1,4];
После третьей итерации в конец b добавляется число 4, а массив a равен [1];
На последней, четвертой итерации, в конец b добавляется число 1, а массив a становится пустым;
Таким образом, итоговый массив b будет выглядеть так: [2,3,4,1]. Нетрудно заметить, что он не является отсортированным по возрастанию. Однако, Вася решил так легко не сдаваться и по данному числу k научиться находить такой массив a, содержащий перестановку последовательности натуральных чисел от 1 до n, который будет сортироваться по возрастанию методом, описанным выше. Помогите ему - по данным числам n и k найдите хотя бы один подходящий массив a.

Формат входных данных
В единственной строке содержится два числа n и k - размер массива и номер элемента, берущегося на каждой итерации, соответственно (1≤k≤n≤1000).

Формат выходных данных
В единственной строке через пробел выведите n чисел - элементы массива, который отсортируется по возрастанию способом Васи. Если существует несколько ответов, выведите любой.
 

Ввод	Вывод
5 1	1 2 3 4 5
5 5	5 4 3 2 1

Обычно, прежде чем в 11 лет поступить в Хогвартс, дети-волшебники воспитываются дома, потому что нельзя быть уверенным, что они смогут скрыть свои волшебные способности от одноклассников-маглов. Например, детей Уизли учила миссис Уизли в Норе.
В Хогвартсе 4 факультета. Четыре факультета в Хогвартсе соответствуют четырем элементам: Гриффиндор – огонь, Когтевран – воздух, Пуффендуй — земля, Слизерин – вода.
У каждого факультета имеется свой флаг. 
Напишите программу, которая по данному числу n от 1 до 9 выводит на экран n флагов. Изображение одного флага имеет размер 4×4 символов, между двумя соседними флагами также имеется пустой (из пробелов) столбец.
Разрешается вывести пустой столбец после последнего флага. Внутри каждого флага должен быть записан его номер — число от 1 до n.

Входные данные
Вводится натуральное число.

Выходные данные 
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	3	+___ +___ +___ |1 / |2 / |3 / |__\ |__\ |__\ | | |

Есть озеро, рядом с которым хотят построить дом. Архитектурный проект (форма дома) уже утверждён, можно только выбрать расположение дома так, чтобы он оказался рядом с озером. Желательно выбрать расположение дома рядом с озером так, чтобы у как можно большего числа жителей дома окна выходили на озеро, то есть чтобы длина общей границы дома и озера была максимальной.

План дома и озера задан в виде изображения на клетчатой бумаге, в котором отмечены клетки, принадлежащие дому и озеру. Первая строка входных данных содержит число N – количество строк в плане дома и озера. Вторая строка входных данных содержит число M – количество столбцов в плане дома и озера.

Следующие N строк содержат по M символов – план дома. Символ «.» в этих строках обозначает пустую клетку, символ «H» обозначает» обозначает клетку дома. План дома является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая дому. Следующие N строк по M символов в каждой содержат план озера, в этих строках символ «.» обозначает пустую клетку, символ «W» обозначает клетку, занятую озером. План» обозначает клетку, занятую озером. План озера является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая озеру.

Программа должна вывести одно число – максимальное значение длины общей границы дома и озера, измеряемую в сторонах клетки. При расположении дома рядом с озером его можно передвигать, но нельзя делать повороты и отражения. Вокруг озера есть неограниченное свободное пространство, дом может располагаться с любой стороны от озера.
Числа N и M являются целыми, положительными, не превосходят 15.
 

Ввод	Вывод	Примечание
5 6 ...... .HHHH. .HHHH. .HHHH. ...... ..WWW. ..WWW. ..WWW. ..WWW. ..WWW.	3	. . . . W W W H H H H W W W H H H H W W W H H H H W W W       . . . . W W W
5 7 ...HHH. .H...H. .H.HHH. .H.H... .HHH... ....... ..WWWWW WWW...W W.W...W ..W....	11

Тем временем Ёж решил покатать шары из снега. В итоге у него получилось N шариков с диаметрами a₁, a₂, … a_n, все они различны. Из них он хочет собрать как можно больше НОРМАЛЬНЫХ снеговиков. Нормальный снеговик состоит из трёх шаров, диаметр которых снизу вверх строго уменьшается. Сколько максимум снеговиком он сможет собрать?

Ввод	Вывод
6 2 3 4 5 6 7	2

(с) Манаев И., Кашукова М., 2018 г.