Problem: Space Invaders

Want to try solving this problem? You can submit your code online if you log in or register.

Space Invaders

Input File: spacein.txt
Output File: spaceout.txt
Time Limit: 2 seconds
Memory Limit: 16 MB

You are sitting at your computer, playing a peaceful game of Space Invaders. In this game, you control a cannon which you can move left and right along the bottom of a 2-dimensional grid. It fires vertically upwards and destroys whatever is in its line of fire. Above each square of the top row of the grid is a Space Invader, as shown in the diagram below.

After days of non-stop playing, you have reached the final level of the game. In this final level, large alien motherships occupy the grid to protect the Space Invaders. The motherships lie in between you and the Space Invaders and cannot be destroyed with your humble cannon. Your cannon can only destroy a Space Invader if a mothership is not obscuring its line of fire. The motherships are represented as large polygons with corners at integer coordinates. Before you attempt to win this battle, you need to determine how many Space Invaders you can now fire at.

For example, in the diagram below, there are only four Space Invaders which you can fire at directly. The others are obscured by the motherships.

Space Invaders and Motherships on a grid

Your task is, given the position and shapes of the motherships in the sky, to determine how many Space Invaders you can destroy using your cannon.

Input

The first line of input will consist of two space-separated integers w h, specifying the width and height of the area that the motherships may occupy (1 <= w,h <= 1,000,000,000). The top-left corner of the grid is defined as coordinate (0,0).

The second line will consist of a single integer k, with 0 <= k <= 100,000, specifying the number of motherships.

Following this will be the descriptions of each of the k motherships represented as polygons. The ith of these definitions will consist of a single integer p_i, the number of points in polygon i, followed by p_i lines each containing a pair of integers x_j and y_j separated by a single space (0 <= x_j <= w, 0 <= y_j <= h). Each of these pairs specifies one of the points on the boundary of polygon i.

You are guaranteed that 3 <= p_i <= 10. No two motherships may overlap, but their edges or corners may touch.

Output

Your output should consist of a single integer--the total number of Space Invaders that you can destroy with the motherships in position.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.