Использование сортировки

Федок очень хочет купить себе комплексный обед в столовой, но сделать это не так просто. В столовой работает всего одна касса, и то очень медленно. На данный момент в очереди находится \(n\) \((2 \leq n \leq 100\,000)\) людей, а сам Федок находится на \(k-\)ой \((1 \leq k \leq n)\) позиции в ней. И вот, чтобы занять себя в этой очереди, Федок стал обдумывать коварный план как побыстрее оплатить комплексный обед и начать есть.

В чем состоит коварный план? Федок хочет крикнуть, что открылась новая касса. Тогда, по его мнению, многие уйдут из очереди в поисках этой кассы, а он приблизится к заветной еде. Но вот в чем проблема: не все люди так нетерпеливы как наш герой. Проще говоря, у каждого человека есть свой параметр \(P_i\) — терпеливость. Если человек стоит на позиции \(x\) и его терпеливость равна \(y\), то он уйдет искать новую кассу только в том случае, если \(y < x\)

Казалось бы, эта задача трудна, но и Федок не глуп. Он своим метким взором определил терпеливости всех людей, стоящих в очереди кроме него. Увы, так как людей очень много, в его голове все перепуталось, и некоторые числа поменялись местами. Таким образом наш герой получил некоторую перестановку множества терпеливости всех людей в очереди \(P_1, P_2, \ldots, P_{n-1}\)

Федок не знает точно, кто насколько терпелив и боится, что не сдвинется в очереди после реализации своей задумки. Поэтому он просит вас помочь ему узнать, какую минимальную и максимальную позицию от начала очереди он может занимать после того как крикнет: <<Свободная касса!>>

Формат входных данных
В первой строке входных данных находится число людей в очереди \(n\) (\(2 \leq n \leq 100\,000\))

Во второй строке находится число \(k\) (\(1 \leq k \leq n\)) — текущая позиция Федка в очереди

В следующей строке содержатся \(n-1\) число — перестановка множества терпеливостей людей в очереди \((0 \leq P_i \leq n)\)

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

Во второй строке выведите максимальное место, которое может стать у Федка после применения его плана

• Решения, работающие для \(n \leq 10\) будут набирать не менее 5 баллов

• Решения, работающие для \(n \leq 1000\) будут набирать не менее 10 баллов

Пояснение к первому тесту:

Алексей стоит на второй позиции. Перед ним один человек.

Если его терпеливость будет равна нулю, то он уйдет, и Федок станет первым

Если же его терпеливость равна трем, то он не уйдет, и Федок останется второй

На доске выписано две последовательности из \(n\) различных целых чисел: \(A = [a_1, a_2, \ldots, a_n]\) и \(B = [b_1, b_2, \ldots, b_n]\).

Составим из них \(n^2\) дробей вида \(a_i / b_j\), сократим каждую дробь и отсортируем их по неубыванию.

Задано число \(q\) и \(q\) целых чисел \(c_1, c_2, \ldots, c_q\). Для каждого \(j\) следует выдать \(c_j\)-ю в неубывающем порядке дробь из получившихся.

Формат входных данных
На первой строке ввода находятся числа \(n\) и \(q\) (\(1 \le n \le 10^5\), \(1 \le q \le 10^5\), \(q \le n^2\)).

Дополнительно выполняется неравенство \(n\cdot q \le 10^5\).

На второй строке ввода находятся \(n\) различных целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)).

На третьей строке ввода находятся \(n\) различных целых чисел \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le 10^6\)).

На четвертой строке ввода находятся \(q\) различных целых чисел \(c_1, c_2, \ldots, c_q\) (\(1 \le c_i \le n^2\)).

Формат выходных данных
Выведите \(q\) строк. На \(j\)-й строке выведите \(c_j\)-ю по неубыванию дробь среди получившихся. Дробь \(p/q\) следует выводить в формате <<p q>>, дробь должна быть несократимой.

