Задача 0A. Astrological prediction ≡

Условие

Астролог Тимофей считает год счастливым, если его номер состоит из различных последовательных цифр. Например, ближайший такой год наступит в 2031-м. По номеру года определите, через сколько лет наступит счастливый год?

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

Единственная строка входных данных содержит натуральное число n — номер года.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 9876543210

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

2023

8

2031

0

Задача 0B. Bricks in the wall ≡

Условие

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

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

Переворачивать кирпичи нельзя — все они должны сохранять горизонтальное положение.

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

Во входных данных указано число n, за которым следует ровно n целых чисел W_i.
Далее записано число L, задающее ширину слоя.

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

Выходные данные должны содержать последовательность из номеров кирпичей,
расположенных в порядке формирования слоев:
вначале идут кирпичи 1-го слоя,
за ними 2-го и так далее.
При этом полагается, что кирпичи нумеруются,
начиная с нулевого.

Ограничения

0 < W_i ≤ L ≤ 20, 0 < n ≤ 100

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

8
1 2 5 1 4 1 3 1
5

4 7 1 6 2

7
1 2 5 5 2 3 3
6

5 6 0 3

6
1 1 1 1 1 1
7

Задача 0C. Counting ones ≡

Условие

Данная задача является интерактивной. Ваша программа будет взаимодействовать с программой жюри путем отправки и приема сообщений определенного вида.

У жюри есть двумерная матрица N строк на M столбцов заполненная числами, где каждое число может быть либо 1, либо 0. Строки имеют нумерацию с 1 по N сверху вниз, столбцы — с 1 по M слева направо.

Ваша программа может делать запросы вида "? Xi Yi Ai Bi", где i — номер запроса, X_i, Y_i — координаты левого верхнего угла прямоугольника, номера строки и столбца соответственно, а A_i, B_i — размеры сторон прямоугольника, количество строк и столбцов соответственно. В ответ на запрос программа жюри сообщит о количестве единиц в прямоугольнике из запроса.

Каждый из прямоугольников должен целиком лежать внутри матрицы, то есть должны выполняться следующие неравенства:

1 ≤ X_i, A_i ≤ N и 1 ≤ Y_i, B_i ≤ M

X_i + A_i − 1 ≤ N и Y_i + B_i − 1 ≤ M

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

min(A₁, B₁) < min(N, M) и max(A₁, B₁) < max(N, M)

min(A_i, B_i) < min(A_i − 1, B_i − 1) и max(A_i, B_i) < max(A_i − 1, B_i − 1) для i > 1

Требуется определить количество единиц в матрице, сделав любое количество запросов. Гарантируется, что значения чисел в матрице определены заранее и не зависят от запросов.

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

В первой строке входных данных записаны целые числа N и M — размеры матрицы.

Протокол взаимодействия

Чтобы сделать i-й запрос, ваша программа должна вывести "? Xi Yi Ai Bi", где X_i, Y_i — целые числа, координаты левого верхнего угла прямоугольника, номера строки и столбца соответственно, а A_i, B_i — целые числа, размеры сторон прямоугольника, количество строк и столбцов соответственно.

После запроса программа жюри отвечает вашей программе целым числом S — количеством единиц в прямоугольнике из запроса.

Когда ваша программа определила ответ на задачу, она должна вывести "! S", где S — целое число, количество единиц в матрице. После вывода ответа программа должна завершиться.

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error".

Каждый запрос и вывод окончательного результата должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Ограничения

10 ≤ N, M ≤ 100

0 ≤ S ≤ 10⁴

Пояснение к примерам

Матрицы из примеров представлены на картинке.

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

11 13

34

0

0

? 1 1 10 12

? 1 11 11 3

? 10 1 2 10

! 34

10 10

38

28

23

16

13

5

3

3

0

? 1 2 9 9

? 3 1 8 8

? 4 2 7 7

? 2 4 6 6

? 5 5 5 5

? 3 7 4 4

? 8 8 3 3

? 1 1 2 2

? 10 10 1 1

! 44

Задача 0D. Doubly-periodic world ≡

Условие

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

