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

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

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

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

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

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

Однако за десять минут до отъезда в тёплые страны ей пришла в голову мысль, что Арсению надо оставить точную инструкцию, какую одежду надевать в какой из дней её отсутствия. Арсений живёт в очень необычной семье, в которой вся одежда пронумерована: например, n носков Арсения имеют различными целые номера от 1 до n . Поэтому всё, что потребовалось его маме, это указать для каждого дня два числа l _i и r _i — номера носков, которые надо надеть в i -й день на левую и правую ногу соответственно (разумеется, l _i не совпадает с r _i ). Каждый носок покрашен в один из k цветов.

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

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

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

Археологи, найдя секретный ход в подземелье одной из пирамид в Цикляндии, столкнулись с необычным замком на двери в сокровищницу. На замке было написано n слов, каждое из которых состоит из нескольких иероглифов. Рядом с замком на стене был обнаружен необычный круглый рычаг, поворот которого меняет иероглифы, из которых состоят слова на замке, по некоторому принципу. Также рядом с иероглифом была найдена надпись на древнецикляндском, которая гласит, что замок откроется, только если слова, написанные на замке, станут идти в лексикографическом порядке (определение дано в пояснении).

Несмотря на то, что археологи отлично знали весь древнецикляндский алфавит, который состоял из c иероглифов, они никак не могли определить закономерность, по которой меняются буквы. Наконец кто-то догадался позвать вас, главного мыслителя современной Цикляндии. Вам хватило одного взгляда, чтобы понять, что поворот рычага на одну позицию по часовой стрелке заменяет каждый иероглиф на следующий за ним по алфавиту, то есть x -й ( 1 ≤ x ≤ c - 1 ) иероглиф превращается в ( x + 1) -й, а c -й превращается в первый.

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

С древних времён ужасный крылатый Сфинкс подстерегает путников у Большого Камня по дороге в священный город Истины, задаёт им хитроумные загадки и съедает тех, кто не сумел дать правильный ответ. Турист Пётр тоже решил посетить город Истины и встретил чудовище.

Сфинкс задал ему такую загадку: «На Большом Камне написано число n . Найди наименьшее целое положительное число k , такое что сумма цифр числа k в десятичной системе счисления делится на n и сумма цифр числа k + 1 в десятичной системе счисления делится на n ».

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

Где-то в Москве в очередной раз построили новый дом: красивый, современный и многоэтажный. Он состоит из ровно \(n\) жилых этажей, пронумерованных от \(1\) до \(n\) снизу вверх, и подземной парковки, являющейся нулевым этажом.

Дом уже был почти готов к сдаче в эксплуатацию, но вот незадача — в самый ответственный момент по всему зданию прорвало водопроводные трубы, в результате чего многие этажи залило водой. К моменту, когда все трубы были заделаны, на \(i\)-м этаже находилось \(w_i\) литров воды.

Также из-за того, что при строительстве дома все средства ушли на отделку фасада, а на перекрытия между этажами был пущен самый дешёвый материал, оказалось, что между этажами ощутимо протекают потолки. В частности, пропускная способность пола \(i\)-го этажа составляет \(v_i\) литров воды в час.

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

Владельцы стройки интересуются, через сколько часов вся вода вытечет на парковку, и они смогут начать продажи квартир?