A - Permutation Grid Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

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 列目にあるマスの色が黒であれば # を、白であれば . を出力してください。

制約

  • 1\le n,q\le 10^5
  • R_1,\dots,R_n と C_1,\dots,C_n はそれぞれ 1,\dots,n の順列
  • 1\le r_i,c_i \le n
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

n
R_1 \dots R_n
C_1 \dots C_n
q
r_1 c_1
\vdots
r_q c_q

出力

i 文字目が i 番目のクエリの答えであるような、# と . からなる長さ q の文字列を出力せよ。

入力例 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

#.#.#.#

次のような塗り方が条件を満たします。

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

Score : 400 points

Problem Statement

Given are two permutations of 1,\dots,n: R_1,\dots,R_n and C_1,\dots,C_n.

We have a grid with n horizontal rows and n vertical columns. You will paint each square black or white to satisfy the following conditions.

  • For each i=1,\dots,n, the i-th row from the top has exactly R_i black squares.
  • For each j=1,\dots,n, the j-th column from the left has exactly C_j black squares.

It can be proved that, under the Constraints of this problem, there is exactly one way to paint the grid to satisfy the conditions.

You are given q queries (r_1,c_1),\dots,(r_q,c_q). For each i=1,\dots,q, print # if the square at the r_i-th row from the top and c_i-th column from the left is painted black; print . if that square is painted white.

Constraints

  • 1\le n,q\le 10^5
  • R_1,\dots,R_n and C_1,\dots,C_n are each permutations of 1,\dots,n.
  • 1\le r_i,c_i \le n
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

n
R_1 \dots R_n
C_1 \dots C_n
q
r_1 c_1
\vdots
r_q c_q

Output

Print a string of length q whose i-th character is the answer to the i-th query.

Sample Input 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

Sample Output 1

#.#.#.#

The conditions are satisfied by painting the grid as follows.

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