Задача A1. Количество инверсий последовательнсти

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Пара элементов (Ai, Aj) последовательности AN называется инверсией, если Ai > Aj и i < j.

Напишите программу, которая по заданной последовательности AN посчитает количество инверсий.

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

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

Последующие N целых чисел задают саму последовательность

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

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

Ограничения

2 ≤ N ≤ 105

0 ≤ Ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 1 2 5 9 13 16 20
0
2
9
1 1 2 3 8 6 1 9 9
5

Problem A2. Bucket sort (LETTERS ONLY)

Author:StdAlg   Time limit:3 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of words and sorts it in lexicographical order. Linear order on characters is given by ASCII codes.

Input file format

First line of input file contains integer N — the sequence length. Following N lines contain one word per line. Each word is exactly three letters long.

Output file format

Output file must consist of N lines, each containing one word from sorted sequence.

Constraints

0 ≤ N ≤ 1000000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
KVN
ACM
FSB
GGG
ACM
FSB
GGG
KVN

Задача A3. Результаты квалификации

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

Когда гонщик завершает очередной круг, в журнал записываются числа Bi и Ti — номер его машины и разность между временем, за которое он проехал этот круг, и текущим лучшим среди всех гонщиков временем. (Ti измеряется в тысячных долях секунды, T1 всегда равно 0). Если Ti < 0, то время, показанное этим гонщиком, становится лучшим.

Требуется определить результат квалификации по записям в журнале.

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

Входной файл содержит число N — общее количество кругов, сделанных всеми гонщиками в квалификации.

Далее содержатся N пар целых чисел Bi Ti — записи в журнале в хронологическом порядке.

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

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

Ограничения

1 ≤ N ≤ 105

Разница между лучшим и худшим временем не превышает 109 тысячных секунды

1 ≤ Bi ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6
7
+0
2
+123
5
-11
2
+7
1
+0
3
+60200
5 1 2 7 3

Problem A4. Вася и Суперкомпьютер

Author:Ю. Михалев   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Programmer Vasya decided to become a man, who solved most problems. To make his wish come true he invented a Supercomputer, which could do next tasks: generate a random problem (0) and solve a random problem (1) instead of Vasya (the problem may not be generated by the first task - Vasya already had an unlimited list of problems to solve).

Unfortunately, implementation features didn't allow to keep the Supercomputer on all day long: every day it could do limited number of tasks. Furthermore, every day the supercomputer must start with the task of the same type, which he ended previous day (first day could be started with any task).

So, Supercomputer worked several days and then broke down. In Supercomputer's log Vasya found that all records are shuffled and there are extra records, which don't belong to this log. You should help Vasya to count maximum count of completed tasks that Supercomputer could do before crash.

Input format

The first line of the input file contains one number N - number of records in the log

Following N lines contains number Mi - number of tasks, completed in some day, and a string Si of Mi characters 0 and 1 - description of tasks, completed in that day.

Log records are not chronologically ordered. Some records could be excess.

Output format

The output file must contain one number - maximum number of tasks, which Supercomputer could do before the crash.

Constraints

Total length of all Si does not exceed 5 ⋅ 105

Sample tests

No. Standard input Standard output
1
6
4 1111
3 100
5 00101
2 00
10 1001010110
2 01
26
2
6
3 100
5 10100
2 11
6 011101
3 110
2 10
16

Задача B1. Сочетания

Автор:std.alg   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Сочетанием из n элементов по k называется возрастающая последовательность из k чисел из диапазона от 1 до n. Во входном файле заданы числа n и k. Выведите в выходной файл все сочетания по k из чисел от 1 до n в лексикографическом порядке. 1 ≤ k ≤ n ≤ 16.

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

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

Ограничения

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

Стандартный вход Стандартный выход
1
4 2
1 2
1 3
1 4
2 3
2 4
3 4

Задача B2. Разбиения на слагаемые

Автор:std.alg   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Перечислите все разбиения целого положительного числа N (1 ≤ N ≤ 40) на целые положительные слагаемые. Разбиения должны обладать следующими свойствами: 1. Слагаемые в разбиениях идут в невозрастающем порядке. 2. Разбиения перечисляются в лексикографическом порядке.

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

Первая строка входного файла содержит целое число N (1 ≤ N ≤ 40).

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

