"Два указателя"

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

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 2 · 10⁵ ) — количество мест в ряду.
Вторая строка содержит целое число k (1 ≤ k ≤ n) — количество приходящих людей.
Третья строка содержит строку s длины n, состоящую из символов «0» и «1» и задающую первоначальную рассадку. Занятые места обозначаются единицами, пустые — нулями. Гарантируется, что в строке s содержится не менее k нулей.
Формат выходных данных
Программа должна вывести k чисел — номера выбранных мест в порядке прихода новых людей.

Замечание
В первом примере первоначально заняты места 1, 2 и 6 (рисунок А).
Если первый пришедший будет двигаться с левой стороны ряда, он пройдёт мимо 1 и 2 места, прежде чем доберётся до свободного места с номером 3. Если же он будет двигаться с правой стороны ряда, то ему понадобится пройти мимо одного места с номером 6, после чего он сможет занять место 5. Именно это место он и выберет (рисунок Б).
Второй пришедший может занять либо место с номером 3, двигаясь с левой стороны и проходя мимо двух занятых мест 1 и 2, либо место с номером 4, двигаясь с правой стороны и проходя мимо двух занятых мест 6 и 5. Поскольку в обоих случаях ему нужно пройти мимо двух занятых мест, он будет двигаться с левой стороны и займёт место с номером 3.
Во втором примере в ряду 6 мест, второе и пятое места изначально уже заняты, заходят ещё 3 человека. Первый заходящий человек будет выбирать между первым и шестым местами, заходя с левого или правого края соответственно. В обоих случаях ему придётся пройти мимо нуля занятых мест, поэтому он решит зайти слева и сесть на 1 место. Второй человек будет выбирать между третьим и шестым местами. В первом случае ему придётся идти мимо двух занятых мест, во втором — мимо нуля, поэтому он выберет зайти справа — 6 место. Третий человек будет выбирать между третьим и четвертым местами. В обоих случаях ему придётся пройти мимо двух занятых мест, поэтому он выберет зайти слева — 3 место.

Рассмотрим отрезок целых неотрицательных чисел от \(l\) до \(r\). Запишем их подряд в десятичной системе счисления, получив строку \(a\). Например, если \(l=3\), \(r=10\), то \(a=345678910\).

Найдите такой отрезок подряд идущих неотрицательных чисел \([l,r]\) (\(0 \le l \le r \le 10^{18}\)), что записанная для него строка \(a\) имеет длину ровно \(S\), а количество чисел на отрезке \([l,r]\) максимально.

Формат входных данных
Первая строка содержит одно целое число \(S\) (\(1 \le S \le 10^{18}\)).

Формат выходных данных
В первой строке выведите длину отрезка \([l,r]\). Если решения не существует, выведите одно целое число \(-1\).

Если решение существует, во второй строке выведите искомые границы отрезка \(l\) и \(r\).

Если существуют несколько решений, выведите любое из них.

Алексей, возможно, самый умный и при этом самый ленивый человек в мире. Сегодня он участвует в олимпиаде.

На олимпиаде участникам даны \(n\) задач, за правильное решение \(i\)-й задачи, участник получит \(a_i\) баллов, за неправильное решение баллов не дают. Дипломы призера дадут тем участникам, которые наберут хотя бы половину от суммарного числа баллов. Например, если на олимпиаде дано три задачи, стоимости которых в баллах равны \(1\), \(3\) и \(4\), соответственно, для получения диплома призера достаточно набрать четыре балла.

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

Алексей настолько ленив, что даже задачи, которые он будет решать, выбирает лениво. Он хочет выбрать некоторую задачу с номером \(k\), а затем решать задачи с номерами \(k, k+1, k+2 \ldots\) до тех пор, пока ему не будет хватать баллов на диплом призера. Максимум, на что готов Алексей, это пропустить одну задачу и не решать ее, чтобы решить в итоге еще меньше задач.

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

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

Во второй строке заданы \(n\) чисел \(a_1, a_2, \dots a_n\) — стоимости каждой задачи в баллах (\(1 \le a_i \le 10^9\)).

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

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

Во втором тесте достаточно решить только вторую задачу, набрав три балла.

Будем называть цепочкой слов длины n последовательность слов w₁, w₂, …, w_n, такую, что для всех i от 1 до n – 1 слово w_i является собственным префиксом слова w_i+1.

Слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u. Например, «program» является собственным префиксом слова «programmer».

Задано множество слов S = {s₁, s₂, …, s_m} и последовательность чисел x[1], x[2], …, x[k]. Требуется найти такие числа l и r (l ≤ r), что s_x[l], s_x[l + 1], …, s_x[r – 1], s_x[r] является цепочкой слов, и количество слов в цепочке (число r – l + 1) максимально.

