A. Звездные треугольники. Формат входных данных. Формат выходных данных. Примеры. B. Гипер-минимум. Формат входных данных. Формат выходных данных. Примеры. C. Энергичная черепаха

A. Звездные треугольники

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

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

В первой строке задается N – количество звезд на небе (3 ≤ N ≤ 300000). В каждой из следующих N строк заданы целые X, Y (|X, Y | ≤ 10⁹) _ координаты соответствующей звезды.

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

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

Примеры

triangles. in	triangles. out
0 0 1 0 0 1
0 0 1 0 0 1 1 1

По этой задаче будет полное отображение результатов.

В 30% тестов N ≤ 100.

B. Гипер-минимум

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

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

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

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

Выведите искомый массив Y.

Примеры

hyper. in	hyper. out
10 3 1 2 30 4 5 10 7 8 9 6	1 2 4 4 5 7 7 6

C. Энергичная черепаха

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