Ограничения

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

Стандартный вход Стандартный выход
1
4
1 1 1 1
2 1 1
2 2
3 1
4

Задача B3. Ответы к тесту

Автор:А. Жуплев, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Крокодил Гена решил поступить в университет. Для поступления ему нужно пройти тест, состоящий из Q вопросов. На каждый из них можно ответить либо "Да", либо "Нет". Количество баллов, получаемых абитуриентом за тест, равно количеству данных им правильных ответов. Все абитуриенты проходят тест с одними и теми же вопросами.

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

По этим данным Гена должен определить правильные ответы.

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

В первой строке входного файла содержатся числа P Q. Далее следует P описаний шушанчиков, по две строки на описание:

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

В выходном файле должна содержаться единственная строка, состоящая из Q символов + (ASCII 43) или - (ASCII 45) — правильные ответы к тесту. Если существует несколько вариантов правильных ответов, вывести любой из них. Так, во втором примере допустим также ответ -+++.

Ограничения

1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15

Исходные данные таковы, что существует хотя бы один вариант решения.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 2
+-
0
-+
2
3 4
--++
3
----
1
---+
2
+-++

Задача B4. Длинное взятие

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

На шашечной доске размером N × N клеток расположены несколько белых и несколько черных шашек. Горизонтали доски обозначены числами 1, 2, 3, … снизу вверх. (То есть первая строка входных данных описывает горизонталь доски с номером N, вторая N − 1 и т.д.) Вертикали обозначены буквами a, b, c, … слева направо. Клетка, таким образом, задается комбинацией из буквы и числа, например d12. Ход шашки задается перечислением всех клеток, которые она посетила за этот ход, включая начальную и конечную. Обозначения клеток при этом разделяются знаком - (минус). Например: a1-c3-e1.

Шашка может побить (взять) шашку противоположного цвета, "перепрыгнув" через нее по диагонали в любом направлении. Если после этого имеется возможность взять еще одну шашку, то это можно сделать на том же ходу.

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

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

В первой строке входного файла содержится число N. В следующих N строках — описание позиции, состоящее из символов '.' (точка), 'O' (заглавная латинская О),'X' (заглавная латинская X). Они определяют пустую клетку, белую шашку и черную шашку соответственно.

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

В выходном файле должна содержаться единственная строка вида L1 N1 − L2 N2 − … − LK NK, где K ≥ 1, или Impossible если взятие невозможно.

Ограничения

1 ≤ N ≤ 12

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
.....
.O.O.
....X
.O.O.
X....  
e3-c1-a3-c5-e3  
2
4
X...
....
....
...O  
Impossible

Задача C. Ближайшее число

Автор:Известная   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 106

|ai| ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
2 3 4 4
2
1
1
1

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

Автор:Известная   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

|ai| ≤ 109

0 ≤ m ≤ 2 n − 2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
-3 -2 -1 0
6
RRRLLL
-2 -1 0 0 0 0
2
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

Задача C1. Чемпионат по боксу

Автор:И. Блинов   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В чемпионате по боксу соревнуется две команды по N боксёров в каждой. Все боксёры разбиты на M весовых категорий. Каждый боксёр характеризуется уровнем мастерства pi (при этом не существует двух боксёров с равным уровнем мастерства) и номером весовой категории в которой он выступает ci. Чемпиона проходит по следующим правилам: все участники разбиваются по весовым категориям и в рамках одной весовой категории каждый боксёр одной команды выходит на ринг против каждого боксёра другой команды, за победу в бое начисляется одно очко. Боксёр точно победит если его уровень мастерства выше уровня мастерства соперника.

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

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

Первая строка входного файла содержит два целых числа N, M. Далее N пар чисел pi, сi  — описание боксёров из команды Пахома. Далее N пар чисел pi, сi  — описание команды соперников.

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

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

Ограничения

1 ≤ N ≤ 106, 1 ≤ M ≤ 300, 1 ≤ сi ≤ M; 1 ≤ pi ≤ 109.

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения
NM
1201 ≤ N ≤ 201 ≤ M ≤ 2
2201 ≤ N ≤ 10001 ≤ M ≤ 2
3201 ≤ N ≤ 1061 ≤ M ≤ 2
4201 ≤ N ≤ 1061 ≤ M ≤ 50
5201 ≤ N ≤ 1061 ≤ M ≤ 300

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
1 1
2 1 
3 1
4 1
5 1
6 1
-9
2
4 2
60 1
100 2
110 2
120 2
200 1
50 2
40 2
30 2
12
3
3 3
5 1
10 2
15 3
6 1
11 2
16 3
-1

