Информатика

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a,b) (где a,b — целые числа), перемещающую  Чертёжника из точки с координатами (x, y) в точку с координатами (x+a, y+b). Если числа a,b положительные, то значение соответствующей координаты увеличивается, если отрицательные — уменьшается.

Например, если Чертёжник находится в точке с координатами (4, 2), то команда Сместиться на (2,-3) переместит Чертёжника в точку (6,-1).

Запись  

Повтори k раз
  Команда1 Команда2 Команда3
конец

означает, что последовательность Команда1 Команда2 Команда3 повторится k раз.


Чертёжнику был дан для исполнения следующий алгоритм:

Повтори 11 раз 
  Сместиться на (2, 4) 
  Сместиться на (-4, 2) 
  Сместиться на (-4, -2) 
  Сместиться на (2, -4)
конец

Найдите количество точек с целочисленными координатами, лежащих на линии, нарисованной Чертежником, если исполнитель стартует в точке с целочисленными координатами.

 

Есть набор строк, который изначально пуст. Необходимо обрабатывать три различные операции над этим набором строк:

• 1 s: Добавить данную строку в набор.
• 2 k l: Узнать, существуют ли в наборе k строк (не обязательно различных) таких, что они имеют общий суффикс длины l. Этот суффикс не обязан быть наибольшим.
• 3 i: Удалить строку из набора, которая была добавлена в i-й операции (если она еще не была удалена).

Входные данные:
В первой строке дано одно целое число - количество операций q (1 <= q <= 10⁵), которые необходимо обработать.
Далее в каждой строке дано описание запроса. Сперва это число 1, 2 или 3, обозначающее тип запроса. 
Если это запрос первого типа, то далее дана строка s, суммарная длина которых не превышает 10⁵.
Если это запрос второго типа, то далее дано два целых числа k и l (1 <= k, l <= 10⁵).
Если это запрос третьего типа, то далее дано число i (1 <= i <= номер текущей операции), где i - номер операции первого типа.

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

Пример:
 

Входные данные	Выходные данные
9 1 aba 1 accba 2 2 2 2 2 3 1 aaaa 1 ababa 2 3 2 3 1 2 3 2	YES NO YES NO

Кайману снится необычный сон, будто он попал в странный район города. Этот район можно представить как граф-дерево, где вершины - это перекрестки и ребра - двусторонние дороги, которые соединяют эти перекрестки. Всего перекрестков n и у каждого свой номер от 0 до n-1.

Но не все так плохо в этом сне, ведь на каждой дороге между перекрестками с номерами u и v есть С_u,v пельменей! Кайман очень любит пельмешки, поэтому хочет съесть как можно больше, но есть проблема - если он побывает в каком-либо перекрестке более чем k раз, то на него нападет злой пельменный монстр.

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

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

Входные данные:
В первой строке следует два целых числа n и k (3 ≤ n ≤ 10⁵; 1 ≤ k ≤ 10⁵) — количество перекрестков и максимальное количество посещений каждого из перекрестков.
В следующих n - 1 строках следует по три целых числа u, v и C_u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C_u,v ≤ 10000), означающих, что перекрестки с номерами u и v связаны дорогой, на которой C_u,v пельменей.
Гарантируется, что перекрестки и дороги формируют дерево.

Выходные данные:
Выведите одно целое число - максимальное количество пельменей, которое сможет съесть Кайман.

Примеры:
 

Входные данные	Выходные данные
9 3 0 1 1 0 2 1 1 3 2 1 4 2 1 5 2 2 6 3 2 7 3 2 8 3	15
9 5 0 1 1 0 2 1 1 3 2 1 4 2 1 5 2 2 6 3 2 7 3 2 8 3	17
11 6 1 0 7932 2 1 1952 3 2 2227 4 0 9112 5 4 6067 6 0 6786 7 6 3883 8 4 7137 9 1 2796 10 5 6200	54092

Пояснение:
В первом примере нужно посетить перекрестки в следующем порядке: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, 2, 8. Тогда он съест суммарно 1+2+2+1+3+3+3 = 15 пельменей.
Обратите внимание, что ни один перекресток не посещается более чем 3 раза.
 

Хлоя недавно установила на свой телефон игру «Zuma». Игроку даётся ряд из n драгоценных камней, i-й из которых имеет цвет c_i. Цель игры — уничтожить все камни за как можно меньшее количество секунд.