Входные данные
Первая строка входного файла содержит целое число m (1 ≤ m ≤ 250 000). Каждая из следующих m строк содержит по одному слову из множества S.

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

Следующая строка содержит число k (1 ≤ k ≤ 250 000). Последняя строка входного файла содержит k чисел — последовательность чисел x[1], x[2], …, x[k] (для всех i выполнено 1 ≤ x[i] ≤ m).

Выходные данные
Выведите в первой строке выходного файла два числа: l и r. Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.

На доске выписано две последовательности из \(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\).

Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — <<PriceFixed>>. У этого магазина есть несколько особенностей:

• В магазине есть бесконечный запас каждого товара.

• Все товары в нем стоят одинаково — ровно 2 рубля.

• Для каждого из \(i\) товаров предусмотрена скидка для опытных покупателей: если вы уже приобрели \(b_i\) товаров (любого типа, не обязательно типа \(i\)), то на все последующие покупки \(i\)-го товара будет действовать скидка \(50\%\) (то есть, \(i\)-й товар можно будет покупать за 1 рубль!).

Лене нужно купить \(n\) товаров: \(i\)-го товара нужно купить \(a_i\) штук. Помогите Лене понять, какую минимальную сумму денег ей нужно будет потратить, если она будет выбирать порядок покупки товаров оптимальным образом.

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

В следующих \(n\) строках вводятся описания товаров. Каждое описание состоит из двух чисел \(a_i\) и \(b_i\), (\(1 \leq a_i \leq 10^{14}\), \(1 \leq b_i \leq 10^{14}\)) — требуемое число товаров типа \(i\) и сколько товаров нужно купить, чтобы получить скидку на товар \(i\).

Сумма всех \(a_i\) в тесте не превосходит \(10^{14}\).

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

В первом примере из условия Лена может купить товары в таком порядке:

1. единицу товара 3 за 2 рубля,

2. единицу товара 1 за 2 рубля

3. единицу товара 1 за 2 рубля,

4. единицу товара 2 за 1 рубль (она может купить его со скидкой, так как уже куплено 3 товара),

5. единицу товара 1 за 1 рубль (она может купить его со скидкой, так как уже куплено 4 товара).

Суммарно она потратит 8 рублей. Можно показать, что меньше потратить невозможно.

Во втором примере из условия Лена может купить товары в таком порядке:

1. единицу товара 1 за 2 рубля,

2. две единицы товара 2 по 2 рубля за каждую,

3. единицу товара 5 за 2 рубля,

4. единицу товара 3 за 1 рубль,

5. две единицы товара 4 по 1 рублю за каждую,

6. единицу товара 1 за 1 рубль.

Суммарно при таком порядке приобретения товаров Лена потратит 12 рублей.

Физрук формирует дистанцию для забега школьников на уроке. Согласно требованиям, длина дистанции должна быть от \(L\) до \(R\) метров.

Дистанция пройдет вдоль дорожки в парке около школы. Вдоль дорожки растет \(n\) деревьев, первое дерево находится на расстоянии \(d_1\) метров от начала дорожки, \(i\)-е дерево находится на расстоянии \(d_i\) метров от предыдущего дерева для \(i > 1\). Для удобства физрук хочет, чтобы дистанция начиналась либо в начале дорожки, либо около какого-либо дерева, и заканчивалась также около какого-либо дерева.

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

Помогите физруку выбрать точки начала и конца дистанции.

Формат входных данных
Первая строка ввода содержат два целых числа \(L\) и \(R\) (\(1 \le L \le R \le 3 \cdot 10^{14}\)). Обратите внимание, что для считывания \(L\) и \(R\) необходимо хотя бы 64-битный тип данных (<<long long>> в C++).

Вторая строка ввода содержит целое число \(n\) (\(1 \le n \le 300\,000\)).

Третья строка ввода содержит \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1 \le d_i \le 10^9\)).

Формат выходных данных
Выведите два целых числа: \(s\) и \(t\) — расстояние от начала дорожки до начала и конца дистанции, соответственно. Должны выполняться условия: \(0 \le s < t\), \(L \le t - s \le R\), \(s = 0\) или \(s\) совпадает с позицией некоторого дерева, \(t\) совпадает с позицией некоторого дерева.

Если выбрать организовать дистанцию не получится, выведите \(s = -1\), \(t = -1\).

 

Дана строка s и символ с, который встречается в s. Для каждого символа из строки s, определите расстояние до ближайшего символа с.
Расстояние между двумя индексами i и j равно abs(i - j), где abs - функция вычисления модуля числа.


