Bodyguards

The auditorium for a closing ceremony has many seats arranged in a large rectangular grid. For security, an expert has fixed the exact number of bodyguards that must be seated in each row and in each column.

You are given the required number of bodyguards for every row and every column, provided in the compressed (grouped) form described below. The auditorium starts empty and each seat may hold at most one bodyguard. Decide whether it is possible to seat the bodyguards so that every row and every column contains exactly its required number of bodyguards.

The input first describes the rows.

• The first line contains an integer $R$, the number of row groups.
• Each of the next $R$ lines contains two integers $b$ and $n$: every row in this group requires exactly $b$ bodyguards, and the group consists of $n$ rows.

The input then describes the columns.

• The next line contains an integer $C$, the number of column groups.
• Each of the next $C$ lines contains two integers $b$ and $n$: every column in this group requires exactly $b$ bodyguards, and the group consists of $n$ columns.

Print a single line containing 1 if the requirements can be satisfied, or 0 otherwise.

• The total number of bodyguards required by the rows equals the total required by the columns, and this total is at most $10^{18}$.
• Every integer in the input is a positive integer not exceeding $10^9$.
• $1 \le R, C \le 200,000$.