Замечание
В примере дроби исходно равны: \[\left[ \frac{3}{2}, \frac{3}{3}, \frac{3}{4}, \frac{3}{5}, \frac{4}{2}, \frac{4}{3}, \frac{4}{4}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{2}{2}, \frac{2}{3}, \frac{2}{4}, \frac{2}{5} \right],\] после сокращения \[\left[ \frac{3}{2}, \frac{1}{1}, \frac{3}{4}, \frac{3}{5}, \frac{2}{1}, \frac{4}{3}, \frac{1}{1}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{1}, \frac{2}{3}, \frac{1}{2}, \frac{2}{5} \right],\] после сортировки \[\left[ \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}, \frac{1}{1}, \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \frac{2}{1} \right].\]

Сеня выбирает себе подарки на новый год. Он знает, что Дед Мороз купит ему ровно два подарка: один якобы от мамы, а другой якобы от папы.

В магазине, где Дед Мороз будет покупать подарки, продаётся \(n\) подарков, про каждый подарок известна его цена: цена \(i\)-го подарка равна \(a_i\) рублей. Сеня знает, что Дед Мороз может потратить на покупку его подарков не больше \(x\) рублей. Разумеется, он хочет получить как можно более дорогие подарки. Таким образом, он хочет выбрать два различных подарка с максимальной суммарной ценой, но при этом она не должна превышать \(x\).

Помогите Сене выбрать себе подарки.

Формат входных данных
Первая строка ввода содержит два целых числа: \(n\) и \(x\) (\(2 \le n \le 100\,000\), \(2 \le x \le 10^9\)). Вторая строка ввода содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)). Гарантируется, что существует два подарка с суммарной ценой не больше \(x\).

Формат выходных данных
Выведите одно целое число: максимальную суммарную цену двух различных подарков, не превышающую \(x\).

У Васи есть массив, состоящий из \(n\) чисел \(a_1, a_2, \ldots, a_n\). Для каждой позиции \(i\) и для каждого подотрезка массива \([l, r]\), который содержит позицию \(i\) (то есть, \(1 \le l \le i \le r \le n\)), Вася вычисляет значение \(c_{i, l, r}\) следующим образом. Вася выписывает на листочек числа из массива с позиции \(l\) до позицию \(r\), всего \(len=r-l+1\) чисел (среди которых обязательно есть \(a_i\)), и сортирует выписанные числа по возрастанию. После чего Вася находит, на какой позиции \(j\) в полученном отсортированном массиве стоит число \(a_i\). Если таких позиций несколько, то среди них он выбирает ту, которая максимизирует расстояние от середины массива — позиции \(mid = \lceil (len+1) / 2 \rceil\) (\(len / 2 + 1\) в случае четного \(len\) и \((len+1)/2\) в случае нечетного \(len\)). Полученное расстояние \(|j - mid|\) и есть искомая величина \(c_{i,l,r}\).

Например, если у Васи был массив \(a=\{5,1,3,2,1,7\}\), а \(i=2\), \(l=2\), \(r=5\), то Вася выпишет на листочек числа \(\{1,3,2,1\}\), отсортирует их и получит массив \(\{1,1,2,3\}\), длина которого равна 4. Середина этого массива находится на позиции \(4/2+1=3\), а искомое число \(a_i=1\) стоит в этом массиве на позициях 1 и 2. Среди этих двух позиций Вася выбирает ту, которая дальше от середины, то есть, позицию 1. Искомая разность между позициями равна 2, и это и есть значение \(c_{2,2,5}\).

Для каждой позиции \(i\) Вася вычисляет величину \(b_i\), которая равна максимуму среди значений \(c_{i,l,r}\) среди всех подотрезков, содержащих позицию \(i\).

Как вы видите, определение числа \(b_i\) достаточно сложное. Помогите Васе вычислить значения \(b_i\) для всех позиций массива.

Формат входных данных
В первой строке входных данных находится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — размер массива Васи.

Во второй строке находится \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) — элементы массива.

Формат выходных данных
В единственной строке выведите \(n\) чисел, \(i\)-е из них должно быть равно \(b_i\).

Разберем подробнее первый пример.

1. Для первой позиции Вася рассмотрит все подотрезки, содержащие эту позицию, в частности, подотрезок \([1,5]\), где \(l=1\) и \(r=5\). Для вычисления \(c_{i,l,r}=c_{1,1,5}\) Вася выпишет числа \(\{5, 4, 3, 2, 1\}\) и после сортировки получит \(\{1, 2, 3, 4, 5\}\). Середина этого массива находится на позиции 3, а искомое число \(a_1=5\) — на позиции 5. Таким образом, \(c_{1,1,5}=2\). Нетрудно заметить, что это число — максимальное среди всех подотрезков, содержащих позицию 1, а значит, \(b_1=2\).