Задача C2. Сумма не без разнообразия

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Задана последовательность целых чисел A1, A2, …, AN. Необходимо выбрать из нее подпоследовательность из подряд стоящих чисел Ai, Ai + 1, …, Aj так, чтобы она содержала не менее K различных чисел, и сумма S = Ai + Ai + 1 + …  + Aj была максимальной.

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

Первая строка ввода содержит целые числа N и K (1 ≤ K ≤ N ≤ 200 000). Вторая строка содержит N целых чисел A1, A2, …, AN (Ai≤ 1 000 000 000).

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

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

Ограничения

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 3
-99 1 2 -100 3 2 3
-89
2 7
2
3 2
1 1 1
IMPOSSIBLE

Задача D1. Сбалансированное дерево revisited

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

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

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

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

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

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 106, сами числа — в диапазоне от  − 231 до 231 − 1.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 1 3 0
1 2 3
2
5 -1 6 -5 5 0
5 6

Задача D2. Сбалансированное дерево

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

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

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

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

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 106, сами числа — в диапазоне от  − 231 до 231 − 1.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 1 3 0
1 2 3
2
5 -1 6 -5 5 0
5 6

Задача E1. Гвоздики

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

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

В первой строке входного файла записано число N — количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел  — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10 000).

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

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

Ограничения

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
4 10 0 12 2
6

Задача E2. Почтовый индекс

Автор:Антон Карабанов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  

Условие

У Тимофея скоро День рождения! В связи с этим эпохальным событием, он собирается сделать рассылку писем-приглашений. К сожалению, отправить почтовый конверт не так просто, как электронное письмо, необходимо знать точный домашний адрес, а самое главное — почтовый индекс адресата.

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

Линии, образующие стороны квадрата, Тимофей называет прямыми, а диагонали квадрата - наклонными. Например, в цифре 9 четыре прямых и одна наклонная линия.

Сегодня Тимофей должен написать письмо-приглашение своему другу, с которым он познакомился в международном лагере юных программистов, да вот беда - Тимофей совсем забыл его почтовый индекс. Все, что он помнит, так это количество прямых и наклонных линий в его индексе, и то, что он является наименьшим натуральным числом из всех подходящих. Помогите Тимофею! Учтите, что длина индекса в других странах может быть произвольной (а не 6, как в России), а также то, что никакой индекс не может начинаться с нуля.

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

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

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

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

Ограничения

0 ≤ a ≤ 103

0 ≤ b ≤ 102

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

Стандартный вход Стандартный выход
1
10 1
28
2
5 4
Wrong
3
23 5
100236

Задача E3. Унисон

Автор:А. Щуров   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Два друга-ирландца Фаолан и Леон очень любят петь, особенно в праздники, когда они могут собраться и петь песни вместе. Хоть они и друзья, у них не так много общих песен, но это не мешает им пытаться петь разные песни одновременно.

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

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

Когда Фаолан и Леон поют, они следуют по текстам своих песен слева направо, сверху вниз, с удовольствием распевая в унисон совместимые строки и пропуская все остальные.

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

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

В первой строке входных данных содержатся целые числа N M: количество строк в первой и второй песне соответственно. Далее следуют N + M строк, содержащих текст первой и затем второй песни. Каждая строка может состоять только из печатных ASCII символов.

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

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

Ограничения

1 ≤ N, M ≤ 106

N * M ≤ 107

Длина каждой строки не превосходит 50.

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения
NM
120N = 11 ≤ M ≤ 104
1301 ≤ N ≤ 101 ≤ M ≤ 10
1501 ≤ N ≤ 1061 ≤ M ≤ 106

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

Стандартный вход Стандартный выход
1
3 4
It's funny how the war goes on
Without John, without our John
La la la la la, la la!
We're so young and so gone
Let's chase the dragon from our home
Ah ah from our home!
From our home
17

