지도 내보내기 추정

루카는 지리 정보 회사를 운영한다. 이 회사는 상세한 도시 지도를 관리하고, 그 데이터를 원하는 곳에 내보낸다. 고객 대부분은 지도 전체를 원하지 않는다. 주요 도로만 남긴 간략한 지도를 원한다.

도시 지도는 $1$번부터 $n$번까지 번호가 붙은 교차로 $n$개와 양방향 도로 $m$개로 이루어진 무향 그래프다. 각 도로에는 우선순위가 하나씩 붙어 있고, 우선순위는 음이 아닌 정수다. 고객은 지도를 요청하면서 기준 우선순위 $p$를 고른다. 원본 지도를 복사한 다음, 아래 절차로 내보낼 지도를 만든다.

1. 우선순위가 $p$보다 낮은 도로를 모두 지운다.

2. 교차로 $i$를 $i = 1, 2, \ldots, n$ 순서로 하나씩 처리한다.

   1. 교차로 $i$에 연결된 도로가 하나도 없으면 교차로 $i$를 지운다.

   2. 교차로 $i$에 서로 다른 도로 $x$와 $y$가 정확히 두 개 연결되어 있고, $x$는 교차로 $a$로, $y$는 교차로 $b$로 이어지며 $a$와 $b$가 모두 $i$와 다르면, 다음 절차로 교차로 $i$를 축약한다.

      1. 도로 $x$와 $y$를 지운다.
      2. 교차로 $i$를 지운다.
      3. 교차로 $a$와 $b$를 잇는 새 도로 $z$를 추가한다.

위 그림은 두 번째 예제의 지도에 기준 우선순위 $95$를 적용한 모습이다.

처음 지도에는 루프(같은 교차로를 자기 자신과 잇는 도로)도 없고, 같은 교차로 쌍을 잇는 도로가 둘 이상 있지도 않다. 그러나 축약 과정에서는 루프와 평행 도로가 생길 수 있다. 위 2번의 두 번째 규칙에서 $x$와 $y$는 루프일 수 없지만($a$와 $b$가 모두 $i$와 달라야 하므로), 새로 추가하는 도로 $z$는 루프가 될 수 있다. $a$와 $b$가 같을 수 있기 때문이다.

지도와 내보내기 요청이 차례로 주어진다. 각 요청마다 내보낸 지도의 교차로 개수와 도로 개수를 구하라.

첫째 줄에 교차로 개수 $n$과 도로 개수 $m$이 주어진다. ($1 \le n \le 300\,000$, $1 \le m \le 300\,000$)

다음 $m$개 줄에는 각각 세 정수 $a$, $b$, $p$가 주어진다. ($1 \le a, b \le n$, $0 \le p \le 300\,000$) 우선순위가 $p$인 도로가 교차로 $a$와 $b$를 잇는다는 뜻이다. 자기 자신을 잇는 도로는 없고, 두 교차로를 잇는 도로는 많아야 하나다.

그다음 줄에 내보내기 요청의 개수 $q$가 주어진다. ($1 \le q \le 300\,000$)

마지막 줄에 정수 $q$개가 주어진다. $k$번째 정수 $t_k$는 $k$번째 요청의 기준 우선순위다. ($0 \le t_k \le 300\,000$)

$q$개의 줄을 출력한다. $k$번째 줄에는 $k$번째 요청으로 내보낸 지도의 교차로 개수와 도로 개수를 공백으로 구분해 출력한다.