Хозяйка кота Бенедикта считает, что он мало двигается, и поэтому придумывает для кота разные подвижные игры. Одна из игр — погоня за светящейся точкой от лазерной указки.
Хозяйка включает лазерную указку и перемещает светящуюся точку по полу в течение $$$n$$$ единиц времени.
Будем считать, что на пол нанесена координатная сетка. За одну единицу времени светящаяся точка перемещается от одной точки с целыми координатами к другой точке с целыми координатами. Каждую единицу времени кот оценивает, будет ли он прыгать к светящейся точке или нет.
Кот выполняет оценку следующим образом. Пусть он находится в точке с координатами $$$(x_C, y_C)$$$, а светящаяся точка — в точке с координатами $$$(x_L, y_L)$$$.
По ходу игры кот подсчитывает, сколько он совершил прыжков и сколько раз поймал светящуюся точку лапой. Каждый раз, когда количество прыжков или количество пойманных светящихся точек меняется, кот вычисляет разность между этими величинами. Его интересует максимальное (по абсолютной величине) значение, которого достигала эта разность по ходу игры.
Изначально кот сидит в точке с координатами $$$(0, 0)$$$. Ваша задача — определить максимальную по абсолютной величине разность между количеством прыжков и количеством светящихся точек, пойманных лапой, которая наблюдалась по ходу игры. Также необходимо указать, в какой точке координатной сетки кот окажется по завершении игры.
В первой строке содержится целое число $$$s$$$ $$$(1 \le s \le 10^9)$$$ — нижняя граница оценки для прыжка кота.
Во второй строке содержится целое число $$$b$$$ $$$(s \le b \le 10^9)$$$ — верхняя граница оценки для прыжка кота.
В третьей строке содержится целое число $$$p$$$ $$$(0 \le p \lt s)$$$ — верхняя граница оценки для поимки светящейся точки лапой.
В четвёртой строке содержится целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — количество единиц времени, в течение которого хозяйка кота перемещала лазерную указку.
В каждой из следующих $$$n$$$ строк содержится по два целых числа $$$x_j$$$ и $$$y_j$$$ $$$(-10^4 \le x_j, \, y_j \le 10^4, \, j = 1, 2, \ldots, n)$$$.
Выведите максимально возможную по абсолютной величине разность между количеством прыжков, которое совершит кот, и количеством светящихся точек, пойманных лапой, а также координаты точки, в которой кот окажется (сначала координату $$$x$$$, потом $$$y$$$).
Разделяйте выводимые числа пробелами или переводами строк.
Обратите внимание, что выводить следует именно разность, а не её абсолютное значение.
Во всех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | $$$p = 0, \, s = 1$$$ | нет | полная |
| 2 | 2 (до 10) | $$$p = 0, \, s \ge 2$$$ | 1 | полная |
| 3 | 2 (до 20) | $$$p = s-1 \ge 1$$$ | 1 | полная |
| 4 | 3 (до 60) | любые возможные значения | 1, 2, 3 | полная |
1 50 0 9 2 3 1 7 2 8 -4 -3 -5 -1 0 -2 5 3 5 3 3 -5
4 5 3
30 100 20 10 2 3 1 7 2 8 -4 -3 -5 -1 -4 -3 -7 3 -5 -1 -1 4 2 0
-3 -1 4
Поясним приведённые примеры.
Будем обозначать количество прыжков $$$jumps$$$ и количество пойманных светящихся точек $$$points$$$. В начале игры обе эти величины равны $$$0$$$.
В первом примере кот действует следующим образом.
Как можно видеть, максимально возможная разность между количеством прыжков и количеством пойманных точек будет равна $$$4$$$. В конце игры кот окажется в точке $$$(5, 3)$$$.
Во втором примере кот действует следующим образом.
Как можно видеть, в течение игры максимальная по абсолютной величине разность между количеством прыжков и количеством пойманных светящихся точек составляла $$$-3$$$ ($$$3$$$ по абсолютной величине).
Кот Бенедикт уже несколько дней недоумевает: вместо фильмов про животных хозяева целыми днями смотрят странные (с точки зрения кота) игры людей. Эти люди бегают по большому полю за одним-единственным мячом, пытаясь отобрать его друг у друга.
Бенедикт уже не раз слышал, что есть $$$4$$$ команды, которые для определённости будем называть $$$A$$$, $$$B$$$, $$$C$$$ и $$$D$$$. Каждая из этих команд должна сыграть с каждой по одному разу. Таким образом, всего должно быть сыграно $$$6$$$ матчей. Часть матчей уже состоялась, а часть — скоро состоится.
Результатом матча может быть ничья, за которую каждой из команд начисляют по одному очку, или выигрыш одной из команд и, соответственно, проигрыш другой. Выигравшей команде начисляют три очка, проигравшей — ноль очков.
Очки суммируются, и команда, набравшая максимальное количество очков, занимает первое место. Если максимальное количество очков набирает несколько команд, то все такие команды считаются занявшими первое место.
Бенедикт знает, что хозяева переживают за команду $$$A$$$ и очень хотят, чтобы она заняла первое место. Ваша задача — зная результаты уже состоявшихся матчей, определить, может ли команда $$$A$$$ занять первое место, и если да, то с какими результатами должны завершиться ещё не состоявшиеся матчи.
В первой строке содержится целое число $$$n$$$ $$$(4 \le n \le 5)$$$ —количество уже состоявшихся матчей.
Далее следует $$$n$$$ строк, в каждой из которых содержится по три символа $$$t_1$$$, $$$r$$$, $$$t_2$$$ $$$(t_1, t_2 \in \{A, \, B, \, C, \, D \}, \, t_1 \not= t_2, \, r \in \{ W, \, R \} )$$$, $$$t_1$$$ и $$$t_2$$$ – наименования команд, а $$$r$$$ — результат их игры: $$$W$$$ означает, что команда $$$t_1$$$ победила команду $$$t_2$$$, а $$$R$$$ — что команды $$$t_1$$$ и $$$t_2$$$ сыграли вничью (посмотрите пример ниже для лучшего понимания формата).
Гарантируется, что все описанные матчи попарно различны.
В первой строке выведите $$$YES$$$, если возможны такие результаты оставшихся матчей, при которых команда $$$A$$$ может занять первое место, и $$$NO$$$ — если ни при каких результатах оставшихся матчей команда $$$A$$$ не займёт первое место.
Если в первой строке выведено $$$YES$$$, далее следуют $$$6-n$$$ строк, в которых записаны результаты оставшихся матчей, при которых команда $$$A$$$ займёт первое место, в таком же формате, как во входных данных.
Если существует несколько вариантов правильного ответа, выведите любой из них.
Во всех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | $$$n = 5$$$, в оставшемся матче | нет | полная |
| команда $$$A$$$ участвует | ||||
| 2 | 2 (до 20) | $$$n = 5$$$, в оставшемся матче | 1 | полная |
| команда $$$A$$$ не участвует | ||||
| 3 | 2 (до 10) | $$$n = 4$$$, в обоих оставшихся матчах | 1 | полная |
| команда $$$A$$$ участвует | ||||
| 4 | 2 (до 30) | $$$n = 4$$$, в одном из оставшихся матчей | 1, 2, 3 | полная |
| команда $$$A$$$ участвует, в другом — нет | ||||
| 5 | 2 (до 30) | $$$n = 4$$$, в обоих оставшихся матчах | 1, 2, 3, 4 | полная |
| команда $$$A$$$ не участвует |
5 A W B C W A B W C C R D D R B
YES A R D
4 A R B C W B D W A C R D
YES A W C B W D
4 A R B B W C D W A C W D
NO
Поясним приведённые примеры.
В первом примере единственная ещё не состоявшаяся игра — это игра между командами $$$A$$$ и $$$D$$$.
Подсчитаем количество очков, которые набрали команды.
Команда $$$A$$$ выиграла у $$$B$$$ ($$$3$$$ очка) и проиграла $$$C$$$ ($$$0$$$ очков), и на настоящий момент имеет $$$3$$$ очка.
Команда $$$B$$$ проиграла команде $$$A$$$ ($$$0$$$ очков), выиграла у команды $$$C$$$ ($$$3$$$ очка), а также сыграла вничью с командой $$$D$$$ ($$$1$$$ очко). Итого у команды $$$B$$$ $$$4$$$ очка.
Команда $$$C$$$ выиграла у команды $$$A$$$ ($$$3$$$ очка), проиграла команде $$$B$$$ ($$$0$$$ очков), сыграла вничью с командой $$$D$$$ ($$$1$$$ очко), так что суммарно набрала $$$4$$$ очка.
Наконец, команда $$$D$$$ дважды сыграла вничью: с командой $$$B$$$ и с командой $$$C$$$, поэтому имеет $$$2$$$ очка.
Как понятно, команде $$$A$$$ достаточно не проиграть команде $$$D$$$. В случае ничьей она наберёт $$$4$$$ очка и займёт одно из первых мест (что допустимо по условиям задачи), в случае победы у неё будет $$$6$$$ очков, что сделает её абсолютным победителем.
Таким образом, корректными будут следующие ответы:
$$$$$$ A \quad R \quad D$$$$$$ $$$$$$ D \quad R \quad A$$$$$$ $$$$$$ A \quad W \quad D$$$$$$
В качестве ответа в этом примере выведен второй из перечисленых.
Во втором примере сыграно четыре игры. Как несложно определить, что между собой ещё не играли пара $$$A$$$ и $$$C$$$ и пара $$$B$$$ и $$$D$$$.
После этих четырёх игр команды $$$A$$$ и $$$B$$$ имеют по одному очку, а команды $$$C$$$ и $$$D$$$ по четыре очка. За одну игру команда не может набрать более трёх очков, поэтому если хотя бы одна из команд $$$C$$$ или $$$D$$$ не проиграет, она займёт первое место. Проигрыш этих команд обеспечивается выигрышем команд $$$A$$$ и $$$B$$$: в этом случае именно они поделят первое место в группе.
В третьем примере также сыграно четыре игры, и между собой ещё не играли пара $$$A$$$ и $$$C$$$ и пара $$$B$$$ и $$$D$$$ (как и во втором примере).
Однако ситуация с набранными очками здесь другая. Команда $$$A$$$ набрала лишь одно очко, в то время как команда $$$B$$$ имеет четыре очка, а команды $$$C$$$ и $$$D$$$ — по три очка. Даже если команда $$$A$$$ выиграет свою игру и наберёт четыре очка, она не сможет занять первое место. В игре между командами $$$B$$$ и $$$C$$$ любой исход плох для $$$A$$$. Действительно, при победе $$$B$$$ набирает $$$7$$$ очков и становится единоличным лидером. В случае ничьей у команды $$$B$$$ будет $$$5$$$ очков, и обойти её может команда $$$D$$$, выиграв у $$$A$$$, но никак не команда $$$A$$$. Наконец, если выиграет команда $$$C$$$, то она наберёт $$$6$$$ очков и займёт первое место.
Таким образом, команда $$$A$$$ не сможет занять первое место ни при каких результатах оставшихся игр.
Кот Бенедикт недавно узнал, как выглядит слово кот на английском языке (cat, если вдруг вы не знаете).
Бенедикт дремлет, и ему снится сон. В этом сне он видит экран, на котором последовательно одна за другой появляются буквы, быстро сменяя друг друга. Каждая буква — это либо $$$C$$$, либо $$$A$$$, либо $$$T$$$.
Букв много, но ему нужно дотронуться лапкой сначала до какой-то из букв $$$C$$$, потом до какой-то из букв $$$A$$$, а затем — до какой-то из букв $$$T$$$. Когда ему это удаётся, буквы пропадают, а на экране показывают забавный короткий ролик про котов.
Ваша задача — определить, сколькими способами Бенедикт может сформировать слово $$$CAT$$$. Поскольку это число может быть достаточно большим, выведите в качестве ответа остаток от деления этого числа на $$$10000019$$$ $$$\left( 10^7 + 19 \right)$$$.
В первой строке содержится непустая последовательность, состоящая из символов $$$C$$$, $$$A$$$, $$$T$$$ (заглавных букв латинского алфавита), в том порядке, в котором они появляются на экране. Последовательность имеет длину не более $$$10^5$$$ символов.
Гарантируется, что последовательность содержит хотя бы один символ $$$C$$$, хотя бы один символ $$$A$$$ и хотя бы один символ $$$T$$$.
Выведите единственное целое число — остаток от деления на $$$10000019$$$ $$$\left( 10^7 + 19 \right)$$$ количества способов, которыми кот может сформировать слово $$$CAT$$$.
В подзадачах с первой по четвёртую применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
В пятой подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
Почти для всех подзадач требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.
Ради краткости будем обозначать входную строку $$$s$$$, а её длину $$$|s|$$$.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | $$$|s| \le 6$$$ | нет | полная |
| 2 | 2 (до 10) | $$$|s| \le 1000$$$, | нет | полная |
| строка является соединением трёх | ||||
| строк: одной строки только из | ||||
| символов $$$C$$$, другой — только из | ||||
| символов $$$A$$$ и третьей — только из | ||||
| символов $$$T$$$, т.е. имеет вид | ||||
| $$$C \ldots CA \ldots AT \ldots T$$$ | ||||
| 3 | 2 (до 10) | в строке содержится только один | нет | полная |
| символ $$$A$$$, $$$|s| \le 10^5$$$ | ||||
| 4 | 2 (до 20) | $$$|s| \le 10^2$$$ | 1, 2, 3 | полная |
| 5 | 0 (50) | $$$|s| \le 10^5$$$ | 1, 2, 3, 4 | первая ошибка |
CACATT
6
ACTCT
0
ATCCATATTA
10
Поясним приведённые примеры.
Перенумеруем буквы в первом примере, начиная с $$$1$$$. Тогда слово $$$CAT$$$ можно сформировать следующими способами: $$$1 2 5$$$, $$$1 2 6$$$, $$$1 4 5$$$, $$$1 4 6$$$, $$$3 4 5$$$, $$$3 4 6$$$. Иных способов последовательно выбрать сначала $$$C$$$, потом $$$A$$$, потом $$$T$$$, не существует.
Во втором примере нет ни одного способа последовательно получить слово $$$CAT$$$.
Перенумеруем буквы в третьем примере (также начиная с $$$1$$$). Способы, которыми можно получить слово $$$CAT$$$, будут следующими: $$$3 5 6$$$, $$$4 5 6$$$, $$$3 5 8$$$, $$$4 5 8$$$, $$$3 5 9$$$, $$$4 5 9$$$, $$$3 7 8$$$, $$$4 7 8$$$, $$$3 7 9$$$, $$$4 7 9$$$. В отличие от первого примера не все буквы участвуют в образовании слова.
Также приведём пояснение про вычисления с остатком от деления.
Пусть есть числа $$$a$$$ и $$$b$$$, которые нужно сложить и сообщить остаток от деления их суммы на число $$$d$$$. Можно сделать это непосредственно: сначала вычислить $$$s = a + b$$$, а затем посчитать $$$s \mod d$$$, где mod обозначена операция взятия остатка от деления.
Однако можно поступить и по-другому: сначала вычислить $$$q = a \mod d$$$ и $$$p = b \mod d$$$, а потом уже посчитать $$$(p + q) \mod d$$$. Действительно, если $$$a$$$ представимо в виде $$$k_a \cdot d + q$$$, а $$$b$$$ — в виде $$$k_b \cdot d + p$$$, то их сумма запишется как $$$s = (k_a + k_b) \cdot d + (q + p)$$$. При вычислении остатка от деления $$$s$$$ на $$$d$$$ определять его значение будет только сумма $$$(q + p)$$$.
Хотя по отдельности $$$q \lt d$$$ и $$$p \lt d$$$, их сумма может быть больше $$$d$$$, поэтому результат вычисляется именно как $$$(p+q) \mod d$$$.
Такой подход позволяет поддерживать результат вычислений не превосходящим значения $$$2 \cdot (d - 1)$$$.
Аналогично можно показать, что остаток от деления произведения чисел $$$a$$$ и $$$b$$$ на число $$$d$$$ будет определяться произведением их остатков — $$$(p \cdot q) \mod d$$$.
Коту Бенедикту очень нравится число $$$k$$$ и он хочет стать $$$k$$$-мышовым котом.
Как известно, кот считается $$$k$$$-мышовым, если он в течение некоторого времени ловит не менее $$$k$$$ мышей. Известны последовательные моменты времени $$$(0 \le) \, t_1 \le t_2 \le \ldots \le t_n$$$, в которые кот Бенедикт ловил мышей. Для каждого момента $$$t_i$$$ также известно количество мышей $$$m_i$$$, которых кот поймал в этот момент.
Кот Бенедикт хотел бы продемонстрировать, что он способен поймать $$$k$$$ мышей за короткое время. Поэтому он хочет выбрать наиболее короткий отрезок времени из диапазона от $$$0$$$ до $$$t_n$$$ (включительно), в течение которого он поймал не менее $$$k$$$ мышей.
Ваша задача — указать границы такого временного отрезка минимальной длины, которые позволят считать кота Бенедикта $$$k$$$-мышовым. Если существует несколько вариантов ответа, выведите любой из них.
В первой строке содержатся целые числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 3 \cdot 10^5,\, 1 \le k \le 10^{18})$$$ — количество моментов времени, в которые кот Бенедикт ловил мышей, а также число $$$k$$$.
Во второй строке содержатся целые числа $$$t_1, t_2, \ldots, t_n$$$ $$$\left(0 \le t_1 \le t_2 \le \ldots \le t_n \le 10^{18} \right)$$$ — моменты времени, в которые кот Бенедикт ловил мышей.
В третьей строке содержатся целые числа $$$m_1, m_2, \ldots, m_n$$$ $$$\left(1 \le m_j \le 10^{9}, \, j = 1, 2, \ldots, n \right)$$$, $$$m_j$$$ — количество мышей, которых кот Бенедикт поймал в момент $$$t_j$$$.
Выведите два целых числа — начальный и конечный моменты времени, ограничивающие временной отрезок минимальной длины, в течение которого кот Бенедикт поймал не менее $$$k$$$ мышей. Разделяйте числа пробелом или переводом строки.
Если существует несколько вариантов ответа, выведите любой из них.
Если кот Бенедикт не сможет стать $$$k$$$-мышовым котом, выведите в качестве ответа два числа: $$$-1$$$ $$$-1$$$.
В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Баллы за подзадачи с третьей по пятую начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач.
Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 20) | $$$n \le 1000, \, k \le 1000, $$$ | нет | полная |
| $$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^6, \, $$$ | ||||
| $$$m_j = 1 \, (j = 1, 2, \ldots, n)$$$ | ||||
| 2 | 2 (до 20) | $$$n \le 1000, \, k \le 10^9, $$$ | 1 | полная |
| $$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^6, \, $$$ | ||||
| $$$m_j \le 10^6 \, (j = 1, 2, \ldots, n)$$$ | ||||
| 3 | 0 (20) | $$$n \le 3 \cdot 10^5, \, k \le 10^9, $$$ | 1 | первая ошибка |
| $$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^9, \, $$$ | ||||
| $$$ m_j = 1 \, (j = 1, 2, \ldots, n)$$$ | ||||
| 4 | 0 (20) | $$$n \le 3 \cdot 10^5, \, k \le 10^9, $$$ | 1, 2, 3 | первая ошибка |
| $$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^9, \, $$$ | ||||
| $$$ m_j \le 5000 \, (j = 1, 2, \ldots, n)$$$ | ||||
| 5 | 0 (20) | любые возможные значения | 1, 2, 3, 4 | первая ошибка |
7 3 0 6 8 19 22 23 25 1 1 1 1 1 1 1
22 25
11 7 5 8 8 14 23 37 42 42 55 64 71 2 1 2 1 4 3 2 2 5 6 2
37 42
5 8 1 5 15 20 28 2 1 1 2 1
-1 -1
Поясним приведённые примеры.
В первом примере кот ловит по одной мыши в каждый момент времени.
Таким образом, кот может утверждать, что может стать $$$k$$$-мышовым котом за $$$3$$$ единицы времени.
Во втором примере минимальное время, которое потребуется коту — $$$5$$$ единиц времени: он поймает трёх мышей в момент $$$37$$$, а затем еще дважды по две мыши в момент $$$42$$$.
В третьем примере кот не сможет стать $$$k$$$-мышовым
С точки зрения кота Бенедикта, каждое время суток интересно по-своему. Когда наступает вечер, в парке включают фонари, и Бенедикту из окна видна цепочка из $$$n$$$ светящихся шаров.
Однако лампочки в фонарях иногда перегорают, и работникам парка приходится их заменять. Работники парка полагают, что сразу же заменять перегоревшую лампочку необязательно. Они дожидаются первого момента времени, когда перегоревших лампочек станет не менее $$$m$$$, и только тогда отправляются менять их на новые.
Работники парка, отправляясь менять лампочки, действуют следующим образом.
Они берут лампочки со склада в нужном для замены всех перегоревших лампочек количестве (обратите внимание, что одновременно могут перегорать несколько лампочек, поэтому количество взятых лампочек может превосходить $$$m$$$) и двигаются в направлении от первого к последнему фонарю.
Все лампочки занумерованы номерами от $$$1$$$ до $$$s$$$ ($$$n \le s$$$). Работники устанавливают лампочки в соответствии с их номерами:
Когда работники в очередной раз придут на склад и обнаружат, что имеющегося количества лампочек недостаточно для замены всех перегоревших, они не станут менять лампочки вовсе и проинформируют начальство о необходимости приобретения лампочек. Приобретение лампочек — процесс достаточно долгий, поэтому после информирования начальства работники парка в полном составе отправятся в отпуск.
Вам известна длительность работы в днях лампочки в каждом фонаре и каждой лампочки на складе.
Считайте, что все лампочки в фонарях установлены сегодня, и это первый день работы лампочек в фонарях. Из соображений общности установку лампочек будем считать первой состоявшейся заменой. Лампочка, находящаяся на складе, не расходует свой ресурс, пока не будет установлена в фонаре.
Работники парка интересуются номером дня $$$k$$$, в который они проинформируют начальство о необходимости закупки лампочек (и, соответственно, у них появится возможность отправиться в отпуск).
Кот Бенедикт хотел бы узнать:
Оба этих значения кот Бенедикт хочет узнать на отрезке от сегодняшнего дня до дня $$$k$$$.
Ваша задача — определить эти три числа.
В первой строке содержатся целые числа $$$n$$$, $$$s$$$, $$$m$$$ $$$\left(1 \le n \le s \le 2 \cdot 10^5; 1 \le m \le n \right)$$$ — количество фонарей, количество лампочек на складе, количество перегоревших лампочек, которое с точки зрения работников парка является поводом отправиться их менять.
Во второй строке содержится $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ $$$(1 \le d_i \le 10^6, \, i = 1, 2, \ldots, n)$$$, $$$d_i$$$ — длительность работы лампочки, установленной в фонаре $$$\#i$$$.
В третьей строке содержится $$$s$$$ целых чисел $$$t_1, t_2, \ldots, t_s$$$ $$$(1 \le t_j \le 10^6, \, j = 1, 2, \ldots, s)$$$, $$$t_j$$$ — длительность работы лампочки, имеющей складской номер $$$\#j$$$.
Выведите три числа.
Первое число — номер дня, в который работникам парка придётся писать заявку (и они смогут отправиться в долгожданный отпуск).
Второе число — максимальное количество дней, которое пройдёт между двумя последовательными заменами лампочек в каком-либо одном фонаре.
Третье число — максимальное суммарное количество дней, которое какой-либо один фонарь будет оставаться неработающим.
Разделяйте числа пробелами или переводами строк.
Во подзадачах с первой по третью применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Баллы за четвёртую подзадачу начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
В первой подзадаче лампочки, исходно установленные в фонарях, двух видов: с длительностью работы $$$a$$$ и с длительностью работы $$$b$$$. Все лампочки на складе имеют одну и ту же длительность работы $$$c$$$.
Во второй подзадаче все лампочки на складе имеют одну и ту же длительность работы $$$c$$$.
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач.
Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 1 (до 10) | $$$s \le 1000, \, d_j \le 1000, \, t_i \le 1000 $$$ | нет | полная |
| $$$d_j \in \{a, b\}, \, t_i = c$$$ для всех $$$j$$$, $$$i$$$ | ||||
| 2 | 2 (до 30) | $$$s \le 1000,\, d_j \le 1000, \, t_i \le 1000 $$$ | 1 | полная |
| $$$t_i = c$$$ для всех $$$j$$$, $$$i$$$ | ||||
| 3 | 2 (до 30) | $$$s \le 1000,\, d_j \le 1000, \, t_i \le 1000 $$$ | 1, 2 | полная |
| для всех $$$j$$$, $$$i$$$ | ||||
| 4 | (30) | любые возможные значения | 1, 2, 3 | первая ошибка |
3 3 2 7 4 7 8 4 6
13 7 5
7 19 3 5 2 14 8 11 8 18 7 4 6 3 3 4 10 21 19 19 20 21 12 13 3 5 4 4 5
36 22 7
Во втором примере (только в условии) часть данных из третьей строки перенесена на четвёртую строку, поскольку не помещалась в колонку таблицы. В тестирующей системе никаких переносов строк нет.
Поясним приведённые примеры.
В первом примере работники отправятся менять лампочки в день $$$7$$$. В день $$$4$$$ перегорит одна лампочка, но для них это не будет поводом делать замену (они планируют делать замены, если перегоревших лампочек не меньше $$$2$$$). В день $$$7$$$ перегорят ещё две лампочки, суммарное количество перегоревших станет равным $$$3$$$, и работники пойдут на склад.
На складе они обнаружат достаточное количество лампочек — $$$3$$$ штуки. Так что в день $$$7$$$ в первом фонаре будет установлена лампочка, которая проработает $$$8$$$ дней, во втором — лампочка, которая проработает $$$4$$$ дней, а в третьем — лампочка, которая проработает $$$6$$$ дней.
Это означает, что в день $$$11$$$ лампочка, установленная во втором фонаре, перегорит. Через два дня, в день $$$13$$$ перегорит лампочка в третьем фонаре. Перегоревших лампочек станет $$$2$$$, и работники отправятся на склад. Поскольку лампочек на складе не окажется, в день $$$13$$$ они составят заявку.
В период времени до дня $$$13$$$ замены лампочек производились в «нулевой» день, а затем в седьмой день — так что максимальное время прошедшее между двумя последовательными заменами составит $$$7$$$ дней.
Максимальное суммарное время, которое не работал какой-либо один фонарь, составляет $$$5$$$ дней для второго фонаря. Как легко видеть, первый и третий фонари до дня $$$13$$$ всегда были в работающем состоянии. А вот второй фонарь не работал сначала $$$3$$$ дня — c $$$4$$$ по $$$7$$$ день, а затем ещё $$$2$$$ дня — с $$$11$$$ по $$$13$$$ день. В условии предлагается ограничиться днём, в который была сформирована заявка на приобретение лампочек, поэтому о дальнейшей «истории» этого фонаря никаких предположений не делается.
Второй пример демонстрирует различные ситуации замен лампочек. Заметим, что значение $$$22$$$ (максимальное количество дней, прошедших между последовательными заменами лампочек) достигается для седьмого фонаря.
Максимальное суммарное количество дней, которое не работал какой-либо фонарь, составляет $$$7$$$ и достигается для второго и пятого фонарей.