Задача E4. Наибольшая возрастающая подпоследовательность

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Дана последовательность из N целых чисел. Найдите любую из ее наибольших строго возрастающих подпоследовательностей.

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

Во входном файле находится число N, а за ним следует последовательность ai из N целых чисел.

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

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

Ограничения

1 ≤ N ≤ 100000;  − 109 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
123 456 124 124 125
3
1 4 5

Задача F1. Бутылка на всех

Автор:А. Шавлюгин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

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

Входной файл содержит целые числа N M, за которыми следуют N чисел ai — жажда i-го ученика.

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

Выходной файл должен содержать одно число —– минимально возможную суммарную жажду.

Ограничения

1 ≤ N, M ≤ 105

0 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
9 30
0
2
4 3
0 101 5 12
7

Задача F2. Эффективное чтение

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

С тех пор как Петя поступил на филфак, его жизнь круто изменилась. Оказалось, что нужно много читать для того, чтобы успевать по всем предметам. Петя читает книги только из университетской библиотеки. Поскольку Петя — не единственный студент в университете, он не может взять все нужные ему книги в начале семестра и сдать в конце. Для каждой книги определена дата, в которую Петя должен её взять и дата, в которую Петя должен её вернуть.

Более формально, занумеруем дни учебного семестра начиная с 1. Пете для учебы необходимо N книг. Занумеруем их числами от 1 до N. Для книги с номером i известны три числа:

Будем считать, что Петя приходит в библиотеку утром, забирая и отдавая необходимые книги. Таким образом, взяв книгу в день с номером Li, он может в тот же день начать её читать. Вместе с этим, если книгу необходимо отдать в день с номером Ri, то Петя должен успеть дочитать её в день с номером Ri − 1.

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

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

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

N = 1;

N ≤ 103;

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

Входной файл содержит целое число N, за которым следует N троек целых чисел Li Ri pi.

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

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

Ограничения

1 ≤ N ≤ 105;

1 ≤ Li < Ri ≤ 105;

1 ≤ pi ≤ 105;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 4 60
2 3 50
50

Problem F3. Carriage inspectors

Author:M. Sporyshev, I. Tuphanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Programmer Vasya commutes to work by train every day. Vasya came to the train station today as usual, but forgot his wallet! There is no time to get back. Vasya decided to take the train without buying a ticket. Obviously, he wouldn't be happy to meet an inspector now.

The train consists of N carriages served by M inspectors. Luckily, Vasya always takes this train and knows Ai — numbers of carriages where inspectors are located at the moment he enters the train. He also knows the direction (toward the first or toward the last carriage) of each inspector and his (or her) speed Vi — the number of carriages that the inspector passes per hour. Thus every 1 / Vi hours the inspector moves to the next carriage in his (or her) direction. The inspector stops if there is no next carriage in that direction.

The trip to work is long, so Vasya wants to pick a carriage where he could stay as long as possible until the moment when an inspector shows up in his carriage. Help Vasya with this.

Input file format

First string of the input contains integers N and M — the number of carriages and the number of inspectors accordingly.

Then M lines follow, i-th line contains integers Ai, Vi — carriage number where the inspector i is located when Vasya gets on the train, and his (or her) speed. Vi is negative if the inspector is moving toward the first carriage, and positive otherwise.

Output file format

Output the number of carriage which Vasya should get in to. Carriages are numbered from 1. If there are multiple solutions, output any of them.

Constraints

1 ≤ N, M ≤ 200000

1 ≤ Ai ≤ N

 − 106 ≤ Vi ≤ 106, Vi ≠ 0

Note on samples

In the first sample input Vasya can stay in the carriage number 1 as long as he wants.

In the seconds sample input there are inspectors in carriages 1 and 5 at time 0. After 0.5 hours inspector 1 enters carriage 4. After 1 hour from the beginning of the ride, inspector 1 enters carriage 2, while inspector 2 enters carriage 3. Thus, both 2 and 3 are correct answers.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 1
2 1
1
2
5 2
5 -2
1 1
2

Задача G1. Конвертер графов

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

Первая строка входного файла содержит два слова. Первое — название формата графа во входном файле. Второе — название формата, в котором граф необходимо вывести.

Начиная со второй строки в файле содержится описание графа в одном из следующих форматов

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