За одну секунду Хлоя может выбрать любую подстроку (последовательность стоящих рядом камней), являющуюся палиндромом, и удалить её. После удаления данной подстроки оставшиеся камни сдвигаются, чтобы снова образовать непрерывный ряд. Какое минимальное количество секунд необходимо, чтобы уничтожить всю строку?

Напомним, что строка (или подстрока) является палиндромом, если она одинаково читается как слева направо, так и справа налево. В данном случае это означает, что цвет первого камня равен цвету последнего камня, цвет второго равен цвету предпоследнего и так далее.

Входные данные:
В первой строке входных данных записано единственное число n (1 ≤ n ≤ 500) — количество камней в изначальном ряду.
Во второй строке записано n целых чисел, i-е из которых равно c_i (1 ≤ c_i ≤ n) — цвет i-го камня в изначальном ряду.

Выходные данные:
Выведите единственное целое число — минимальное количество секунд, необходимое чтобы удалить все камни.

Примеры:
 

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

Пояснения:
Последовательность в третьем примере: [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []

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

Скажем, что квадраты i и j лежат в одной компоненте, если c_i = c_j и c_i = c_k для всех k, удовлетворяющих i < k < j. Иначе говоря, все квадраты на отрезке от i до j должны иметь одинаковый цвет.
Например, у полоски [3,3,3] есть 1 компонента связности, а у [5,2,4,4] их 3.

Игра «заливка» играется на этой полоске следующим образом:
В начале игры вы выбираете один произвольный стартовый квадрат (это не считается за ход).
Затем, в каждый ход, вы меняете цвет компоненты связности, содержащей стартовый квадрат на любой другой цвет.

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

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 5000) — количество квадратов.

Вторая строка содержит целые числа c₁,c₂,…,c_n (1 ≤ c_i ≤ 5000) — изначальные цвета квадратов.

Выходные данные:
Выведите одно целое число — минимальное количество ходов, которое нужно сделать.

Примеры:
 

Входные данные	Выходные данные
4 5 2 2 1	2
8 4 5 2 2 1 3 5 5	4
1 4	0

Пояснение:
Один из оптимальных способов в первом примере: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]

В городе M расположена кольцевая автодорога длиной в N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы стоимость доставки мусора была минимальной. Стоимость доставки мусора вычисляется, как вместимость пункта сбора умноженная на расстояние от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым. Контейнеры нумеруются с 1 до N.
Рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод?

Описание входных данных
Даны два входных файла (файл A и файл B), каждый из которых содержит (2 <= N <= 10⁹) чисел. Первое число N - количество контейнеров для мусора. Последующие N чисел - количество килограмм мусора, которое производится на точке.

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


Пример организации входных данных:
6
8
20
5
13
7
19
Для данного примера ответ - 6 (7*1 + 13*2 + 5*3 + 20*2 + 8*1 + 19*0).

 

Болеющие коровы решили помочь Фермеру Джону.
Для того, чтобы ограничить передачу болезни, N (2 ≤ N ≤ 10⁵) коров ФД решили попрактиковаться в "социальном дистанцировании" и "распределились" по ферме. Ферма представлена в виде прямой линии, с M взаимно не имеющими общих точек интервалами (1 ≤ M ≤ 10⁵), на которых растёт трава. Коровы хотят расставиться в точках с различными координатами, каждая точка покрыта травой, так, чтобы максимизировать значение D. Где D представляет расстояние между ближайшей парой коров. Помогите коровам определить наибольшее значение D.

Входные данные
Первая строка ввода содержит N и M. Каждая из следующих M строк описывает интервал двумя целыми числами a и b, где 0 ≤ a ≤ b ≤10¹⁸. Никакие два интервала не перекрываются и не касаются своими конечными точками. Корова, стоящая на конечной точке интервала считается стоящей на траве.
Выходные данные
Выведите наибольшее возможное значение D такое, что все пары коров не менее чем на D единиц друг от друга. Гарантируется, что существует решение с D>0.

Примеры

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

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L. 

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке подается 3 числа: количество чисел N (1 <= N <= 1 000 000),  L и C (\(1 <= L, C <= N <= 1 000 000\)). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Пример организации исходных данных во входном файле (для L = 3 и С = 1):
5 3 1
1
-1
-5
-2
3

В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной -4 будет: -5+(-2)+3. 
Ответ (для С = 3 и L = 1): -4. 

В ответе укажите два числа в одной строке через пробел: сначала значение искомой суммы для файла А, затем для файла B.

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

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L.

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке подается 3 числа: количество чисел N (1 <= N <= 1 000 000),  L и C (1 <= L, C <= N <= 10⁶). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Пример организации исходных данных во входном файле (для L = 3 и С = 3):
5 3 3
1
-1
2
-2
3

