Problem A. Трёхмерное суммирование ≡

Statement

Имеется трёхмерный массив чисел. Поступают запросы двух видов. Запрос первого вида заменяет значение в заданной ячейке на заданную величину. Запрос второго вида требует вычисления суммы значений в ячеках заданного параллелепиппеда.

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

Input file format

В первой строке входного файла находится целое число n — общее количество запросов.

Далее следует n строк, содержащих запросы. В начале каждой строки находится число 1 или 2 — тип запроса.

Для запросов первого типа далее в строке содержатся целые числа x, y, z, value — координаты ячейки и новое значение в ней.

Для запросов второго типа далее в строке содержатся целые числа x₁, y₁, z₁, x₁, y₁, z₁ — координаты параллелепиппеда, для которого следет предоставить ответ на запрос.

Output file format

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

Constraints

1 ≤ n ≤ 100000;

1 ≤ x, y, z, x₁, y₁, z₁, x₂, y₂, z₂ ≤ 100;

0 ≤ 2³² − 1;

Sample tests

4
1 1 2 1 10
2 1 1 1 1 1 1
2 1 1 1 2 2 2
2 1 1 2 2 2 2

0
10
0

Задача B. Наибольшая общая подстрока ≡

Условие

Найдите наибольшую общую подстроку строк s и t.

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

Первая строка входного файла содержит строку s, вторая — t (1 ≤ |s|, |t| ≤ 100,000). Строки состоят из строчных латинских букв.

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

Выведите одну строку — наибольшую общую подстроку строк s и t. В случае, если ответ не единственный, выведите минимальный лексикографически.

Ограничения

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

ababb
abacabba

aba

Задача C. Коммивояжёр возвращается! ≡

Условие

Коммивояжёр возвращается в систему Альфы Центавра! Население системы с нетерпением ждёт его прибытия — каждый хочет приобрести что-нибудь с далёких планет!

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

Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!

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

В системе Альфы Центавра n планет. Это число записано в первой строке входного файла. Следующие n строк содержат по n чисел каждая: j-ое число на i-ой из этих строк — стоимость перемещения a_ij от i-ой планеты до j-ой. Числа в каждой строке разделены пробелами. a_ij = -1 означает, что из планеты i нельзя на прямую добраться до планеты j.

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

Выходной файл должен содержать единственное целое число — длину оптимального пути. Если не существует пути проходящего через все планеты, вывести -1.

Ограничения

1 ≤ n ≤ 19, a_ij ≤ 10⁸

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

3
-1 1 6
3 -1 7
4 9 -1

5

4
-1 1 1 1
1 -1 1 1
1 1 -1 1
1 1 1 -1

3

Задача D. Финишные позиции ≡

Условие

На одном из этапов марсианских гонок по кольцевому треку вышла из строя программа, рассчитывающая финишные позиции гонщиков. На трассе имеется специальное оборудование, формирующее хронику гонки — список машин, пересекающих финишную черту. То есть, когда машина заканчивает очередной круг, пересекая финишную черту, её номер добавляется в список. Например, если список имеет вид 47874874, то это означает, что первый круг закончили машины с номерами 478 в указанном порядке, на втором круге машина 7 обогнала машину 4, а на третий круг закончили только машины 74, а машина 8 либо сломалась, либо всё ещё находится на втором круге.

Требуется написать программу, которая по заданному списку машин определит их финишные позиции.

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

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

Во входном файле содержится число N — количество элементов списка.

Далее следуют N чисел, задающие список.

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

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

Ограничения

1 ≤ N ≤ 10⁶

Номера машин являются целыми неотрицательными числами, не превосходящими 10⁹

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

3
5 1 10

5 1 10

8
4 7 8 7 4 8 7 4

7 4 8

16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222

17 39 88 222222222