Выходной файл должен содержать описание графа в требуемом формате.

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ N2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
edges mat
3 4
1 2
2 3
1 3
2 2
3
0 1 1
0 1 1
0 0 0
2
mat lists
4
1 0 1 1
0 0 0 0
1 1 0 0
0 1 1 0
4
3 1 3 4
0
2 1 2
2 2 3

Задача G2. Расстояние от корня

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

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

В первой строке задано n "--- количество вершин в дереве. В следующих n − 1 строках заданы вершины, являющиеся предками вершин 2, 3, , n. Вершина 1 является корнем дерева.

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

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

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

В третьей строке выведите номера этих вершин через пробел в порядке возрастания.

Ограничения

1 ≤ n ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1
1
1
2
2 3
2
3
1
2
2
1
3

Задача G3. КПК

Автор:И. Олейников, Т. Чистяков   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Хакер Вася решил собрать карманный персональный компьютер (КПК). Согласно найденной им в Интернет инструкции компьютер собран правильно тогда, когда ток из каждой микросхемы может пройти в каждую и притом единственным путем.

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

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

Входной файл содержит числа N и M — соответственно число микросхем и проводов в КПК, за которыми следуют M пар чисел ai aj, означающие, что i-ая и j-ая микросхемы соединены проводом. Ток по проводу может течь в любом направлении.

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

Выходной файл содержит сначала число K1 — количество проводов, которые нужно оставить в схеме, затем K1 пар чисел ai aj — описание проводов. После этого следует число K2 — число проводов, которые нужно добавить в схему, затем K2 пар чисел ai aj — описание проводов. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 3
1
2 3
1
1 2

Задача G4. Дерево

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

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

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа ui и vi через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

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

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 105

0 ≤ m ≤ 105

1 ≤ ui, vi ≤ n

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2
1 3
YES
2
3 3
1 2
2 3
3 1
NO

Задача G5. Производство деталей

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:details.in   Ограничение памяти:256 Мб
Выходной файл:details.out  

Условие

Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

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

Система оценивания

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

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

Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p1, p2… pn, определяющих время изготовления каждой детали в секундах.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера.

Известно, что не существует циклических зависимостей в производстве деталей.

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

В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Ограничения

1 ≤ n ≤ 100000, 1 ≤ pi ≤ 109

Сумма всех чисел ki не превосходит 200000.

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

Входной файл (details.in) Выходной файл (details.out)
1
3
100 200 300
1 2
0
2 2 1
300 2
2 1
2
2
2 3
1 2
0
5 2
2 1
3
4
2 3 4 5
2 3 2
1 3
0
2 1 3
9 3
3 2 1

Problem G6. Eulerian cycle

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

You are to write a program that receives an undirected connected graph and finds its Eulerian cycle.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of following M lines contains a pair of vertex numbers, connected by some edge. There is at most one edge connecting two vertices.

Output file format

Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle. If there does not exist any Eiler cycle, output file must contain  − 1.

Constraints

1 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2
2 3
3 1
1 2 3 1

Problem G7. Biconnectivity

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

You are to write a program that receives a connected undirected graph and finds all its articulation points, which are the vertices that, if removed, leave disconnected graph.

Input file format

Input file contains two integers N and M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain pair of integers — numbers of vertices connected by an edge. There are no pairs of equal numbers.

Output file format

Output file must contain integer representing a quantity of articulation points, followed by numbers of corresponding vertices in arbitrary order.

Constraints

1 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 6
1 2
1 3
2 3
1 4
1 5
4 5
1 1

Problem G8. SST for sparse graph

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

Задача G91. Разрезание графа

Входной файл:cutting.in   Ограничение времени:2 сек
Выходной файл:cutting.out   Ограничение памяти:256 Мб

Условие

Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:

Известно, что после выполнения всех операций типа cut рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.

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

Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа n, количество рёбер m и количество операций k (1 ⩽ n ⩽ 50 000, 0 ⩽ m ⩽ 100 000, m ⩽ k ⩽ 150 000).

Следующие m строк задают рёбра графа; i-ая из этих строк содержит два числа ui и vi (1 ⩽ ui,  vi ⩽ n), разделённые пробелами — номера концов i-го ребра. Вершины нумеруются с единицы; граф не содержит петель и кратных рёбер.

