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. Наибольшая общая подпоследовательность ≡

Условие

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

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

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

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

Вывести наибольшую общую подпоследовательность. Если решений несколько, вывести любое.

Ограничения

Длина каждой строки не менее 1 и не превосходят 1000.

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

ababaca
acaba

aaba

Задача C. Канатная дорога ≡

Условие

Не так давно администрация столицы Флатландии приняла решение о строительстве канатной дороги. Этот транспорт подходит городу как нельзя лучше: столица построена на N холмах, каждый из которых при взгляде сбоку имеет вид параболы с направленными вниз ветвями. То есть i-й холм можно однозначно определить такими тремя числами A_i, B_i, C_i, что точка плоскости с координатами (x, y) находится внутри холма тогда и только тогда, когда A_i x² + B_i x + C_i ≥ y. Холмы могут пересекаться, но вершина холма никогда не находится внутри другого холма.

Канатная дорога представляет собой набор из K одинаковых столбов высоты H, через вершины которых последовательно (в порядке увеличения абсциссы) протянут канат. В целях повышения надежности пассажирских перевозок столбы должны устанавливаться только на вершинах холмов. На первом и N-м холмах обязательно должны быть установлены столбы. Отрезки каната не должны пересекаться или даже касаться холмов.

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

Рекомендуется рассмотреть частичные решения

• K = 2
• K = N

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

В первой строке входного файла находятся числа N K H, где N — количество холмов, K — число столбов и H — высота каждого из них (вещественное число). В каждой из следующих N строк содержится тройка вещественных чисел A_i B_i C_i, определяющая вид i-го холма. Холмы заданы в порядке увеличения абсциссы вершин.

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

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

Ограничения

2 ≤ N ≤ 300, 2 ≤ K ≤ N, 1 ≤ H ≤ 10⁶.

−10⁶ ≤ A_i < 0, −10⁶ ≤ B_i, C_i ≤ 10⁶.

Все вещественные числа во входном файле заданы не более чем с 5 знаками после десятичной точки.

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

3 3 1.5
-1 -5 0
-2 0 10
-1 4 0

10.831

3 2 1.5
-1 -5 0
-2 0 10
-1 4 0

-1