2. \(b_2=c_{2,2,4}\).

3. \(b_3=c_{3,3,5}\).

4. \(b_4=c_{4,1,4}\). Действительно, если выписать числа на подотрезке \([1,4]\), то получится массив \(\{5,4,3,2\}\), который после сортировки превратится в \(\{2,3,4,5\}\). Середина этого массива находится на позиции \(3\), а искомый элемент \(a_4=2\) — на позиции 1. Таким образом, \(c_{4,1,4}=2\).

5. \(b_5=c_{5,1,5}\).

 

Найдите и выведите в возрастающем порядке все несократимые обыкновенные дроби \(f\) со знаменателем не превышающим \(n\), которые удовлетворяют неравенству \(1/p < f < 1/q\).

Формат входных данных
На ввод подается три числа: \(n\), \(p\) и \(q\) (\(1 \le n \le 100\), \(1 \le q < p \le 100\)).

Формат выходных данных
Выведите все искомые дроби, по одной на строке.

Петя открыл цветочный магазин. Магазин Пети занимается изготовлением и продажей букетов. Всего существует \(n\) видов цветов, занумерованных от 1 до \(n\). Каждый букет, чтобы быть гармоничным и красивым, должен состоять из цветов всех видов, по одной штуке каждого вида. В магазине уже есть \(a_i\) штук цветов вида \(i\). На цветочной базе можно купить цветок любого вида за 1 рубль.

Определите, сколько букетов сможет собрать Петя, если потратит не более \(x\) рублей на покупку цветов на базе. Ответьте на \(q\) запросов с различными \(x_i\).

Формат входных данных
В первой строке входных данных находятся два целых числа \(n\) и \(q\) (\(1 \le n, q \le 10^5\)) — количество различных типов цветов и количество запросов.

Во второй строке находятся \(n\) целых чисел \(a_1, a_2, \cdots, a_n\) (\(0 \le a_i \le 10^9\)) — количество цветов каждого вида, имеющихся в магазине.

В третьей строке находятся \(q\) целых чисел \(x_1, x_2, \cdots, x_q\) (\(0 \le x_i \le 10^9\)) — запросы Пети.

Формат выходных данных
Выходной файл должен содержать \(q\) чисел, где \(i\)-е число это максимальное количество букетов, которое можно собрать потратив не более \(x_i\) рублей.

Примечание
В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.

В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.

Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1.

В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.

Космический аппарат "Звезда" выполняет задачу по фиксации показаний уровня космической радиации. Каждое показание записывается в виде целого числа. В процессе первоначальной обработки данных, для устранения потенциально неточных результатов, убирают из списка K наибольших и K наименьших показаний.
Исходя из списка полученных показаний и количестве исключаемых показаний, определите самое высокое точное показание и целую часть среднего арифметического всех точных показаний.

Формат входных данных
В первой строке записаны два числа через пробел: N – общее количество показаний (натуральное число, не превышающее 10 000) и K – количество исключаемых минимальных и максимальных показаний. В следующих N строках находятся значений каждого показания (все числа натуральные, не превышающие 10000), каждое в отдельной строке.

Формат выходных данных
Запишите в ответе два числа: сначала наибольшего точного показания, а затем целую часть среднего арифметического всех точных показаний.

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

Входные данные
В первой строке вводят три числа, записанные через пробел: N – общее количество товаров (натуральное число, не превышающее 100 000), K – количество товаров (1 < K <  N), d - размер скидки в процентах (5 < d <  50). В следующих N строках находятся значения цены каждого из товаров (все числа натуральные, не превышающие 10 000), каждое в отдельной строке.  Гарантируется, что ответ не превышает 10⁹.

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

Примечание
Стоимость товара со скидкой выисляется по следующей формуле:
Цена со скидкой = Исходная цена - Исходная цена * (Процент скидки / 100).

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