Это значит, что по каждой из осей координат x и y выполняется условие периодичности с периодом Lx и Ly соответственно.
Иначе говоря, точки с координатами (x + u ⋅ Lx, y + v ⋅ Ly) при любых целых u и v являются тождественными.

В целях научного эксперимента из точки с координатами (0, 0) выпускается луч, заданный вектором D⃗ = (dx, dy).
Требуется определить минимальное расстояние, которое пройдет луч прежде чем попасть в исходную точку.

Результат следует записать в единицах измерения, равных длине вектора D⃗,
т.е. найти наименьшее λ  > 0 такое, чтобы при сдвиге на вектор λ  ⋅ D⃗ можно было попасть в исходную точку.

Полученное число должно быть представлено в виде несократимой дроби: λ  = αβ.

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

В начале входных данных хранится число n, за которым следует n запросов,
каждый из которых задается набором целых чисел: Lx_i, Ly_i, dx_i и dy_i.

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

Выходные данные должны содержать значения α_i и β_i,
полученные в ответ на каждый i-й запрос.

Ограничения

1 ≤ (Lx_i, Ly_i) ≤ 10⁶,  − 10⁶ ≤ (dx_i, dy_i) ≤ 10⁶, |dx_i| + |dy_i| > 0,
1 ≤ n ≤ 10⁵.

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

4

17 18 -6 -8
15 16 6 8
13 14 4 0
10 12 0 2

153 2
10 1
13 4
6 1

Задача 0E. Erasing numbers ≡

Условие

В Научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа от 1 до n и пытается ответить на вопрос, возможно ли стереть в середине списка несколько (не менее одного) чисел, идущих подряд, чтобы сумма оставшихся чисел слева равнялась сумме оставшихся чисел справа?

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

Единственная строка входных данных содержит натуральное число n.

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

Выведите в первой строке неотрицательное целое число — количество различных способов стереть числа.

Ограничения

3 ≤ n ≤ 10⁵

Пояснения к примерам

В первом примере дано n = 5. Перечислим все способы стереть числа в середине ряда:

• 1 # 3 4 5
• 1 2 # 4 5
• 1 2 3 # 5
• 1 # # 4 5
• 1 2 # # 5
• 1 # # # 5

Ни в одном из них нужное свойство не достигается.

Во втором примере дано n = 21. Перечислим все хорошие способы стереть числа в середине ряда:

• 1 2 3 4 5 6 # # # ## ## ## ## ## ## ## ## ## ## ## 21
• 1 2 3 4 5 6 7 8 9 10 11 12 ## ## ## ## ## 18 19 20 21

В первом списке сумма чисел слева и справа равны 21, во втором — 78. Всего два способа.

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

5

0

21

2

Задача 0F. Flag of Chita ≡

Условие

Флаг Читы представляет собой полотнище прямоугольной формы, разделённое на четыре элемента. Отношение ширины флага к его длине 2:3. В древковой части флага — равнобедренный треугольник жёлтого цвета, который имеет основание равное ширине флага (вертикальный размер полотнища), и высоту, равную половине его длины (горизонтальный размер полотнища). К треугольнику примыкают равновеликие полосы зелёного, белого и красного цветов.

Состав цветов флага отражает цвета герба городского округа «Город Чита», неся традиционное геральдическое значение:

• жёлтый (золото) — символ богатства и справедливости;
• красный (червлень) — символ мужества, храбрости и неустрашимости;
• зелёный (зелень) — символ надежды, радости и изобилия;
• белый (серебро) — символ чистоты, совершенства и независимости.

На координатной плоскости нарисовали флаг Читы высотой h так, как показано на рисунке (в первой четверти, левый нижний угол совпадает с началом координат). Определите цвет точки с указанными координатами.

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

Три строки входного файла содержат три натуральных числа, записанных через пробел: h — высота флага, а также x и y — координаты точки. Гарантируется, что h делится нацело на 12.

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

Выведите Green, White, Red или Yellow — ответ на вопрос задачи. Выведите Line, если точка лежат на границе флага или на линии, разделяющей две или три цветные области.

Ограничения

12 ≤ h ≤ 10⁹

