Ви граєте у свою улюблену мобільну гру. Карта гри складається з ~N~ (~2≤N≤10^5~) кімнат, помічених ~1…N~ з'єднаних ~N-1~ ребрами так, що утворюють дерево.

Ви можете дослідити карту, виконуючи серію "подорожей". Подорож це простий шлях з кімнати 1 до будь-якої іншої кімнати на дереві. Коли ви закінчуєте одну подорож, ви можете почати іншу знову з кімнати 1 . Карта завершена, коли кожна кімната відвідана хоча б однією подорожжю. Ваша головна мета – завершити карту мінімальною кількістю подорожей.

Ваша друга мета – зібрати якнайбільше зілля. Перш ніж розпочнуться подорожі, зілля з'явиться у деякій кімнаті. Ви можете взяти зілля, відвідавши кімнату, де з'явилося зілля перед поточною подорожжю. Якщо Ви не візьмете зілля, воно зникне, коли ця подорож закінчиться, і Ви не зможете взяти її у майбутній подорожі.

Як розумний програміст, після перегляду файлів гри, Ви змогли передбачити, де з'явиться зілля перед наступними ~N~ подорожами.

Яка максимальна кількість зілля, яку Ви можете зібрати за мінімальної кількості подорожей?

Формат вхідних даних

Перший рядок введення містить ціле число ~N~, кількість кімнат на карті.

Потім слідують ~N~ розділених одиночними пробілами цілих чисел ~p_1,p_2,…,p_N~ , ~1≤p_i≤N~ , де ~p_i~ це кімната, в якій з'явиться зілля перед ~i~-ю подорожжю.

Далі йдуть ~N-1~ рядків, що містять два розділених пробілами цілих числа ~a,b~ (~1≤a,b≤N~) - ребро між вершинами ~a~ і ~b~ . Гарантується, що ці ребра утворюють дерево.

Формат вихідних даних

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

ОЦІНЮВАННЯ:

• Тести 2 -7 (30 балів): ~N≤1000~
• Тести 8-15 (70 балів): Немає додаткових обмежень.

Приклад вхідних даних

5
5 4 3 2 1
1 2
1 3
3 4
3 5

Приклад вихідних даних

2

У цьому випадку мінімальна кількість необхідних подорожей дорівнює 3 .

Один оптимальний план, який збирає два зілля за три подорожі такий:

• Подорож 1: 1→3→5 (Беремо зілля у 5)
• Подорож 2: 1→3→4 (Беремо зілля у 4)
• Подорож 3: 1→2 (завершуємо подорож і ігноруємо зілля в 3)

Альтернативний план:

• Подорож 1: 1→2 (немає зілля)
• Подорож 2: 1→3→4 (Беремо зілля в 4)
• Подорож 3: 1→3→5 (Беремо зілля 3)

Бесі на дивній планеті. На цій планеті ~N~ (~1\le N\le 10^4~) місяців з ~a_1, \ldots, a_N~ днями по місяцях, відповідно. (~1\leq a_i \leq 4 \cdot 10^9~, всі ~a_i~ цілі числа). Тиждень на цій планеті триває ~L~ днів, ~L~ - додатне число.

Бесі відомо також таке:

• Для коректного ~L~, кожен місяць має щонайменше ~4~ тижні
• Для коректного ~L~, є не більше ~3~ різних значень ~a_i\bmod L~.

На жаль, Бесі забула ~L~. Допоможіть їй, виведіть суму всіх можливих значень ~L~.

Рекомендується використовувати 64-бітовий цілий тип (наприклад "long long" C/C++).

Формат вхідних даних

Перший рядок містить одне ціле число ~N~. Другий рядок містить ~N~ розділених одиночними пробілами цілих чисел ~a_1, \ldots, a_N~.

Формат вихідних даних

Одне ціле число - суму всіх можливих значень ~L~.

Оцінювання

• Тесты 3-4: ~1 \leq a_i \leq 10^6~
• Тесты 5-14: Немає додаткових обмежень

Приклад вхідних даних

12
31 28 31 30 31 30 31 31 30 31 30 31

Приклад вихідних даних

28

Можливі значення ~L~: 1, 2, 3, 4, 5, 6, 7. Наприклад, ~L=7~ коректно, тому що кожен місяць має не менше ~4 \cdot 7 = 28~ днів, кількість днів кожного місяця при розподілі на 7 дає один із залишків 0, 2, 3.

Приклад вхідних даних

4
31 35 28 29

Приклад вихідних даних

23

