Bodyguards
Have you ever met the members of the ten European royal houses, the Argentinian football team including their coach Diego Maradona, or all of the Turing and Fields medal prize winners? We have invited many celebrities from all over the world to the CEOI 2010 closing ceremony. Unfortunately, very few of them responded to our invitation, and those who did, politely rejected. Nevertheless, do not forget to bring your camera to the ceremony, one never knows who might turn up!
As you can imagine, the security of the guests is of utmost importance. The problem is how to seat their bodyguards in the audience so that maximal security is guaranteed.
The auditorium contains many seats, arranged into a large grid. Based on the safety regulations a security expert has determined necessary bodyguard counts for each row and each column of the auditorium.
You are given the required number of bodyguards for each row and column of the auditorium. This information is given in a compressed form as explained below. Determine whether it is possible to place the bodyguards in such a way that in each row and each column we would have exactly the required number of bodyguards.
Assume that the auditorium is initially empty, i.e., you may seat bodyguards wherever you wish. Each seat may only be occupied by a single bodyguard.
Input
The input begins with the description of the rows. The first line of the input contains one positive integer R: the number of groups of rows. R lines follow. Each of these lines contains 2 positive integers: the required number of bodyguards in each row of the group and the number of rows that form the group.
This is followed by the description of column groups. The next line contains one positive integer C: the number of groups of columns. C lines follow. Each of these lines contains 2 positive integers: the required number of bodyguards in each column of the group and the number of columns that form the group.
Constraints
You may assume that the total number of bodyguards required by row constrains is the same as the total number of bodyguards required by column constraints. You may assume that this total number of bodyguards is at most 10^18.
You may assume that all numbers are positive integers that do not exceed 1000000000.
You may assume that 1 ≤ R, C ≤ 200000.
Several batches of test cases, worth a total of 50 points, satisfy the following criteria:
the total number of rows in the auditorium will be at most 2000
the total number of columns in the auditorium will be at most 2000
the total number of bodyguards will be at most 1000000.
In a test batch worth another 10 points we have R, C ≤ 100 in each test case.
Output
Output a single line with the number "1" if the constraints are satisfiable and the number "0" otherwise (quotes for clarity).