0 ≤ x ≤ 3 × h2

0 ≤ y ≤ h

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

Смотри рисунок.

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

12
17
7

White

Задача 0G. Grading ≡

Условие

В классе учится N человек. Для удобства будем нумеровать их от 1 до N.

Однажды учитель по информатике дал очень сложную контрольную работу. Естественно, есть люди, которые ее спишут, а есть люди, которые будут делать ее сами и получат максимальную оценку (в школе K-бальная система оценивания, то есть ученик может получить оценку, которая равна натуральному числу на промежутке от 1 до K). Но если человек с номером U спишет у человека с номером V, и у человека V балл равен X, то у человека U балл будет равен X − 1 (если X = 1, то человек получит оценку 1, так как оценки меньше нет).

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

Вам известно, кто у кого списывал. Помогите классу и скажите, кто какую оценку получит!

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

В первой строке вводятся натуральные числа N и K — количество учеников и число системы оценивания. В следующей строке находится последовательность A из N натуральных чисел, i-ое число означает то, что i-ый школьник списал у A_i-ого.

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

В единственной строке выведите N чисел, где i-ое число показывает, какую оценку получил i-ый школьник.

Ограничения

1 ≤ K ≤ N ≤ 10⁵, 1 ≤ A_i ≤ N

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

Первый списал у второго, второй списал у четвертого, четвертый списал у первого. Эти 3 ученика получили оценку 1. Третий сделал работу сам и получил оценку 3, пятый списал работу у третьего и получил 2.

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

5 3
2 4 3 1 3

1 1 3 1 2

Задача 0H. Historical search ≡

Условие

Молодой историк Вася в рамках своей диссертационной работы занимается сопоставлением записей из хранящихся в архиве документов.

Каждый документ охватывает определенный промежуток времени и содержит информацию о произошедших за это время событиях.

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

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

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

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

В начале входных данных хранится натуральное число N, за которым следует 2 × N целых чисел,
задающих границы временного интервала [A_i, B_i] для каждого из документов.

Далее следует число M и ровно M запросов, содержащих время события C_j.

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

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

При этом полагается, что нумерация документов начинается с нуля.

Ограничения

Гарантируется, что суммарное число документов на выходе не превосходит 10⁶.

 − 10⁶ ≤ A_i ≤ B_i ≤ 10⁶,  − 10⁶ ≤ C_j ≤ 10⁶, 1 ≤ N ≤ 2 ⋅ 10⁴, 1 ≤ M ≤ 10⁵

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

6
-1  0
-1 -1
-1  0
 4  4
 2  3
 3  3

8
-1
 0
 2
 3
 1
-2
 4
 5

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

Задача 0I. Image correction ≡

Условие

Матрица фотоаппарата представляет собой прямоугольную таблицу размерности [n × m], состоящую из светочувствительных элементов (ячеек). В момент съемки каждой ячейке такой таблицы ставится в соответствие вещественное значение X_{i j}, указывающее ее состояние (интенсивность).

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

Коэффициент влияния каждой такой ячейки на полученное значение равен 1 / (2^l ⋅ N_l), где l — номер содержащего ее слоя, N_l — число ячеек в l-м слое.

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

Для заданной матрицы Y, полученной в результате измерений, и радиуса воздействия k требуется восстановить исходные значения X_{i j}.

Значения фиктивных ячеек (лежащих за пределами матрицы) полагаются равными нулю.

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

В начале входных данных хранятся три натуральных числа: n, m и k.
Далее следует матрица результатов измерений Y, записанная в строчном формате.

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

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

Ограничения

0 ≤ Y_{i j} ≤ 10, 0 < n ⋅ m ≤ 40 000, 0 < k ≤ 6

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

9 6 3
0.26620 1.51042 0.59606 2.85301 0.76968 3.75000
1.51042 0.67130 3.09027 1.05324 4.38657 0.90856
0.59606 3.09027 1.13426 4.57754 1.29629 5.21412
2.88194 1.08217 4.61805 1.42940 5.60763 0.91435
0.87384 4.51388 1.43518 5.72916 1.08796 1.78819
4.13773 1.31944 5.72916 1.18055 2.03704 0.58449
0.98958 5.53819 1.12847 2.10648 0.76389 2.69097
4.98842 0.92592 1.98495 0.76389 2.95717 0.61343
0.49190 1.63773 0.54398 2.69097 0.61343 3.59375

