你是否曾见过欧洲十个皇室的成员、包括主教练迭戈·马拉多纳在内的阿根廷国家足球队，或者所有的图灵奖和菲尔兹奖得主？我们邀请了来自世界各地的众多名流参加 CEOI 2010 的闭幕式。遗憾的是，他们中很少有人回应我们的邀请，而那些回应的人也礼貌地拒绝了。尽管如此，别忘了带上你的相机去参加典礼，谁也说不准会有谁突然出现！

正如你所能想象的，宾客的安全至关重要。问题是如何在观众席中安排保镖的座位，以确保最大程度的安全。

礼堂包含许多座位，排列成一个大型网格。根据安全规定，安全专家确定了礼堂每行和每列所需的保镖人数。

给你礼堂每行和每列所需的保镖人数。这些信息以压缩格式给出，具体说明如下。请判断是否可以安排保镖的位置，使得每行和每列都恰好有所需数量的保镖。

假设礼堂最初是空的，即你可以将保镖安排在任何你希望的位置。每个座位最多只能由一名保镖占用。

输入格式

输入首先是行的描述。输入的第一行包含一个正整数 $R$：行组的数量。接下来的 $R$ 行，每行包含 2 个正整数：该组中每行所需的保镖人数以及组成该组的行数。

接下来是列组的描述。下一行包含一个正整数 $C$：列组的数量。接下来的 $C$ 行，每行包含 2 个正整数：该组中每列所需的保镖人数以及组成该组的列数。

输出格式

如果约束可以满足，则输出单行数字 1，否则输出 0。

数据范围

你可以假设行约束所需的保镖总数与列约束所需的保镖总数相同。你可以假设保镖总数最多为 $10^{18}$。

你可以假设所有数字均为不超过 $1\,000\,000\,000$ 的正整数。

你可以假设 $1 \le R, C \le 200\,000$。

若干测试点（共 50 分）满足以下标准：

• 礼堂的总行数最多为 $2000$
• 礼堂的总列数最多为 $2000$
• 保镖总数最多为 $1\,000\,000$

另有 10 分的测试点满足每个测试用例中 $R, C \le 100$。

样例

输入格式 1

2
2 1
1 2
1
2 2

输出格式 1

1

说明 1

有两组行：第一组有一行，必须包含两名保镖；第二组有两行，每行必须包含一名保镖。有一组列：两列中的每一列都必须包含两名保镖。一种可能的保镖安置方案如下：

XX
X.
.X

输入格式 2

2
3 2
1 1
2
3 2
1 1

输出格式 2

0

说明 2

其中两行需要排满保镖。因此，每列中必须至少有两名保镖。然而，最后一列只能包含一名保镖，这产生了矛盾。