Взаимодействие сотрудников в некоторой компании организовано в виде иерархической структуры. Всего в компании работают \(n\) сотрудников. Каждому сотруднику присвоен уникальный номер от 1 до \(n\), директору присвоен номер 1. У каждого сотрудника, кроме директора, есть ровно один непосредственный начальник. Непосредственный начальник сотрудника \(i\) имеет номер \(p_i\) , причем \(p_i \lt i\).

Сотрудник \(x\) является подчиненным уровня 1 сотрудника \(y\), если \(p_x = y\). Для \(k \gt 1\) сотрудник \(x\) является подчиненным уровня \(k\) сотрудника \(y\), если сотрудник \(p_x\) является подчиненным уровня \(k – 1\) сотрудника y.

У директора компании появилась возможность направить некоторых сотрудников на курсы повышения квалификации. Для этого он решил выбрать два числа \(L\) и \(R\) и направить на курсы всех сотрудников с номерами \(i\), такими что \(L \le i \le R\).

Перед тем, как выбрать числа \(L\) и \(R\), директор получил \(m\) пожеланий от сотрудников компании, \(j\)-е пожелание задается двумя числами \(u_j\) и \(k_j\) и означает, что сотрудник \(u_j\) просит отправить на курсы одного из своих подчиненных уровня \(k_j\) . Для экономии средств директор хочет выбрать такие \(L\) и \(R\), чтобы количество сотрудников, направленных на повышение квалификации, было минимальным возможным, но при этом все пожелания были выполнены.

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

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

В столице города Бестеланд есть огороженный парк, площадь которого представляет собой прямоугольник. Деревья и посетители в парке представляют собой круги. В парке есть четыре входа, по одному в каждом углу (1 = внизу слева, 2 = внизу справа, 3 = верхний правый, 4 = верхний левый). Посетители могут войти и выйти из парка только через входы. Посетители могут войти и выйти из парка, когда они касаются обеих сторон угла соответствующего входа. Посетители могут свободно передвигаться по парку, но они не могут пересекаться ни с деревьями, ни с забором. Ваша задача для каждого посетителя, учитывая вход, через который он войдет в парк, рассчитать через какие входы он может выйти из парка.

Сетка размера (2 n + 1) * (2 n + 1) была построена следующим образом. Номер 1 был помещен в центральный квадрат, номер 2 был помещен справа от него, а следующие числа были помещены вдоль спирали против часовой стрелки.

Ваша задача - рассчитать ответы на q запросов, где запрашивается сумма чисел в прямоугольной области в сетке (по модулю 10 ⁹ + 7 ). Например, в следующей сетке n = 2 а сумма чисел в серой области 74 :

Есть n городов в Байтландии, и k из них важные города, часто посещаемые королем. В стране есть m дорог, каждая из которых соединяет два города. К сожалению, состояние дорог настолько плохо, что король не может проехать через них с полной скоростью на своих спортивных автомобилях. Для каждой дороги известны затраты на ее обновление. Ваша задача - выбрать, какие дороги будут отремонтированы, чтобы все k важных города были связаны отремонтированными дорогами, а общая стоимость была как можно ниже.