This page is still under construction.

Parts of this page are still being built. What you see may change.

Goblin Garden Guards

Time limit3sMemory limit256 MB

Summary
Count how many of up to 100000 points remain uncovered by 20000 sprinkler circles of radius at most 100.
Level

Medium5 of 10

Topics
Geometry, Hash map
Solved
No attempts yet

Problem

Goblins have invaded the Nedewsian city of Mlohkcots. Goblins are small, green critters, and nothing pleases them more than adding entropy to the calm and ordered lives of ordinary people. They fear very little, but they do fear water.

The invasion has reached the royal gardens. The goblins steal fruit, take the lawnmower for joyrides and carve the trees into obscene shapes, and King Lrac Fatsug has decreed that the nonsense stop immediately.

The garden has an automated sprinkler system. Turning the sprinklers on soaks every goblin within range, and a soaked goblin runs home to dry off.

You serve in the royal garden guards. Count how many goblins are still in the garden after the sprinklers have been turned on, so that the royal gardeners can plan their next move.

Input

The first line contains one integer gg (1≤g≤1000001 \le g \le 100000), the number of goblins in the royal gardens.

Each of the next gg lines contains the position of one goblin as two integers xix_i and yiy_i (0≤xi≤100000 \le x_i \le 10000, 0≤yi≤100000 \le y_i \le 10000). The garden is flat and square, and all distances are in meters. Because of quantum interference, several goblins can occupy exactly the same spot in the garden.

The next line contains one integer mm (1≤m≤200001 \le m \le 20000), the number of sprinklers in the garden.

Each of the next mm lines contains the position of one sprinkler and the radius of the area it covers as three integers xix_i, yiy_i and rr (0≤xi≤100000 \le x_i \le 10000, 0≤yi≤100000 \le y_i \le 10000, 1≤r≤1001 \le r \le 100). Any goblin at a distance of at most rr from the point (xi,yi)(x_i, y_i) is soaked by this sprinkler. Several sprinklers can share the same location.

Output

Print the number of goblins remaining in the garden after the sprinklers have been turned on.

Examples3

  1. Example 1

    Input
    5
0 0
100 0
0 100
100 100
50 50
1
0 0 50
    Expected output
    4

  2. Example 2

    Input
    6
0 5
5 0
2 1
1 1
10 10
5 5
1
5 5 5
    Expected output
    2

  3. Example 3

    Input
    3
0 0
10000 10000
5000 5000
2
100 100 1
9000 9000 100
    Expected output
    3