В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной 3 будет: 2+(-2)+3. 
Ответ (для L = 3 и С = 3): 3. 

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

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

Дана последовательность из N натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество нечётных чисел кратно K = 7. Найдите наибольшую сумму такой подпоследовательности. 

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 <= N <= 1 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1 000.

Пример организации исходных данных во входном файле (для К=4):
6
8
17
3
13
11
21

В этом наборе можно выбрать последовательности 8+17+3+13+11 (сумма 52) и 3+13+11+21 (сумма 48). 
Ответ (для K = 4): 52. 

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

Дана последовательность из N натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество чётных чисел кратно K = 8. Найдите наибольшую сумму такой подпоследовательности. 

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 <= N <= 1 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1 000.

Пример организации исходных данных во входном файле (для К=4):
6
9
16
4
12
10
18

В этом наборе можно выбрать последовательности 9+16+4+12+10 (сумма 51) и 4+12+10+18 (сумма 44). 
Ответ (для K = 4): 51. 

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

Пусть M – сумма минимального четного и максимального нечетного натуральных делителей целого числа, не считая единицы и самого числа. Если какого-либо делителя у числа нет (либо четного, либо нечетного), то значение этого делителя считается равным нулю.
Напишите программу, которая перебирает целые числа, большие 12 000 000, в порядке возрастания и ищет среди них такие, для которых значение 0 < M < 1 000 000 . Выведите первые пять найденных чисел и соответствующие им значения M. 

Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем – значение M (через один пробел). Строки выводятся в порядке возрастания найденных чисел.

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1<= N <= 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:
7
21
13
9
19
17
26
95
В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Для указанных программа должна вывести число 2.

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

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

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

Используя информацию из приведённой базы данных, определите сколько учащихся 11 класса школ ЗАО выбрали тестирование по физике. 

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

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

Используя информацию из приведённой базы данных, определите сколько учащихся 10 класса школ ЦАО выбрали тестирование по информатике.

Скачать файл

Художник Тюбик учит Незнайку рисовать. Он дал ему сетку с H строками и W столбцами. Все клетки сетки изначально выкрашены в белый цвет. Тюбик попросил Незнайку закрасить N из этих ячеек в черный цвет. I-я (1<=i<=N) ячейка, которую закрасил Незнайка, является ячейкой в a_i-й строке и b_i -м столбце. Для каждого целого числа j (0<=j<=9), определите сколько в сетке подпрямоугольников размером 3×3 содержит ровно j черных ячеек после того, как Незнайка закрасил N ячеек?

Входные данные
В первой строке заданы 3 целых числа: H, W (3<=H,W<=10⁹) и N (0<=N<=min(10⁵,H×W)). Далее идут N строк по 2 числа в каждом a_i (1<=a_i<=H) и b_i (1<=b_i<=W), 1<=i<=N, (a_i,b_i)≠(a_j,b_j), i ≠ j.

Выходные данные
Выведите 10 строк. В (j + 1)-й (0<=j<=9) строке должно быть указано количество подпрямоугольников размером 3 × 3 сетки, содержащей ровно j черных ячеек.
 

 

Примеры

№	Входные данные	Выходные данные
1	4 5 8 1 1 1 4 1 5 2 3 3 1 3 2 3 4 4 4	0 0 0 2 4 0 0 0 0 0
2	10 10 20 1 1 1 4 1 9 2 5 3 10 4 2 4 7 5 9 6 4 6 6 6 7 7 1 7 3 7 7 8 1 8 5 8 10 9 2 10 4 10 9	4 26 22 10 2 0 0 0 0 0
3	1000000000 1000000000 0	999999996000000004 0 0 0 0 0 0 0 0 0

 

Ушан с планеты Блук открыл пекарню. В его пекарне продается N видов тортов. Каждый вид торта имеет три параметра: «красота», «вкус» и «популярность». I-й вид торта имеет красоту xi, вкус yi и популярность zi. Эти значения могут быть нулевыми или отрицательными.
Громозека решил, что купит М кусочков торта. Он выбирает набор следующим образом:
- Нельзя использовать два и более куска одного и того же вида торта.
- При указанном выше условии выбирается набор тортов, который максимизирует (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности).
Найдите максимально возможное значение (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности) для набора тортов, который выберет Громозека.

Входные данные
В первой строке через пробел записаны два целых числа N (1<=N<=1000) и M (0<=M<=N). В следующих N строках записано по  три целых числа xi, yi и zi (-10⁹<=xi, yi, zi <=10⁹, 1<=i<=N).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9	56	Подумайте о 2-м, 4-м и 5-м видах тортов. Общая красота, вкус и популярность будут следующими: Красота: 1 + 3 + 9 = 13 Вкус: 5 + 5 + 7 = 17 Популярность: 9 + 8 + 9 = 26 Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 13 + 17 + 26 = 56. Это максимальное значение.
2	5 3 1 -2 3 -4 5 -6 7 -8 -9 -10 11 -12 13 -14 15	54	Подумайте о том, чтобы иметь 1-й, 3-й и 5-й виды тортов. Общая красота, вкус и популярность будут следующими: Красота: 1 + 7 + 13 = 21 Вкус: (−2) + (- 8) + (- 14) = - 24 Популярность: 3 + (- 9) + 15 = 9 Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 21 + 24 + 9 = 54. Это максимальное значение.
3	10 5 10 -80 21 23 8 38 -94 28 11 -26 -2 18 -69 72 79 -26 -86 -54 -72 -50 59 21 65 -32 40 -94 87 -62 18 82	638	Если у нас есть 3-й, 4-й, 5-й, 7-й и 10-й виды тортов, общая красота, вкус и популярность будут -323, 66 и 249 соответственно. Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 323 + 66 + 249 = 638. Это максимальное значение.
4	3 2 2000000000 -9000000000 4000000000 7000000000 -5000000000 3000000000 6000000000 -1000000000 8000000000	30000000000	Значения красоты, вкуса и популярности тортов, а также значение, которое будет напечатано, могут не соответствовать 32-битным целым числам.

 

У вас есть таблица c N строками и M столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка - значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение K-го пути в этом отсортированном листе.

Входные данные
В первой строке задается два целых числа N - количество рядов и M - количество столбцов заданной таблицы (1 <= N, M <= 30). Каждая из следующих N строк содержит ровно M строчных букв английского алфавита. Последняя строка входного файла содержит целое число K (1 <= K <= 10¹⁸). Гарантируется, что для K ответ всегда существует.

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

Пояснения к примеру
abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk
 

Примеры

№	Входные данные	Выходные данные
1	3 4 abcd efdg hijk 4	abfdgk

Дана сетка с N + 1 рядами и M + 1 столбцами. Черепаха находится на клетке (0, 0) и хочет попасть в клетку (N, M). Черепаха может идти только вверх или вправо. На сетке в K клетках находятся ловушки. Если черепаха пойдет в одну из этих клеток, то она перевернется. У черепашки есть силы для того, чтобы встать не более чем T раз. Посчитайте, сколькими различными путями черепаха может попасть в клетку (N, M). Так как это число может быть очень большим, выведите остаток от его деления на Z.

Входные данные
В первой строке входного файла задается 5 целых чисел: N, M, K, T и Z (1 ≤ N,M ≤ 300000, 0 ≤ K, T  20, 1 ≤ Z ≤ 10⁹). В каждой из следующих K строк расположены координаты соответствующей клетки с ловушкой X, Y (0 ≤ X ≤ N, 0 ≤ Y ≤ M). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и (N, M) ловушек нет.

Выходные данные
Выведите требуемое число.

Примеры

№	Входные данные	Выходные данные
1	1 1 1 0 100 0 1	1
2	2 2 0 0 10	6

Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: Y [i₁, i₂, i₃, i₄] = min(X[j₁, j₂, j₃, j₄]), где 1 ≤ i_k ≤ N − M + 1, i_k ≤ j_k ≤ i_k + M − 1, а M -  заданное число.

Входные данные
В первой строке входного файла задаются N и M (1 ≤ M ≤ N). Остальные строки файла содержат элементы массива X. Количество элементов не будет превышать 1500000 и сами они будут целыми числами, не превышающими по абсолютному значению 10⁹. Они расположены в таком порядке, что считать их можно с помощью псевдокода:

for i = 1 to N:
for j = 1 to N:
for k = 1 to N:
for l = 1 to N:
read X[i, j, k, l]

Выходные данные
Выведите искомый массив Y в том же формате, в котором был дан массив X.
 

Примеры

№	Входные данные	Выходные данные
1	1 1 1	1
2	3 2 3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4 4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5 -1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3 -2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1 -5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2 -4 -3 1 3 1	-5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5