在一个神秘的 JOSLFN 上，wzy 和 lqs2015 常年占据着切题榜的 rk1 和 rk2。现在他们在研究如何快速造题并验题。

分工是这样的：有 $n$ 个 wzy 负责造题，第 $i$ 个 wzy 会造出恰好 $a_i$ 道题。有 $m$ 个 lqs2015 负责验题，第 $j$ 个 lqs2015 最多能验 $b_j$ 道题。每个 wzy 需要把他造的每一道题都给一个 lqs2015 来验。不过有一条限制，就是每个 wzy 的 $a_i$ 道题必须给不同的 lqs2015 ，否则这个 lqs2015 会因为验到了来自同一个 wzy 的题而感到厌烦并且让所有 wzy 和 lqs2015 都消失。

在一旁瑟瑟发抖的 superay 想要知道，是否存在一种符合限制的验题的分配方案。

随着时间的推移，会有 $q$ 次对 $a, b$ 的修改。每次修改有如下四种：

• 1 i 表示将 $a_i$ 加 $1$。
• 2 i 表示将 $a_i$ 减 $1$。
• 3 j 表示将 $b_j$ 加 $1$。
• 4 j 表示将 $b_j$ 减 $1$。

superay 想知道每次修改之后还是否存在合法方案。

Task

Input

第一行两个正整数 $n, m$。

第二行 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$。

第三行 $m$ 个非负整数 $b_1, b_2, \cdots, b_m$。

第四行一个正整数 $q$。

接下来 $q$ 行，每行是如下四种之一：

• 1 i ($1\leq i\leq n$)
• 2 i ($1\leq i\leq n$)
• 3 j ($1\leq j\leq m$)
• 4 j ($1\leq j\leq m$)

保证任意时刻 $a, b$ 都非负。

Output

输出 $q$ 行，第 $i$ 行表示在第 $i$ 次操作之后的答案，有解输出 1，无解输出 0。

Sample

Input

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

Output

0
1
1
1
0

Constraint

本题采用捆绑测试。

• subtask $1$ ($10$ pts)：$n, m, q\leq 50$。
• subtask $2$ ($30$ pts)：$n, m, q\leq 1000$。
• subtask $3$ ($40$ pts)：$n, m, q\leq 100000$。
• subtask $4$ ($20$ pts)：无特殊限制。

对于 $100\%$ 的数据，$1\leq n, m, q\leq 250000, 0\leq a_i, b_j\leq 250000$。