Permutation Grid

时间限制：2s
空间限制：1024MB

题目描述

给定两个 $1,2,\ldots,N$ 的排列 $R_1,\ldots,R_N$ 和 $C_1,\ldots,C_N$。要把一个 $N\times N$ 网格的每个格子染成黑色或白色，使第 $i$ 行恰有 $R_i$ 个黑格，第 $j$ 列恰有 $C_j$ 个黑格。可以证明满足这些条件的染色方案恰好有一个。

给定 $Q$ 个询问 $(r_i,c_i)$。对每个询问，若第 $r_i$ 行第 $c_i$ 列的格子为黑色则回答 #，否则回答 .。

输入格式

第一行输入整数 $N$。

第二行输入排列 $R_1,R_2,\ldots,R_N$。

第三行输入排列 $C_1,C_2,\ldots,C_N$。

第四行输入整数 $Q$，随后 $Q$ 行每行输入两个整数 $r_i,c_i$。

输出格式

输出一个长度为 $Q$、仅由 # 和 . 组成的字符串，第 $i$ 个字符表示第 $i$ 个询问的答案。

样例输入 1

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

样例输出 1

#.#.#.#

数据范围

• $1\le N,Q\le 10^5$；
• $R$ 和 $C$ 均为 $1,2,\ldots,N$ 的排列；
• $1\le r_i,c_i\le N$；
• 输入中的所有数均为整数。