После пожара 1812 года на одной из главных улиц Москвы уцелел лишь один дом. Вернувшиеся после победы жители решили вновь поселиться на этой улице. При этом каждый решил построить себе дом такой же высоты, каким он был у него до пожара.
Дома будут строиться вплотную друг другу, а крыши соседних домов будут соединяться лестницами (длина лестницы равна разнице высот домов), чтобы трубочист мог путешествовать по крышам и чистить трубы.
Когда план постройки домов был уже почти утвержден, свое веское слово сказал Главный Трубочист. Он попросил построить дома так, чтобы суммарная длина лестниц была минимальной. Помогите ему составить такой план постройки домов.
Во входном файле записано сначала число N (1 ≤ N ≤ 10000), затем N чисел — высоты домов до пожара (это натуральные числа от 1 до 109), и затем K — номер уцелевшего дома.
В выходной файл выведите высоты домов в таком порядке, чтобы выполнялось требование Главного Трубочиста. Обратите внимание, что K-ый дом (уцелевший) перестраивать не нужно (и следовательно его высота должна остаться прежней).
5 1 3 4 2 6 2
6 3 4 2 1
Рассмотрим две строки \(α\) и \(β\). Их конкатенацией называется строка, получающаяся в результате приписывания к строке \(α\) строки \(β\). Эта строка обозначается \(αβ\). Например, конкатенацией строк `ab' и `ac' будет строка `abac'. Очевидно, что это определение естественным образом распространяется на конкатенацию произвольного количества строк. Так, конкатенацией нуля строк будет пустая строка, а конкатенацией одной строки будет она сама.
Рассмотрим некоторое множество \(W\), состоящее из строк. Назовём его замыканием множество \(W\)*, состоящее из тех и только тех строк, которые можно получить в результате конкатенации нуля и более строк из множества \(W\). Таким образом, множество \(W\)* содержит пустую строку, и если строка α принадлежит множеству \(W\)*, а строка \(β\) принадлежит множеству \(W\), то строка \(αβ\) принадлежит множеству \(W\)*. Более того, все элементы множества \(W\)* можно представить в таком виде, то есть \(W\)* является пересечением всех множеств с указанными выше свойствами. Например, если \(W\)={a,ab}, то \(W\)* состоит из всех строк, в которых перед каждой буквой `b' идёт хотя бы одна буква `a'.
Задано некоторое множество строк \(W\). Требуется найти множество \(X\), такое, что \(W\)*=\(X\)* и множество \(X\) имеет минимальное возможное число элементов. В случае, если таких множеств несколько, подходит любое из них. Например, если \(W\)={a,aabb,ab,ac,b,bac}, то единственным множеством, удовлетворяющим условиям задачи будет множество {a,ac,b}.
Входной файл состоит из набора строк, каждая из которых является элементом множества \(W\). Каждая строка из множества \(W\) встречается во входном файле хотя бы один раз. Суммарная длина всех строк во входном файле не превосходит \(10^4\). Количество строк во входном файле не превосходит \(10^4\). После каждой строки из множества \(W\) во входном файле идёт перевод строки (пара символов с ASCII кодами 13 и 10). Строки состоят из символов с ASCII кодами от 33 до 126 включительно.
Выведите в выходной файл элементы одного из множеств \(X\), удовлетворяющих условиям задачи. Каждая строка множества \(X\) должна быть выведена ровно один раз. Строки должны идти в лексикографическом порядке (лексикографический порядок используется в словарях, в этом порядке строка `ab' меньше строки `aba' и строка `ab' меньше строки `ac'). После каждой строки множества \(X\) должен идти один перевод строки.
a aabb ab ac b bac
a ac b
Идёт 2163 год. Мишу, который работает в отделении таможни при космодроме города Нью-Питер, вызвал в кабинет шеф.
Как оказалось, недавно Министерство Налогов и Сборов выделило отделению определённую сумму денег на установку новых аппаратов для автоматического досмотра грузов. Естественно, средства были выделены с таким расчётом, чтобы грузы теперь находились на таможне ровно столько времени, сколько требуется непосредственно на их досмотр.
В руках шефа каким-то образом оказались сведения о надвигающейся ревизии – список из \(N\) грузов, которые будут контролироваться Министерством. Для каждого груза известны время его прибытия, отсчитываемое с некоторого момента, хранимого в большом секрете, и время, требуемое аппарату для обработки этого груза. Шеф дал Мише задание по этим данным определить, какое минимальное количество аппаратов необходимо заказать на заводе, чтобы все грузы Министерства начинали досматриваться сразу после прибытия. Необходимо учесть, что конструкция тех аппаратов, которые было решено установить, не позволяет обрабатывать два груза одновременно на одном аппарате. Напишите программу, которая поможет Мише справиться с его задачей.
На первой строке входного файла задано число \(N\) (0 ≤ \(N\) ≤ 50 000). На следующих \(N\) строках находится по 2 целых положительных числа \(T_i\) и \(L_i\) – время прибытия соответствующего груза и время, требуемое для его обработки (1 ≤ \(T_i\) ≤ \(10^6\), 1 ≤ \(L_i\) ≤ \(10^6\)).
В выходной файл выведите одно число – наименьшее количество аппаратов, которое нужно установить, чтобы не вызвать подозрений у Министерства.
3 3 2 4 2 5 2
2
5 13 4 15 1 11 5 12 3 10 3
3
«Ну не гномы, а наказание какое-то!», – подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь – другой уже проснулся! И так всю ночь.
У Белоснежки \(n\) гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать \(i\)-го гнома нужно \(a_i\) минут, и после этого он будет спать ровно \(b_i\) минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.
Например, пусть есть всего два гнома, \(a_1\) = 1, \(b_1\) = 10, \(a_2\) = 10, \(b_2\) = 20. Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.
Первая строка входного файла содержит число \(n\) (1 ≤ \(n\) ≤ \(10^5\)), вторая строка содержит числа \(a_1\),\(a_2\),… \(a_n\), третья – числа \(b_1\),\(b_2\),… \(b_n\) (1 ≤ \(a_i\), \(b_i\) ≤ \(10^9\)).
Выведите в выходной файл \(n\) чисел – порядок, в котором нужно укладывать гномов спать. Если Белоснежке отдохнуть не удастся, выведите число -1.
2 1 10 10 20
2 1
2 10 10 10 10
-1