Under construction

Still being built. Things may change

A Walk in the Park

Time limit2sMemory limit128 MB

Summary
Given points for trees and infinite horizontal or vertical paths that avoid all trees, count trees visible along a perpendicular direction with no other tree blocking the sight line.
Level

Medium6 of 10

Topics
Sorting, Hash map, Geometry, Implementation
Solved
No attempts yet

Problem

You are responsible for inspecting the trees in a park to keep them healthy. Each tree is a point in the two-dimensional plane, and no two trees share a location. Because of freshly replanted grass, you may only walk along a set of paths. Each path is an infinite horizontal or vertical line in the plane, and no tree lies on any path.

You are worried that some trees cannot be seen from the paths. A tree is visible only if, standing somewhere on a path and facing in a direction perpendicular to that path, you can see it with no other tree blocking your line of sight. (From a vertical path you look horizontally; from a horizontal path you look vertically.) Given the layout of the park, report how many trees are visible.

Input

The input contains several data sets. For each data set, the first line has two integers NN and MM (0<N,M≤1000000 < N, M \le 100000) separated by a space: NN is the number of trees and MM is the number of paths.

The next NN lines each contain two space-separated integers XX and YY, the coordinates of a tree; XX and YY may be any 32-bit integers.

The next MM lines each describe one path — a vertical or horizontal line — in the form x=K or y=K with no spaces, where x and y are lower-case and KK may be any 32-bit integer.

The input ends with a line containing two space-separated zeros.

Output

For each data set, print a single line with one integer: the number of visible trees. Do not print any blank lines between outputs.

Examples1

  1. Example 1

    Input
    6 3
    -1 3
    4 2
    6 2
    6 3
    6 4
    4 3
    x=0
    y=-1
    y=5
    1 2
    2 3
    x=5
    y=5
    0 0
    
    Expected output
    5
    1