Входные данные
В первой строке вводят два числа, записанные через пробел: N – общее количество товаров (натуральное число, не превышающее 100 000) и K – количество товаров (1 < K <  N). В следующих N строках находятся значения цены каждого из товаров (все числа натуральные, не превышающие 10 000), каждое в отдельной строке.  

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

У Максима есть n книг различных жанров. В i-й книге ai страниц. Сегодня он хочет прочитать  не менее xj страниц, при этом, чтобы не запутаться в историях, он хочет прочитать как можно меньше книг. 
Помогите Максиму  определить минимальное количество книг, которые он должен прочитать, чтобы общее число прочитанных страниц было не менее xj. Если это невозможно, выведите -1. Максим не может читать одну и ту же книгу дважды. 

Формат входных данных

Первая строка содержит натуральное число n (1 ≤ 𝑛 ≤ 10⁵) - количество книг, которые есть у Максима. Вторая строка  содержит n целых чисел a1, a2, ..., an (1≤ ai ≤10⁴) - количество страниц в i-й книге. Третья строка содержит натуральное число xj (1 ≤ xj ≤ 2⋅10⁹) - количество страниц, которое хочет прочитать Максим.

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

Напишите программу, которая переставляет строки матрицы так, чтобы при их просмотре сверху вниз максимальные значения в каждой строке образовали невозрастающую последовательность. В случае равенства максимальных значений в двух строках, строки должны следовать в том же порядке, что и в исходной матрице.
 
Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. 
 
Формат выходных данных
Программа должна вывести получившуюся матрицу.
 

Напишите программу, которая переставляет строки матрицы так, чтобы при их просмотре сверху вниз суммы всех значений в каждой строке образовали невозрастающую последовательность. В случае равенства суммы всех значений в двух строках, строки должны следовать в том же порядке, что и в исходной матрице.
 
Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. 
 
Формат выходных данных
Программа должна вывести получившуюся матрицу.
 

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

Формат входных данных
В первой строке записано натуральное число N - количество отмеченных точек (2 <= N <= 103). Во второй строке записано N целых чисел - координаты точек (каждое число по модулю не больше 109).

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

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

На складах фабрики находятся \(n\) колец, \(i\)-е кольцо имеет внутренний радиус \(a_i\), внешний радиус \(b_i\) и высоту \(h_i\). Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия:

• Внешние радиусы колец образовывали невозрастающую последовательность, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j \leq b_i\).

• Кольца не должны проваливаться друг в друга, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j > a_i\).

• Суммарная высота всех использованных колец должна быть максимальна.

Формат входных данных
В первой строке входных данных записано целое число \(n\) (\(1 \leq n \leqslant 100\,000\)) — количество колец на складах фабрики.

В \(i\)-й из последующих \(n\) строк записаны три числа \(a_i\), \(b_i\) и \(h_i\) (\(1 \leq a_i, b_i, h_i \leq 10^9\), \(b_i > a_i\)) — внутренний радиус, внешний радиус и высота \(i\)-го кольца соответственно.

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

В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке \(3\), \(2\), \(1\).

Во втором примере можно либо поставить кольцо \(3\) на кольцо \(4\) и получить башню высоты \(3\), либо поставить кольцо \(1\) на кольцо \(2\) и получить башню высоты \(4\).

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.

Решение, корректно работающие при \(1 \leq n \leq 9\), наберут не менее \(10\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 15\), наберут не менее \(20\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 1000\), наберут не менее \(60\) баллов.

Специально для \(n\) сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно \(n\) парковочных мест, каждому сотруднику должно достаться свое место.

