MOLOCO 是一家利用其高性能广告平台将广告商与潜在用户进行匹配的公司。

MOLOCO 与 $N$ 个广告商保持联系，其中第 $i$ 个广告商已付费投放 $a_i$ 个广告。我们先进的预测算法挑选了 $M$ 个潜在接收者，我们将向他们投放广告。对于第 $j$ 个受众，我们最多可以投放 $b_j$ 个广告。

Jaehyun 正在测试几种增加广告参与度的假设。有一天，Jaehyun 想到，单个接收者收到的所有广告都应该来自不同的广告商：多次观看同一个广告是很无聊的。

Jaehyun 想要评估他假设的盈利能力。他将执行以下几种更新：

• 1 $i$：将 $a_i$ 增加 1。
• 2 $i$：将 $a_i$ 减少 1。
• 3 $j$：将 $b_j$ 增加 1。
• 4 $j$：将 $b_j$ 减少 1。

所有更新都是累积的。Jaehyun 想要检查在广告商和接收者情况不断变化的情况下，系统是否能够投放所有广告商的广告。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 250\,000$)。 第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$ ($0 \le a_i \le 250\,000$)。 第三行包含 $M$ 个整数 $b_1, b_2, \dots, b_M$ ($0 \le b_j \le 250\,000$)。 第四行包含一个整数 $Q$ ($1 \le Q \le 250\,000$)。 接下来的 $Q$ 行，每行包含两个整数，形式如下：

• 1 $i$ ($1 \le i \le N$)
• 2 $i$ ($1 \le i \le N$)
• 3 $j$ ($1 \le j \le M$)
• 4 $j$ ($1 \le j \le M$)

输入保证所有 $a_i$ 和 $b_j$ 的值始终为非负数。

输出格式

输出 $Q$ 行。在第 $i$ 行，如果经过前 $i$ 次更新后所有广告都能被投放，则输出 1，否则输出 0。

样例

输入 1

5 5
1 5 2 4 3
3 3 3 3 3
5
4 2
3 5
2 2
1 1
1 4

输出 1

0
1
1
1
0