题目描述

给定 $1,\dots,n$ 的排列 $R_1,\dots,R_n$ 和 $C_1,\dots,C_n$。

你需要将一个 $n$ 行 $n$ 列的网格按照以下条件用黑色或白色进行涂色：

• 对于每个 $i=1,\dots,n$，从上往下第 $i$ 行的黑色格子的数量恰好为 $R_i$ 个。
• 对于每个 $j=1,\dots,n$，从左往右第 $j$ 列的黑色格子的数量恰好为 $C_j$ 个。

在本题的限制条件下，可以证明满足条件的涂色方法恰好只有一种。

给定 $q$ 个查询 $(r_1,c_1),\dots,(r_q,c_q)$。对于每个 $i=1,\dots,q$，如果从上往下第 $r_i$ 行、从左往右第 $c_i$ 列的格子是黑色，则输出 #，否则输出 .。

输入格式

输入以如下格式从标准输入读入。

$n$ $R_1$ $…$ $R_n$ $C_1$ $…$ $C_n$ $q$
$r_1$ $c_1$
⋮
$r_q$ $c_q$

输出格式

输出一个由 # 和 . 组成的长度为 $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\leq n,q\leq 10^5$
• $R_1,\dots,R_n$ 和 $C_1,\dots,C_n$ 均为 $1,\dots,n$ 的排列
• $1\leq r_i,c_i\leq n$
• 所有输入均为整数

样例解释 1

以下是一种满足条件的涂色方案：

#####
#...#
#.#.#
###.#
....#

由 ChatGPT 4.1 翻译