Оцінка на експорт
Лука володіє компанією, що спеціалізується на географічних даних, і створює детальні карти міста для експорту зацікавленим клієнтам. Часто клієнтам не потрібна повна карта, а лише спрощена версія, що включає лише основні вулиці.
Карта міста представлена у вигляді неорієнтованого графа, що складається з n перехресть, позначених цілими числами від 1 до n, і m двосторонніх вулиць. Кожна вулиця має пріоритет, виражений невід'ємним цілим числом. Коли клієнт запитує карту, він обирає пороговий пріоритет p. Оригінальна карта копіюється і перетворюється в експортовану карту за наступною процедурою:
Видаляються всі вулиці з пріоритетом нижче p.
Для кожного перехрестя i від 1 до n (обробляються в цьому порядку):
(a) Якщо перехрестя i не з'єднане з жодною вулицею, воно видаляється.
(b) Якщо перехрестя i з'єднане лише з двома вулицями x і y, що ведуть до перехресть a і b, відмінних від i, то перехрестя i стягується наступним чином:
Вулиці x і y видаляються.
Перехрестя i видаляється.
Додається нова вулиця z, що з'єднує перехрестя a і b.
Ілюстрація другого прикладу з пороговим пріоритетом 95
Спочатку карта не містить петель (вулиця, що з'єднує перехрестя з самим собою) і паралельних ребер (більше однієї вулиці між однією і тією ж парою перехресть), але петлі і паралельні ребра можуть утворюватися під час процедури стиснення. Зверніть увагу, що на кроці 2. (б) ні x, ні y не можуть бути петлями (обидва a і b повинні відрізнятися від i), але нова додана вулиця z може бути петлею (можливо, a і b однакові).
За наданою картою і послідовністю запитів на експорт, для кожного запиту визначте кількість перехресть і кількість вулиць на експортованій карті.
Вхідні дані
Перша стрічка містить два числа n (1 ≤ n ≤ 300 000) і m (1 ≤ m ≤ 300 000) – кількість перехресть і кількість вулиць. Кожна з наступних m стрічок містить три цілі числа a, b і p (1 ≤ a, b ≤ n, 0 ≤ p ≤ 300 000), що описують вулицю з пріоритетом p, яка з'єднує перехрестя a і b. Жодна вулиця не з'єднує перехрестя саме з собою. Між кожною парою перехресть існує не більше однієї вулиці.
Наступна стрічка містить кількість запитів на експорт q (1 ≤ q ≤ 300 000). Наступна стрічка містить q цілих чисел. k-те число t[k] (0 ≤ t[k] ≤ 300 000) є пороговим значенням для k-го запиту.
Вихідні дані
Виведіть q рядків. У k-му рядку виведіть два цілі числа - кількість перехресть і кількість вулиць відповідно, на експортованій карті для k-го запиту.