Gats and the Cozy Corridors

Time limit: 2000 msMemory limit: 256 MB

Gats has found a network of soft cushions connected by yarn corridors. Each cushion $i$ has a coziness $C_i$ and contains $B_i$ drops of milk. Each corridor $j$ connects cushions $U_j$ and $V_j$ and has steadiness $S_j$ .

Gats receives several independent queries. For a query $(A, X)$ :

A cushion $i$ is welcoming if $C_i \ge X$ .
A corridor $j$ is safe if $S_j \ge X$ .

For each query, report the sum of $B_i$ over all cushions $i$ that Gats can reach. Milk is not consumed, and all queries are independent.

Input

The first line contains three integers $N$ , $M$ , and $Q$ ( $1 \le N \le 2 \times 10^5$ , , ), the number of cushions, corridors, and queries.

Output

For each query $k$ in order from $1$ to $Q$ , print one integer: the total number of drops of milk over all cushions reachable by Gats in that query.

Samples

Sample 1

Input

Output

18
0
1

In the first query, Gats starts at cushion $1$ with mood $3$ . Cushions $1$ , $2$ , and $3$ are welcoming, and they are connected by safe corridors, so the total is $10 + 7 + 1 = 18$ . In the second query, cushion is not welcoming for mood .

Gats and the Cozy Corridors

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2