Далее следуют k строк, описывающих операции. Операция типа cut задаётся строкой «cut ~u v» (1 ⩽ u,  v ⩽ n), которая означает, что из графа удаляют ребро между вершинами u и v. Операция типа ask задаётся строкой «ask u v» (1 ⩽ u,  v ⩽ n), которая означает, что необходимо узнать, лежат ли в данный момент вершины u и v в одной компоненте связности. Гарантируется, что каждое ребро графа встретится в операциях типа cut ровно один раз.

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

Для каждой операции ask во входном файле выведите на отдельной строке слово «YES», если две указанные вершины лежат в одной компоненте связности, и «NO» в противном случае. Порядок ответов должен соответствовать порядку операций ask во входном файле.

Ограничения

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

Входной файл (cutting.in) Выходной файл (cutting.out)
1
3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1
YES
YES
NO
NO

Problem G92. Fast Dijkstra

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted directed graph and finds all distances from fixed vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its arcs.

Input file format

Input file contains two integers N, M and S. Vertices are numbered with integer numbers from 1 to N. S is the number of source vertex. M is the number of arcs. Each of next M lines contain three integers — numbers of starting and ending vertices of some arc and its weight respectively. All weights are positive. There is at most one arc connecting two vertices in every direction.

Output file format

Output file must contain N numbers. Each I-th number is the distance from vertex S to vertex I. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Problem G93. Ford-Bellman

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3 1
1 2 5
1 3 10
2 3 2
0 5 7

Problem G94. Floyd-Warshall

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances between all pairs of vertices in a directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N and M, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a matrix of size NxN. Element in the j-th column of i-th row mush be the shortest distance between vertices i and j. The distance from the vertex to itself is considered to be 0. If some vertex is not reachable from some other, there must be empty space in corresponding cell of matrix.

Constraints

0 ≤ N ≤ 100. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 5
1 3 10
2 3 2
0 5 7
  0 2
    0

Задача S1. Префикс-функция

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Дана строка s. Найдите сумму значений префикс-функции для всех позиций строки s.

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

Во входном файле записана единственная строка s.

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

В выходной файл выведите одно число — ответ на задачу.

Ограничения

1 ≤ |s| ≤ 150000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abcaabacabc
11

Problem S2. Knuth-Morris-Pratt

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of small latin letters from 'a' to 'z' and empty spaces.

Output file format

Output file must contain single integer number — position of the most left occurence of the substring in a string, or −1 if there is no one.

Constraints

Length of both strings is less than 100000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16

Задача S3. Нормальная палиндромика

Автор:Жюри летних сборов, И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Палиндром — это строка, которая одинаково читается и в прямом, и в обратном порядке. Например, kazak — палиндром, а kazachka — нет. По данной строке S требуется найти такую кратчайшую (возможно, пустую) строку P, что строка S + P будет палиндромом.

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

Во входном файле содержится строка S, состоящая из маленьких латинских букв.

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

В выходной файл необходимо вывести строку P.

Ограничения

Длина исходной строки не превосходит 300000 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abcc
ba
2
abcd
cba

Задача S4. Сравнения подстрок

Автор:std.alg   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Дана строка. Нужно уметь отвечать на запросы вида: равны ли подстроки [a..b] и [c..d].

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

Сперва строка S (не более 105 строчных латинских букв). Далее число M — количество запросов.

В следующих M строках запросы a,b,c,d. 0 ≤ M ≤ 105, 1 ≤ a ≤ b ≤ |S|, 1 ≤ c ≤ d ≤ |S|

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

M строк. Выведите Yes, если подстроки совпадают, и No иначе.

Ограничения

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

Стандартный вход Стандартный выход
1
trololo
3
1 7 1 7
3 5 5 7
1 1 1 5
Yes
Yes
No

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

Автор:std.alg   Ограничение времени:2 сек
Входной файл:common.in   Ограничение памяти:256 Мб
Выходной файл:common.out  

Условие

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

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

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

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

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

Ограничения

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

Входной файл (common.in) Выходной файл (common.out)
1
ababb
abacabba
aba

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

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 19, aij ≤ 108

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
-1 1 6
3 -1 7
4 9 -1
5
2
4
-1 1 1 1
1 -1 1 1
1 1 -1 1
1 1 1 -1
3

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

Author:-   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

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

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