Для экономии мест парковка будет разбита на несколько <<рядов>>. Места в каждом ряду нумеруются от \(1\) (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.

Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО  — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу \(t^\mathrm{in}_i\), и время, в которое он уезжает на следующий день \(t^\mathrm{out}_i\). Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать

• появления доступного парковочного места, когда он приезжает;

• возможности выехать, когда он заканчивает работу.

Более формально, если сотрудникам \(i\) и \(j\) назначены места \(p_i\) и \(p_j\) в одном ряду, и \(p_i < p_j\), должно выполняться \(t^\mathrm{in}_i \le t^\mathrm{in}_j\) и \(t^\mathrm{out}_i \ge t^\mathrm{out}_j\).

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

Формат входных данных

В первой строке ввода дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют описания наборов входных данных.

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

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(n\) строках перечислены времена въезда и выезда для каждого сотрудника, в \(i\)-й строке через пробел \(t^\mathrm{in}_i\) и \(t^\mathrm{out}_i\) (\(1 \le t^\mathrm{in}_i, t^\mathrm{out}_i \le 10^9\)).

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

В первой строке выведите число \(k\) — минимальное необходимое количество рядов.

В \(i\)-й из следующих \(n\) строк выведите через пробел сначала номер ряда, а затем номер места в этом ряду, которое надо отдать \(i\)-му сотруднику. Ряды и места нумеруются с единицы.

Если существует несколько различных ответов, минимизирующих \(k\), выведите любой из них.

Наши люди до метро на такси не ездят!

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин — ровно столько, сколько у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

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

Формат входных данных

Сначала во входном файле записано натуральное число N (1 ≤ N ≤ 1000) — количество сотрудников компании (совпадающее с количеством вызванных машин такси). Далее записано N чисел, задающих расстояния в километрах от работы до домов сотрудников компании (первое число — для первого сотрудника, второе — для второго и т.д.). Все расстояния — положительные целые числа, не превышающие 1000. Далее записано еще N чисел — тарифы за проезд одного километра в такси (первое число — в первой машине такси, второе — во второй и т.д.). Тарифы выражаются положительными целыми числами, не превышающими 10000.

Формат входных данных

В выходной файл выведите N чисел. Первое число — номер такси, в которое должен сесть первый сотрудник, второе число — номер такси, в которое должен сесть второй и т.д., чтобы суммарные затраты на такси были минимальны. Если вариантов рассадки сотрудников, при которых затраты минимальны, несколько, выведите любой из них.

 

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

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

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

Сегодня вечером по телевизору на разных каналах будут показывать n матчей по кёрлингу, причём i-й матч начинается в момент времени l_i и заканчивается в момент времени r_i. 

Василиса хочет посмотреть как можно больше матчей от начала до конца. При этом если какой-то матч заканчивается в момент времени r_i, то она может после него посмотреть любой матч j, который начинается не раньше момента времени r_i, то есть l_j >  r_i (Василиса может моментально переключить каналы в момент окончания матча и начать смотреть новый матч). Также она хочет сделать перерыв длины хотя бы t между какими-то двумя играми, чтобы поужинать, то есть должны найтись два последовательных матча i и j, которые просмотрит Василиса, удовлетворяющие условию l_j - r_i => t. Перерыв не может быть до или после всех просмотренных игр.

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

Формат входных данных
Первая строка входных данных содержит число n  (2 ≤ n ≤ 100 000) -  количество показываемых матчей.
Вторая строка входных данных содержит число t (1 ≤ n ≤ 10⁹) -  минимальная длина перерыва, который должна сделать Василиса.
В следующих n строках содержится по два числа l_i  и r_i  ( 1 ≤ l_i < r_i ≤ 10⁹) -  начало и конец i-го матча.

Формат выходных данных
Программа должна вывести число m - максимально возможное количество матчей, которые просмотрит Василиса. Во второй строке выведите m чисел через пробел - номера матчей, которые должна посмотреть Василиса, в порядке просмотра.
Если Василиса не может составить расписание хотя бы из двух матчей так, чтобы между какими-то двумя матчами был перерыв хотя бы t, то выведите число -1.

Замечание
В первом примере ответом будет последовательность матчей 6, 3, 5. Василиса сначала посмотрит матч 6, 
который заканчивается в момент времени 4, потом переключится на матч 3, который продолжается с 4 до 6. 
Затем она сделает перерыв с 6 по 10, после чего просмотрит матч номер 5 с 10 до 12. Получилось расписание из 3 матчей с перерывом, продолжительность которого равна 4. Заметим, что в данном примере правильным ответом также будет последовательность матчей 6, 4, 5, в этом случае продолжительность перерыва между матчами 4 и 5 будет равна 3.

Во втором примере всего два матча, первый заканчивается в 5, а второй начинается в 9, то есть составить расписание, в котором был бы перерыв продолжительностью не менее t=5, нельзя.