Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов «Большой линейный коллайдер» (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон \(е^–\) , либо положительно заряженную частицу — позитрон \(е^{+}\) . В эксперименте \(i\)-я частица исходно размещается в точке с координатой \(x_i\) . После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: \(е^{–}\) частицы перемещаются по направлению уменьшения координаты, а \(е^{+}\) частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

Если в процессе перемещения частицы \(е^{–}\) и \(е^{+}\) оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.

Ученые выбрали \(m\) различных моментов времени \(t_1, t_2, \dots, t_m\), для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени \(t_j\) , не должны учитываться при подсчете количества частиц для этого момента времени.

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

В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.

Экспериментальная установка содержит квадратную платформу размером \(10^9 \times 10^9\) , заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать \(n\) силовых полей.

Генератор силовых полей установлен над точкой (0, 0). При этом \(i\)-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и \((x_i , y_i)\).

В эксперименте планируется изучать воздействие излучения на растения при облучении через \(k\) силовых полей. Из заданных n полей необходимо выбрать \(k\) полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все \(k\) выбранных силовых полей, была максимальна.

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

Взаимодействие сотрудников в некоторой компании организовано в виде иерархической структуры. Всего в компании работают \(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\) минимально.