Задача A. Очередь на мойку ≡

Условие

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

Мойка почти современная и состоит из n почти одинаковых боксов. Каждый бокс моет машину за t_i минут.

Паша работает на кассе, куда водитель подъезжает после того, как машина была вымыта, и где он оплачивает мойку.

Для того, чтобы заработать больше денег Паша в этот день позвал к себе k друзей на машинах. И когда Юля подъехала к мойке перед ней уже была очередь из k машин.

Всё бы хорошо, но Паша работает ещё только t минут и после этого уходит. Поэтому все водители (и друзья, и Юля) хотят, чтобы за эти t минут помылось как можно больше машин.

Помогите Юле узнать успеет ли она помыть свою машину и увидеться с Пашей, до того, как он уйдёт.

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

Первая строка ввода содержит три целых числа n, k и t.

Вторая строка ввода содержит n целых чисел: t₁,t₂,...,t_n.

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

Выведите одно слово "YES" или "NO".

Ограничения

0 < n, t_i ≤ 10⁵

0 < t ≤ 10⁹

0 ≤ k ≤ 10⁹

Примечание

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

Примеры тестов

5 1 10
5 10 20 30 40

YES

4 3 100
60 70 110 120

NO

Задача B. Супер-пупер-маркет ≡

Условие

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

В супер-пупер-маркете находится n различных стендов, пронумерованных целыми числами от 1 до n. В этом супер-пупер-маркете используется тактика создания лабиринта, поэтому от i-го стенда покупатель перейдет к a_i-му стенду.

Вы — менеджер супер-пупер-маркета. Вам стало интересно, около какого стенда покупатель окажется через k переходов, если сейчас он находится около d-го стенда (причем Вам стало интересно q раз, то есть Вам нужно ответить на q независимых друг от друга запросов).

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

В первой строке входных данных вводятся натуральные числа n и q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵).

В следующей строке вводится n чисел, i-е по счету число равно a_i. Это означает, что от i-го стенда покупатель перейдет к a_i-му стенду (1 ≤ a_i ≤ n).

В следующих q строках вводятся числа d_i и k_i (1 ≤ d_i ≤ n, 1 ≤ k_i ≤ 10⁹). Это означает, что для каждого запроса вам нужно сообщить, около какого стенда покупатель окажется через k переходов, если сейчас он находится около d-го стенда.

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

Для каждого запроса на новой строке выведите порядковый номер нужного стенда.

Примеры тестов

3 5
2 3 1
1 1
1 2
1 3
1 4
1 5

2
3
1
2
3

Задача C. Кратные суммы ≡

Условие

У Анжелики есть массив натуральных чисел a, длина которого равна n, а также у Анжелики есть любимое число, равное s. Жене очень нравится этот массив, поэтому он просит Анжелику проводить над данным массивом операции. Всего Женя попросит Анжелику выполнить q операций. Каждая операция имеет один из двух видов:

• 1 k d — Женя просит Анжелику присвоить k-му элементу массива значение d (то есть, a_k = d);
• 2 — Женя просит Анжелику сообщить количество пар чисел l и r таких, что 1 ≤ l ≤ r ≤ n и сумма a_l + a_l + 1 + ...  + a_r − 1 + a_r кратна s.

Так как Женя очень надоедливый и хочет спросить Анжелику очень много раз, Анжелика скинула эту работу на Вас! Помогите Анжелике!

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

В первой строке вводятся натуральные числа n, s и q — длина массива, любимое число Анжелики и количество операций соответственно (1 ≤ n, q ≤ 50000, 2 ≤ s ≤ 50). В следующей строке вводится массив Анжелики (1 ≤ a_i ≤ 10⁹).

В последующих q строках вводятся запросы Жени. Если первое число в строке равно 1, то после него следуют числа k и d, это означает, что Женя хочет изменить значение a_k на d. Если первое число в строке равно 2, то после него ничего не следует, это означает, что Женя хочет узнать количество пар чисел l и r таких, что 1 ≤ l ≤ r ≤ n и сумма a_l + a_l + 1 + ...  + a_r − 1 + a_r кратна s.

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

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

Для каждого запроса второго вида на отдельной строке выведите количество подходящих пар чисел l и r.

Примеры тестов

4 3 5
1 2 1 2
2
1 2 1
2
1 2 3
2

4
2
3

Задача D. Весенний поход ≡

Условие

Наступила весна и Даша отправилась в поход, ей надо выбрать место для установки лагеря. Для удобства она мысленно разделила местность на квадраты. У неё получилось n × m квадратов. Некоторые квадраты оказались с лужами, а некоторые с приятным мягким сеном.

И для каждого квадрата она оценила его "приятность", то есть то, насколько бы она хотела ставить лагерь на этот квадрат. Лагерь располагается на прямоугольнике размера h × w блоков.

Помогите Даше определить место расстановки лагеря, сумма приятности квадратов которого максимальна.

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

Первая строка ввода содержит четыре числа n, m, h, w.

Затем идут n строк по m целых чисел в каждом.

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