Формат входных данных
В первой строке записана непустая строка s, состоящая из маленьких английских букв (длина строки не превышает 104). Во второй строке записан символ c. Гарантируется, что в строке s содержится как минимум один символ c.

Формат выходных данных
Выведите в одной строке через пробел n чисел ai. Число ai - расстояние от символа с индексом i до ближайшего символа c (n равно длине строки s, 0 <= i < n). Числа выводить в порядке следоваения букв в исходной строке.  

Последовательность \([b_1, b_2, \ldots, b_k]\) называется битонической, если выполнены неравенства \(b_1 < b_2 < \ldots < b_i > \ldots > b_k\) для некоторого \(1 \le i \le k\).

Например, последовательности \([1]\), \([1, 2, 3, 2]\), \([1, 4, 10]\), \([3, 2]\) являются битоническими, а последовательности \([1, 1]\), \([2, 1, 3]\) — нет.

Задана последовательность \([a_1, a_2, \ldots, a_n]\). Требуется количество пар \((l, r)\) таких, что \(1 \le l \le r \le n\) и последовательность \([a_l, a_{l+1}, \ldots, a_r]\) является битонической.

Формат входных данных
Первая строка ввода содержит число \(n\) (\(1 \leq n \leq 300\,000\)).

Вторая строка ввода содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)).

Формат выходных данных
Выведите одно число — количество пар \((l, r)\), таких, что \(1 \le l \le r \le n\) и последовательность \([a_l, a_{l+1}, \ldots, a_r]\) является битонической.

В первом примере подходят следующие пары:

• \((1, 1)\), последовательность \([1]\)

• \((2, 2)\), последовательность \([1]\)

• \((2, 3)\), последовательность \([1, 2]\)

• \((2, 4)\), последовательность \([1, 2, 3]\)

• \((2, 5)\), последовательность \([1, 2, 3, 1]\)

• \((3, 3)\), последовательность \([2]\)

• \((3, 4)\), последовательность \([2, 3]\)

• \((3, 5)\), последовательность \([2, 3, 1]\)

• \((4, 4)\), последовательность \([3]\)

• \((4, 5)\), последовательность \([3, 1]\)

• \((5, 5)\), последовательность \([1]\)

У Максимуса есть коллекция волшебных амулетов, каждый из которых обладает своей магической силой. Список имеющихся у него амулетов отсортирован в порядке неубывания магической силы. Вернувшись из очередного путешествия, Максимус составил список новых амулетов, предварительно отсортировав их по невозрастанию магической силы. Теперь у него два отдельных списка и он хочет объединить их в один упорядоченный по неубыанию список. 
Он хочет сделать это как можно быстрее. Помогите ему отсортировать два этих списка. Максимус просит вас написать программу, которая будет работать за O(len(A)+len(B)). 
 

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

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

Примеры

№	Входные данные	Выходные данные
1	1 5 7 2 4 4 5	1 2 4 4 5 5 7

Лука часто ездит на сборы по программированию. Сборы длятся n дней. Лука фиксирует количество решенных задач в каждый день сборов. Лука считает сборы «эффективными», если только один непрерывный не нулевой промежуток дней (от l до r), когда выполнялись следующие условия по числу решенных задач:

• 1 <= l <= r <= n;
• al = al+1 = al+2 =…=ar;
• l = 1 или al-1 > al;
• r = n или ar < ar+1;

Примеры 

Пусть массив A хранит информацию о решении задач за каждый день сборов, тогда:

1) массив A = [5, 3, 3, 2, 3, 3, 4] описывает «эффективные», по мнению Луки, сборы (промежуток в 1 день l = r = 4 удовлетворяет условию);

2) массив А = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] также описывает «эффективные» сборы (промежут l = 1, r = 3 удовлетворяет условию);

3) массив А = [1, 2, 3, 4, 3, 2, 1] описывает не «эффективные» сборы (есть два промежутка удовлетворяющих условию l = r = 1 и l = r = 7).

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

Входные данные
Первая строка содержит одно целое число n (1 <= n <= 2·10⁵) — длину массива. Вторая строка n целых чисел ai (1 <= ai <= 10⁹) — количество решенных Лукой задач в i-й день .

Выходные данные
Выведите YES, если сборы Луки оказались эффективными, и NO в противном случае.
 

Примеры

№	Входные данные	Выходные данные
1	7 5 3 3 2 3 3 4	YES
2	11 2 2 2 3 4 4 5 6 7 7 8	YES
3	7 1 2 3 4 3 2 1	NO