Input file format

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

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

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

Для запросов второго типа далее в строке содержатся целые числа x1, y1, z1, x1, y1, z1 — координаты параллелепиппеда, для которого следет предоставить ответ на запрос.

Output file format

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

Constraints

1 ≤ n ≤ 100000;

1 ≤ x, y, z, x1, y1, z1, x2, y2, z2 ≤ 100;

0 ≤ 232 − 1;

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
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


Задача Z3. Размещение данных

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:data.in   Ограничение памяти:256 Мб
Выходной файл:data.out  

Условие

Телекоммуникационная сеть крупной IT-компании содержит n серверов, пронумерованных от 1 до n. Некоторые пары серверов соединены двусторонними каналами связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.

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

На рис. 1 показан пример сети и отказоустойчивого множества из серверов с номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При недоступности канала между серверами 1 и 2  — с сервера 4, при недоступности канала между серверами 2 и 3  — с сервера 1. На серверы 3 и 5 при недоступности любого канала связи можно по другим каналам передать данные с сервера 4.

Рис. 1. Пример сети и отказоустойчивого множества серверов.

В рамках проекта группе разработчиков компании необходимо разместить свои данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики хотят продублировать свои данные, разместив их одновременно на нескольких серверах, образующих отказоустойчивое множество. Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов выбора такого множества, и поскольку это количество способов может быть большим, необходимо найти остаток от деления этого количества способов на число 109 + 7.

Требуется написать программу, которая по заданному описанию сети определяет следующие числа: k  — минимальное количество серверов в отказоустойчивом множестве серверов, c  — остаток от деления количества способов выбора отказоустойчивого множества из k серверов на число 109 + 7

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

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

Следующие m строк содержат по два целых числа и описывают каналы связи между серверами. Каждый канал связи задается двумя целыми числами: номерами серверов, которые он соединяет.

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

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

Выведите два целых числа, разделенных пробелом: k  — минимальное число серверов в отказоустойчивом множестве серверов, c  — количество способов выбора отказоустойчивого множества из k серверов, взятое по модулю 109 + 7

Ограничения

2 ≤ n ≤ 200000, 1 ≤ m ≤ 200000

Система оценки и описание подзадач

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
nm
1252 ≤ n ≤ 101 ≤ m ≤ 45
2272 ≤ n ≤ 200000m = n − 1
3282 ≤ n ≤ 10001 ≤ m ≤ 50001
4212 ≤ n ≤ 2000001 ≤ m ≤ 2000001, 2, 3

Описание подзадач и системы оценивания

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

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

В приведённом примере отказоустойчивыми являются следующие множества из двух серверов: {1, 3}, {1, 4}, {1, 5}.

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

Входной файл (data.in) Выходной файл (data.out)
1
5 5
1 2
2 3
3 4
3 5
4 5
2 3

Problem Z4. Etintrof

Author:A. Klenin, I. Blinov   Time limit:3 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Young programmer Vasya created a two-dimensional game in Battle Royale genre. The game is played on a square field of N by N cells. Each cell is either empty (represented by '.') or occupied by wall (represented by '#').

The player is located in one of the empty cells. Every second the player can stay in place or move to an adjacent empty cell up, down, left or right. After player moves, all cells along the perimeter of the game field are removed (so field size is reduced by 2 along each axis). If the player was located on one of the removed cells, he dies.

Your program must, for each empty cell of the field, calculate maximum number of seconds the player can survive if he starts the game from that cell and plays optimally.

Input format

The first line of input contains a single integer N. The next N lines contain one string of N characters each — representation of the game field.

Output format

The output should contain N lines of N numbers, where the j-th number in the i-th line indicates the maximum survival time of a player when starting from a cell with coordinates (i, j). If the corresponding cell is not empty, output zero.

Constraints

1 ≤ N ≤ 500

Sample tests

No. Standard input Standard output
1
5
.....
.....
.....
.....
.....
1 2 3 2 1 
2 3 3 3 2 
3 3 3 3 3 
2 3 3 3 2 
1 2 3 2 1 
2
5
.....
.#.#.
.....
.#.#.
.....
1 1 3 1 1 
1 0 3 0 1 
3 3 3 3 3 
1 0 3 0 1 
1 1 3 1 1 

2.324s 0.017s 99