0.00000 1.11111 0.00000 2.22222 0.00000 3.33333
1.11111 0.00000 2.22222 0.00000 3.33333 0.00000
0.00000 2.22222 0.00000 3.33333 0.00000 4.44444
2.22222 0.00000 3.33333 0.00000 4.44444 0.00000
0.00000 3.33333 0.00000 4.44444 0.00000 1.11111
3.33333 0.00000 4.44444 0.00000 1.11111 0.00000
0.00000 4.44444 0.00000 1.11111 0.00000 2.22222
4.44444 0.00000 1.11111 0.00000 2.22222 0.00000
0.00000 1.11111 0.00000 2.22222 0.00000 3.33333

Задача 0J. Javelin-throwing ≡

Условие

Как-то раз Женя и Анжелика оказались на соревнованиях по метанию копья в качестве зрителей. В соревновании участвовали N спортсменов.

Каждый раз, когда i-ый спортсмен кидал копьё, Женя сообщал Анжелике, на сколько метров кинул копьё данный спортсмен (случайно получилось так, что все числа, которые назвал Женя, были попарно различными). В это время Анжелика записывала на листик, какое место после своего броска займет i-ый спортсмен.

К сожалению, когда соревнование закончилось, Анжелика потеряла листик и очень расстроилась. Но Женя помнит, на сколько метров i-ый спортсмен бросил своё копьё. Помогите ребятам восстановить потерянный листик!

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

В первой строке вводится натуральное число N — количество спортсменов.

Во второй строке вводится последовательность различных натуральных чисел L, где L_i — число, которое показывает, на сколько метров кинул своё копьё i-ый спортсмен.

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

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

Ограничения

1 ≤ N ≤ 10⁵, 1 ≤ L_i ≤ 10⁹

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

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

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

4
20 40 30 25

1 1 2 3

Задача 0K. Kind of cheating ≡

Условие

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

• В случае если один участник парного забега срывается, он проигрывает
• Если же оба участника финишируют, то побеждает тот участник, который показал лучшее время
• В случае равенства времён или если срываются оба участника, побеждает участник с лучшим временем в квалификации

Паулундра победила в квалификации, показав лучшее время, и подглядела стратегию каждого из n участников соревнования. Она знает, что участник с номером i планирует пробежать трассу за t_i секунд и знает вероятность в процентах того, что этот участник сорвётся p_i. Так же Паулундра знает, что может пробежать трассу за любое время в промежутке от a до b и при этом вероятность срыва при выбранном времени x можно вычислить следующим образом: 1 − x − ab − a.

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

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

Первая строка входных данных содержит два целых числа a и b. Вторая строка содержит одно целое число n. Далее следует n строк содержащих по два целых числа t_i и p_i.

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

Выведите n целых чисел x_i.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ a, b, t_i ≤ 10⁹

1 ≤ p_i ≤ 100

a < b

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

1 5
5
4 10
10 50
1 99
5 50
2 90

4
5
1
5
2

Задача 0L. Long-term activity ≡

Условие

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

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

Единственная строка входных данных содержит натуральное число n.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10¹⁰⁰⁰⁰⁰.

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

Исходная строка: 2023.

1) 2032.

2) 2302.

3) 3202.

4) 3220.

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

2023

4

Задача 0M. Must be excluded ≡

Условие

Слон Пахом - начинающий разработчик. Первая задача Пахома на новом месте работы - это разработка программы для удаления персональных данных из текста, состоящего из букв латинского алфавита, цифр и пробелов.

Персональными данными является два подряд идущих через пробел числа, состоящего из четырёх цифр и шести цифр соответственно (серия и номер паспорта). Их требуется заменить на последовательность символов "#### ******".

Пахом без проблем справился с этой задачей. Теперь очередь за вами.

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

Входные данные содержат одну строку S.

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

Выведите строку S после удаления персональных данных.