Можливі значень L : 1, 2, 3, 4, 6, 7 Наприклад, для L=6 - щомісяця має щонайменше 4⋅6=24 дня - залишок від розподілу на 6: 1 чи 4 чи 5.

Фермер Джон та його ~Q~ (~1≤Q≤2⋅10^5~ ) корів на Манхеттені. Корови втекли і гуляють містом. У Манхеттені ~N~ (~1≤N≤2⋅10^5~ ) доріг проходять нескінченно на ~xy~ - площині. Усі вони розташовані чи горизонтально, чи вертикально. Кожна горизонтальна або вертикальна може бути змодельована рівнянням виду ~y=c_i~ або ~x=c_i~ , де ціле число ~c_i~ в інтервалі від 0 до ~10^9~ включно.

ФД знає точно де кожна корова почала подорож та час подорожі. Кожна з корів рухається за наступним шаблоном:

• Вона рухається на північ (~+y~) або схід (~+x~) на одну одиницю на секунду.
• Якщо вона на одній дорозі, вона продовжує рухатися нею.
• Якщо вона на перетині двох доріг, вона йде на північ, на парній секунді подорожі та на схід інакше.

Вам дана карта Манхеттена та інформація про кожну корову, допоможіть ФД визначити де його корови зараз.

Формат вхідних даних

Перший рядок введення містить ~N~ та ~Q~.

Наступні ~N~ рядків описують дороги. Кожна дорога описується напрямком (H чи V), координатою ~c_i~. Гарантується, що кожна дорога є унікальною.

Наступні ~Q~ рядків описують корів. Кожна корова описується трьома цілими числами (~x_i, y_i, d_i~), що означають, що вона почала подорож з позиції (~x_i, y_i~) рівно ~d_i~ секунд тому. Гарантується, що (~x_i, y_i~) лежить на деякій дорозі і ~0≤x_i,y_i,d_i≤10^9~.

Формат вихідних даних

Виведіть ~Q~ рядків, де ~i~-й рядок містить поточну позицію ~i~-ї корови.

Оцінювання

• Тести 2-4 (20 балів): ~N, Q, c_i, x_i, y_i, d_i≤100~.
• Тести 5-9 (30 балів): ~N, Q≤3000~.
• Тести 10-20 (50 балів): Немає додаткових обмежень.

Пояснення

Перші дві корови пройшли такий шлях:

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)

(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

Приклад вхідних даних

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

Приклад вихідних даних

14 5
7 13
6 15
6 16
110 4

Фермер Джон наймає нового ватажка стада своїх корів. Для цього він проінтерв'юював ~N~ (~2≤N≤10^9~ ) корів. Кожному він призначив " рівень компетенції " - число трохи більше ~C~ (~1≤C≤10^4~ ).

Тому що він провів багато інтерв'ю, ФД забув усі ці рівні компетенції. Однак він запам'ятав ~Q~ (~1≤Q≤min(N-1,100) ~) пар чисел (~a_i,h_i~) де ~h_i~ - номер першої корови, з рівнем компетенції строго більшим ніж у корів від 1 до ~a_i~ (~1≤a_i<h_i≤N ~). </p>

ФД сказав Вам ~Q~ пар (~a_i, h_i~). Допоможіть йому порахувати скільки послідовностей рівнів компетенції відповідають цій інформації. Оскільки число дуже велике, виводьте його за модулем ~10^9+7~

Формат вхідних даних

Перший рядок містить ~N, Q, C~.

Кожен з наступних рядків ~Q~ містить пару (~a_i,h_i~). Гарантується, що всі ~a_i~ різні.

Формат вихідних даних

Вивести кількість за модулем ~10^9+7~ послідовностей компетенцій, відповідних інформації ФД.

Оцінювання

• Тести 3-4 (10 балів): ~N \leq 10~ і ~Q, C \leq 4~.
• Тести 5-7 (20 балів): ~N, C \leq 100~.
• Тести 8-10 (20 балів): ~N \leq 2000~ і ~C \leq 200~.
• Тести 11-15 (20 балів) ~N, C \leq 2000~.
• Тести 16-20 (30 балів) Немає додаткових обмежень

Приклад вхідних даних

6 2 3
2 3
4 5

Приклад вихідних даних

6

Тільки наступні шість послідовностей відповідають інформації ФД:

1 1 2 1 3 1
1 1 2 1 3 2
1 1 2 1 3 3
1 1 2 2 3 1
1 1 2 2 3 2
1 1 2 2 3 3

Приклад вхідних даних

10 1 20
1 3

Приклад вихідних даних

399988086