Description

In a matrix, you need to place a required number of bodyguards in certain rows and columns. Each cell can contain at most one bodyguard. Determine whether there exists an arrangement such that some rows and columns contain exactly the required number of bodyguards.

Input Format

The first line contains an integer $R$, meaning there are $R$ constraints on rows.

The next $R$ lines each contain two integers $a, b$, meaning there are $b$ rows that must contain exactly $a$ bodyguards.

The next line contains an integer $C$, meaning there are $C$ constraints on columns.

The next $C$ lines each contain two integers $x, y$, meaning there are $y$ columns that must contain exactly $x$ bodyguards.

Output Format

Output one number in a single line. If such an arrangement exists, output 1; otherwise output 0.

2
2 1
1 2
1
2 2

1

2
3 2
1 1
2
3 2
1 1

0

Hint

Explanation of Sample 1

One row must contain two bodyguards, and two rows must contain one bodyguard; two columns must contain two bodyguards. One possible arrangement is:

XX
X.
.X

Here, X represents a bodyguard and . represents an empty cell.

Explanation of Sample 2

Two rows must be filled entirely with bodyguards, but one column is required to contain only one bodyguard, so it is impossible. Therefore, there is no solution.

Constraints

• For $50\%$ of the testdata, it is guaranteed that $R, C \le 2000$, and there are at most $10^6$ bodyguards.
• For $100\%$ of the testdata, the total number of bodyguards is at most $10^{18}$. All numbers are positive integers not exceeding $10^9$, and $1 \le R, C \le 2 \times 10^5$.

Notes

Translated from CEOI 2010 day 1 T3 bodyguards.

The translation copyright belongs to the problem provider

Translated by ChatGPT 5