Вывести одно число — максимальную приятность, которую может получить Даша.

Ограничения

0 < h ≤ n < 10³

0 < w ≤ m < 10³

∑Приятность ≤ 10⁹

Примеры тестов

2 3 2 1
1 0 10
2 3 30

40

Задача E. Минимизация числа ≡

Условие

У вас есть число N. А также есть число M, изначально равное нулю.

Вы можете выполнять следующие операции:

1. Прибавить к M единицу (+)
2. Отнять от M единицу (-)
3. Умножить M на 2 (*)
4. Поделить M нацело 2 (/)

Вы можете сделать до K таких операций, после чего вычисляется число, равное побитовому исключающему "или" (xor) чисел N и M.

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

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

Первая строка ввода содержит число K.

Вторая строка содержит число n записанное в двоичной системе счисления.

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

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

Ограничения

0 ≤ N ≤ 2¹⁰⁵

0 ≤ k ≤ 2 * 10⁵

Примечание:

Нельзя использовать операцию 2, если M = 0.

Примеры тестов

15
1000001111011011

1000000000000001

Задача F. Морской бой ≡

Условие

Женя с Анжеликой играют в морской бой! Поле Анжелики представлено в виде клетчатого прямоугольника из n строк и m столбцов. На поле находится один единственный корабль, который представлен в виде клетчатого прямоугольника из k строк и d столбцов (обратите внимание, что корабль именно таких размеров, его нельзя поворачивать, то есть не может быть корабля из d строк и k столбцов).

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

Какое количество выстрелов Анжелика разрешит сделать Жене?

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

В первой строке входных данных вводятся числа n, m, k, d  — размеры поля и размеры корабля соответственно (1 ≤ k ≤ n ≤ 10⁹, 1 ≤ d ≤ m ≤ 10⁹).

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

Выведите ответ на задачу.

Примеры тестов

3 3 2 2

1

Задача G. Шахтеры Online ≡

Условие

Денис и Женя захотели вместе поиграть в новую игру — «Шахтёры Online». Пока Женя пошел обустраивать базу и строить дом, Денис отправился в шахту за самым ценным ресурсом в игре — за алмазами. Зона, которую будет копать Денис, представляет собой поле n × n × n клеток. Алмазы в Шахтерах Онлайн находятся на n-м уровне по высоте. Денис уже хорошо изучил игру и точно знает, что алмазы будут находится на координате (x,y).

Рост персонажа в игре — одна клетка. Копать Денис может в пределах слоях на соседние клетки — вперед, назад, влево и вправо (Денис пользуется эффективной техникой копания, поэтому он сразу входит в скопанную клетку). Также Денис может копать под себя и провалиться на уровень ниже. Возвращаться же на уровни выше он не хочет, потому что он хочет похвастаться добытыми алмазами как можно быстрее. Но не стоит забывать, о том, что в мире «Шахтёров Online» есть лава, и Денис не очень хочет с ней сталкиваться или провалиться в неё. Также Денису следует быть осторожным, потому что лава имеет физику, может стечь на него сверху, ещё она разливается на одну клетку во все стороны, если клетка пустая (считается, что если Денис ломает клетку рядом с источником лавы, то лава мгновенно стекает на образовавшееся пространство, из-за чего Денису придется с ней контактировать).

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

Помогите Денису определить, сможет ли он похвастаться перед Женей алмазами!

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

В первой строке входных данных вводятся числа n и q — размер поля и количество блоков с лавой (2 ≤ n ≤ 100, 0 ≤ q ≤ n³ − 1). В следующих q строках вводятся числа h_i, x_i и y_i, которые показывают, что на h_i-м слое сверху в клетке с координатами (x_i, y_i) находится блок лавы. В последней строке вводятся числа x и y — координаты алмазов.

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

Выведите YES, если Денис сможет достигнуть желаемой алмазной руды, и NO, если дойти до алмазов, не искупавшись в лаве, нельзя.

Примеры тестов

3 4
2 1 1
2 1 3
2 3 1
2 3 3
2 2

YES

2 4
1 1 1
1 1 2
1 2 1
1 2 2
1 1

NO

Задача H. Домино ≡

Условие

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

Также Вася дал следующее определение: доминошка называется «особенной», если при её опрокидывании цепной реацией получается так, что на эту же доминошку падает другая доминошка.

Помогите Васе определить сколько «особенных» доминошек есть в его расстановке.

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

В первой строке — целое число N (N ≤ 10⁵).

Далее идут N строк, где в i-й строке сначала написано число M_i, после чего M_i целых чисел a_ij — номера доминошек, которые упадут, если упадет i-я доминошка. (M_i ≤ N, 1 ≤ a_ij ≤ N).

Гарантируется, что сумма по всем M_i не превосходит 2 ⋅ 10⁵.

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

Выведите одно число — количество «особенных» доминошек.

Примеры тестов

3
1 2
1 3
0

0

8
1 2
1 3
2 4 8
1 5
1 1
1 1
1 6
0

5

5
2 2 3
1 4
1 2
1 5
1 1

5