Export Estimate

Luka runs a geographic data company. The company maintains a detailed city map and exports the data to interested parties. Most clients do not want the complete map. They want a simplified map that keeps only the major streets.

The city map is an undirected graph with $n$ intersections, numbered from $1$ to $n$, and $m$ two-way streets. Every street carries a priority, which is a non-negative integer. A client who requests a map picks a threshold priority $p$. The original map is copied, and the exported map is produced by the following procedure.

1. Delete every street whose priority is lower than $p$.

2. Process the intersections $i$ in the order $i = 1, 2, \ldots, n$.

   1. If intersection $i$ has no street attached to it, delete intersection $i$.

   2. If intersection $i$ has exactly two different streets $x$ and $y$ attached to it, where $x$ leads to intersection $a$ and $y$ leads to intersection $b$, and both $a$ and $b$ differ from $i$, contract intersection $i$ as follows.

      1. Delete streets $x$ and $y$.
      2. Delete intersection $i$.
      3. Add a new street $z$ connecting intersections $a$ and $b$.

The picture shows threshold priority $95$ applied to the map of the second example.

The initial map has no loop (a street joining an intersection to itself) and no parallel streets (more than one street between the same pair of intersections), but contraction can create both. In the second rule of step 2 neither $x$ nor $y$ can be a loop, because $a$ and $b$ both differ from $i$, yet the new street $z$ can be a loop, because $a$ and $b$ may be equal.

You are given the map and a sequence of export requests. For each request, report how many intersections and how many streets the exported map has.

The first line contains the number of intersections $n$ and the number of streets $m$. ($1 \le n \le 300\,000$, $1 \le m \le 300\,000$)

Each of the next $m$ lines contains three integers $a$, $b$ and $p$. ($1 \le a, b \le n$, $0 \le p \le 300\,000$) They describe a street of priority $p$ connecting intersections $a$ and $b$. No street joins an intersection to itself, and there is at most one street between any two intersections.

The next line contains the number of export requests $q$. ($1 \le q \le 300\,000$)

The last line contains $q$ integers. The $k$-th integer $t_k$ is the threshold priority of the $k$-th request. ($0 \le t_k \le 300\,000$)

Print $q$ lines. On the $k$-th line print the number of intersections and the number of streets of the map exported for the $k$-th request, separated by a space.