#arc132a. [arc132_a]Permutation Grid

[arc132_a]Permutation Grid

题目描述

给定两个 1,dots,n1,\\dots,n 的排列:R1,dots,RnR_1,\\dots,R_nC1,dots,CnC_1,\\dots,C_n

我们有一个由 nn 行和 nn 列组成的网格。你需要将每个方块涂成黑色或白色,以满足以下条件:

  • 对于 i=1,dots,ni=1,\\dots,n,从上到下数第 ii 行有恰好 RiR_i 个黑方块。
  • 对于 j=1,dots,nj=1,\\dots,n,从左到右数第 jj 列有恰好 CjC_j 个黑方块。

可以证明,在这个问题的约束条件下,只有一种方式可以绘制网格来满足条件。

给定 qq 个查询 (r1,c1),dots,(rq,cq)(r_1,c_1),\\dots,(r_q,c_q)。对于每个 i=1,dots,qi=1,\\dots,q,如果位于从上到下数第 rir_i 行和从左到右数第 cic_i 列的方块被涂成黑色,则输出 #;如果该方块被涂成白色,则输出 .

约束条件

  • 1len,qle1051\\le n,q\\le 10^5
  • R1,dots,RnR_1,\\dots,R_nC1,dots,CnC_1,\\dots,C_n 都是 1,dots,n1,\\dots,n 的排列。
  • 1leri,cilen1\\le r_i,c_i \\le n
  • 输入中的所有值都为整数。

输入

从标准输入中以以下格式给出输入:

nn R1R_1 dots\\dots RnR_n C1C_1 dots\\dots CnC_n qq r1r_1 c1c_1 vdots\\vdots rqr_q cqc_q

输出

输出一个长度为 qq 的字符串,第 ii 个字符是第 ii 个查询的答案。


示例输入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

#.#.#.#

通过以下方式绘制网格,可以满足条件。

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