Ограничения

1 ≤ |S| ≤ 1000

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

My passport details are 1234 533224 please do not distribute them

My passport details are #### ****** please do not distribute them

A826 B1234 654321 fgfgh 3333 456789s 5432 123456 0000 000000 56554 34534 2344 32456 0000 000000

A826 B1234 654321 fgfgh 3333 456789s #### ****** #### ****** 56554 34534 2344 32456 #### ******

Задача 1A. Максимум в скользящем окне ≡

Условие

Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r. Изначально оба они указывают на первый элемент массива. Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

Формат входного файла

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел a_i - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

Формат выходного файла

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 10⁵

|a_i| ≤ 10⁹

0 ≤ m ≤ 2n − 2

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

4
-3 -2 -1 0
6
RRRLLL

-2 -1 0 0 0 0

10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL

4 4 4 4 5 8 8 8 8 8 8 6

Задача 1B. Ближайшее число ≡

Условие

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

Формат входного файла

Входной файл содержит целое число N за которым следует N целых чисел a_i - исходная последовательность.

Формат выходного файла

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

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

4 1 2 3 4

2 3 4 4

1
1

1

Задача 1C. Супергерой ≡

Условие

Юный супергерой Вася однажды выяснил, что на один из небоскрёбов его города планирует напасть группа из N злодеев. Небоскрёб состоит из M этажей, пронумерованных от 1 до M. Вася прибыл на первый этаж непосредственно перед началом нападения злодеев и приготовился его отражать.

Злодей номер i появляется на этаже f_i через t_i секунд после начала нападения, и начинает творить зло со скоростью одно злое дело в секунду.

Каждую секунду Вася проделывает следующие действия:

1. Если на текущем этаже находятся злодеи, обезвреживает их.
2. Сдвигается вниз или вверх на один этаж по направлению к ближайшему злодею.
3. Если расстояния равны, Вася предпочитает подниматься вверх.
4. Если в текущий момент ни одного активного злодея в небоскрёбе нет, Вася остаётся на текущем этаже.

Требуется определить, сколько злых дел успеют совершить все злодеи в сумме.

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

Входной файл содержит целые числа M N, за которыми следует N пар целых чисел t_i f_i.

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

Выходной файл должен содержать единственное целое число — количество злых дел.

Ограничения

1 ≤ N ≤ 10⁶

1 ≤ f_i ≤ M ≤ 10⁹

1 ≤ t_i ≤ t_i + 1 ≤ 10⁹

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

3 3
1 2
2 3
5 1

4

100 1
1 100

99

1 1
1 1

0

Задача 1D. Кошачьи шпионы ≡

Условие

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

Мяуканье представляет из себя набор из букв m, e, o, w, причем этих букв может быть много, но одинаковые буквы всегда идут подряд.

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

Настоящие коты никогда не ошибаются и издают правильно мяуканье, а вот собаки-шпионы всегда допускают хотя бы одну ошибку.

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

Первая строка входного файла содержит одно целое число: n - количество допрошенных особей.

В следующих n строках содержится целое число m_i и строка s_i длинны m_i.

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

Выходной файл должен содержать одно целое число - количество шпионов.

Ограничения

0 < N ≤ 10⁵

0 < m_i ≤ 10⁵

0 < ∑m_i ≤ 4 * 10⁵

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

5
4 meow
11 meeeeooooow
4 miow
4 myau
5 hello

3

7
7 bonjour
7 alaykum
8 dobryden
2 ep
9 reverence
4 iiti
8 konishua

7

Задача 1E. Очередь к врачу ≡

Условие

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

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

Первая строка входных данных содержит два целых числа N — количество посетителей за последний день и K — длительность приема одного пациента.

Вторая строка содержит N чисел, отсортированных по возрастанию: t_i  — время, когда i − ый посетитель пришел на прием к терапевту.

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

Выходные данные должны содержать одно целое число  — максимальную длину очереди за последний день.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁹

0 ≤ t_i ≤ 10⁹

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

5 5
0 5 5 6 20

2

5 2
1 4 6 8 20

0

6 5
0 5 10 15 19 25

1