City Map Contraction

An undirected graph is given which represents a city map. The map contains \( n \) intersections (numbered from 1 to \( n \)) and \( m \) two-way streets. Each street is assigned a non-negative integer priority.

When a client requests an exported map, they provide a threshold priority \( p \). The exported map is obtained by performing the following steps on a copy of the original map:

1. Delete all streets with priority lower than \( p \).
2. For each intersection \( i \) (from 1 to \( n \), in that order):
   • If intersection \( i \) is not incident to any street, delete it.
   • If intersection \( i \) is incident to exactly two different streets \( x \) and \( y \) (and both \( x \) and \( y \) are not loops, i.e. they connect \( i \) to some other intersections \( a \) and \( b \) respectively), then contract intersection \( i \) by performing the following:
     1. Delete streets \( x \) and \( y \);
     2. Delete intersection \( i \);
     3. Add a new street connecting intersections \( a \) and \( b \). Note that \( a \) and \( b \) may be equal, forming a loop, and parallel edges may be introduced.

Initially, the map does not contain loops or parallel edges, but these might appear after contraction. For a given exported map request, output the number of intersections and the number of streets in the resulting map.

Input Format: The first line contains three integers \( n \), \( m \), \( q \) \( (1 \leq n \leq \ldots) \) denoting the number of intersections, streets, and export requests respectively. The following \( m \) lines each contain three integers \( u\), \( v\) and \( w \) representing a street connecting intersections \( u \) and \( v \) with priority \( w \) (with \( u \neq v \)). Then, \( q \) lines follow, each containing a single integer \( p \) representing an export request's threshold priority.

Output Format: For each query, output two integers on a separate line: the number of intersections and the number of streets in the exported map.

inputFormat

The first line contains three integers \( n \), \( m \), \( q \). Each of the next \( m \) lines contains three integers \( u \), \( v \), \( w \), indicating a street between intersections \( u \) and \( v \) with priority \( w \). The following \( q \) lines each contain a threshold integer \( p \>.

outputFormat

For each threshold \( p \), output the number of intersections and the number of streets in the resulting exported map, separated by a space. Each answer should be on its own line.

sample

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

4 2
2 1