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

Карта города представляет собой неориентированный граф, состоящий из n пересечений, обозначенных целыми числами от 1 до n и m двухсторонних улиц. Каждой улице присваивается приоритет - неотрицательное целое число. При запросе карты клиент выбирает пороговый приоритет p. Затем исходная карта копируется и преобразуется в экспортированную карту, используя следующую процедуру:

1. Все улицы, приоритет которых ниже p, удаляются.

2. Для каждого пересечения i для 1, 2, . . . , 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-ое число tk (0 ≤ tk ≤ 300 000) является пороговым значением для k-го запроса.

Выходные данные

Выведите q строк. В k - ой строке выведите два целых числа - количество пересечений и количество улиц соответственно, на экспортированной карте для k - го запроса.