Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой.

Она организована как подвешенное за вершину 0 дерево из \(n\) (\(1 \le n \le 20000\)) вершин, каждая из которых требует цифру от \(0\) до \(9\). Вершины пронумерованы от \(0\) до \(n - 1\).

Единственная информация, которой владеют коровы – что определённые последовательности длины \(5\) не появляютя на путях в этом дереве начиная с каких-то стартовых позиций при движении вверх по дереву.

По заданным \(m\) (\(0 \le m \le 50000\)) последовательностям длины \(5\), вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет не подходить.

Вы должны выводить свой ответ по модулю \(1234567\).

Мислав и Мирко разработали новую игру под названием повороты.

Сначала Мирко выбирает последовательность чисел длины \(n\) и число \(k\) и разбивает последовательность на секции, каждая из которых содержит \(k\) чисел (\(n\) делится на \(k\)). Первая секция содержит первые \(k\) позиций в последовательности, вторая секция содержит последующие \(k\) позиций в последовательности и так далее.

После этого Мирко начинает применять различные операции на данной последовательности. Есть два типа операций:

1. Совершить циклический сдвиг элементов последовательности чисел в каждой секции на \(x\) влево или вправо.

2. Совершить циклический сдвиг элементов последовательности чисел целиком на \(x\) влево или вправо.

Заметим, что операция типа 2 может изменить то, к какой секции принадлежит какое число.

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

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

Поздравляем! Вас наняли управляющим одного крупного завода по производству чего-то очень важного. На вашем заводе есть \(n\) рабочих и \(n\) станков. Каждый рабочий умеет работать на каких-то станках, а на каких-то не умеет. К счастью, вы можете отправить какого-то рабочего на курсы повышения квалификации, чтобы он научился работать на каком-то станке, заплатив за это 1 тугрик. Нет никаких ограничений по тому, кого и сколько раз отправлять на курсы. У ваших работников также очень хорошая память, поэтому если они умели или научились работать на каком-то станке, то уже никогда не забудут, как это делать.

Но не все так радужно. Из-за кризиса сократили всех других менеджеров, поэтому рабочие сами определяют, за каким станком им работать в определенный день. Рабочие могут прийти на работу в случайном порядке. Когда рабочий пришел на работу он может выбрать любой еще не занятый станок, на котором умеет работать, и сядет за него. Если же такого не нашлось, то он расстроится и уйдет домой, а ваш завод понесет убытки. Так, если у вас было два рабочих, первый из которых умел работать на 1 и 2 станке, а второй только на первом, то если первый пришел на работу раньше и занял первый станок, то ваш завод понесет убытки.

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

Будем считать, что карта Адриатического моря представляет собой сетку, состоящую из единичных квадратиков, организованных в \(2500\) рядов и \(2500\) столбцов. Ряды пронумерованы от \(1\) до \(2500\) с севера на юг, столбцы пронумерованы от \(1\) до \(2500\) с запада на восток. В море есть N островов, пронумерованных от 1 до N и каждый остров находится внутри некоторого единичного квадрата сетки. Позиция острова K задана его координатами — рядом \(R_k\) и столбцом \(C_k\). Никакие два острова не находятся в одном квадрате.

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

Точнее, можно переплыть с острова \(A\) на остров \(B\) за один шах, если или \(R_A \lt R_B\) и \(C_A \lt C_B\), или \(R_A \gt R_B\) и \(C_A \gt C_B\). При этом расстояние между островами или наличие островов по дороге не влияет на возможность доплыть с одного острова на другой. Если нельзя доплыть с одного острова на другой напрямую, иногда можно доплыть с использованием промежуточных островов более чем за один шаг. Определим как расстояние между островами величину, равную числу шагов, необходимых, чтобы переплыть с одного острова на другой.

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