Due to its long history, a school campus contains many historical sites. To better protect these sites, the school has decided to enclose them with fences.

There are $p$ historical sites that need to be protected. These sites can be considered as integer points in a 2D plane. There are $n$ points that can serve as endpoints for the fences, and the coordinates of these endpoints are also integer points in the 2D plane. The endpoints are numbered from $1$ to $n$.

Fences can be built between $m$ pairs of endpoints. A potential fence segment is described by $(u, v, w)$, meaning a fence can be built between endpoint $u$ and endpoint $v$ at a cost of $w$. Fences are considered to be straight line segments. For design convenience, these potential fence segments do not intersect (they only meet at their endpoints).

Enclosing a historical site means there exists a simple polygon formed by fences such that the site lies inside the polygon.

Due to budget constraints, the school wants to minimize the cost of building the fences. You need to output the minimum cost to enclose at least $1$, $2$, ..., $p$ historical sites.

Input

The first line contains three positive integers $p$, $n$, and $m$, representing the number of historical sites, the number of endpoints, and the number of potential fence segments, respectively.

The next $p$ lines each contain two integers, representing the coordinates of each historical site.

The next $n$ lines each contain two integers, representing the coordinates of each endpoint. These endpoints are numbered $1$ to $n$ in the order they are provided.

The last $m$ lines each contain three non-negative integers $u$, $v$, and $w$, representing that a fence can be built between endpoint $u$ and endpoint $v$ at a cost of $w$.

Output

Output $p$ lines, representing the minimum cost to enclose at least $1$, $2$, ..., $p$ historical sites, respectively.

Examples

Input 1

3 9 15
-2 2
2 1
2 -1
3 0
3 2
1 2
-1 3
-3 3
-2 1
1 0
2 -2
2 -3
1 2 20
1 7 40
1 8 10
1 9 100
2 3 50
3 4 1000
3 7 10
4 5 10
4 6 10
4 7 1000
5 6 10
6 7 1000
7 8 120
7 9 10
8 9 10

Output 1

30
100
140

Note

The example is illustrated in the figures below.

Plan to protect at least 1 historical site

Plan to protect at least 2 historical sites

Plan to protect at least 3 historical sites

Constraints

For $100\%$ of the data, $n \leq 100$, $m \leq \binom{n}{2}$, $p \leq 10$. The absolute values of both coordinates for all points do not exceed $10^9$, $u, v \leq n$, and $w \leq 10^6$.

It is guaranteed that the potential fence segments will not pass through any historical sites. It is guaranteed that no two potential fence segments will intersect or overlap except at their endpoints. It is guaranteed that at least one way to enclose all historical sites exists. It is guaranteed that the $n$ endpoints are distinct.

The specific scale for each test case is as follows: