/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
各辺に 10^9 個のマスが並ぶマス目があり、最初は全てのマスが白です。このうち上から i マス目、左から j マス目を (i,j) と呼びます。
このマス目に操作を N 回行います。そのうち i 回目は次の通りです。
- (P_i,Q_i) を中心として X 字状にマス目を黒く塗る。即ち、全ての整数 k について以下の 2 種類のマスを黒く塗る。
- 1 \le P_i+k \le 10^9 かつ 1 \le Q_i+k \le 10^9 ならば (P_i+k,Q_i+k) を黒く塗る。
- 1 \le P_i+k \le 10^9 かつ 1 \le Q_i-k \le 10^9 ならば (P_i+k,Q_i-k) を黒く塗る。
操作後のマス目のうち、上から A マス目から B マス目、左から C マス目から D マス目からなる部分長方形を出力してください。
制約
- 入力は全て整数
- 1 \le N \le 2 \times 10^5
- 1 \le P_i, Q_i \le 10^9
- 1 \le A \le B \le 10^9
- 1 \le C \le D \le 10^9
- (B-A+1) \times (D-C+1) \le 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N A B C D P_1 Q_1 P_2 Q_2 \vdots P_N Q_N
出力
全体で B-A+1 行出力せよ。そのうち i 行目には D-C+1 文字の文字列を出力せよ。
出力のうち i 行目の j 文字目は、次の通りにせよ。
- (A+i-1,C+j-1) が白いなら、
. - (A+i-1,C+j-1) が黒いなら、
#
入力例 1
3 2 6 3 9 3 5 5 1 4 9
出力例 1
.#.##.. #.#..#. .#.#..# #...##. ....##.
最初、マス目の左上は次の通りです。
.......... .......... .......... .......... .......... .......... ..........
1 回目の操作で、 (3,5) を中心として X 字状にマス目を塗ります。操作後のマス目は次の通りです。
..#...#... ...#.#.... ....#..... ...#.#.... ..#...#... .#.....#.. #.......#.
2 回目の操作で、 (5,1) を中心として X 字状にマス目を塗ります。操作後のマス目は次の通りです。
..#.#.#... ...#.#.... ..#.#..... .#.#.#.... #.#...#... .#.....#.. #.#.....#.
3 回目の操作で、 (4,9) を中心として X 字状にマス目を塗ります。操作後のマス目は次の通りです。
..#.###... ...#.##... ..#.#..#.# .#.#.#..#. #.#...##.# .#....##.. #.#..#..#.
このうち、上から 2 マス目から 6 マス目、左から 3 マス目から 9 マス目を出力します。その結果は次の通りです。
.#.##.. #.#..#. .#.#..# #...##. ....##.
Problem Statement
There is a grid with 10^9 cells on each side, and all the cells are initially white. The cell in the i-th row from the top and j-th column from the left is called (i,j).
We will perform N operations. The i-th operation is as follows:
- Paint cells in an X shape centered at (P_i,Q_i). More formally, paint the following cells black for all integers k:
- Paint (P_i+k,Q_i+k) black if 1 \le P_i+k \le 10^9 and 1 \le Q_i+k \le 10^9.
- Paint (P_i+k,Q_i-k) black if 1 \le P_i+k \le 10^9 and 1 \le Q_i-k \le 10^9.
Print the subrectangle in the A-th through B-th rows form the top and the C-th through D-th columns from the left in the resulting grid.
Constraints
- All input values are integers.
- 1 \le N \le 2 \times 10^5
- 1 \le P_i, Q_i \le 10^9
- 1 \le A \le B \le 10^9
- 1 \le C \le D \le 10^9
- (B-A+1) \times (D-C+1) \le 2 \times 10^5
Input
The input is given from Standard Input in the following format:
N A B C D P_1 Q_1 P_2 Q_2 \vdots P_N Q_N
Output
Print (B-A+1) lines. The i-th line should be a string of length (D-C+1), whose j-th character is:
.if (A+i-1,C+j-1) is white;#if (A+i-1,C+j-1) is black.
Sample Input 1
3 2 6 3 9 3 5 5 1 4 9
Sample Output 1
.#.##.. #.#..#. .#.#..# #...##. ....##.
The top-left cells initially look like this:
.......... .......... .......... .......... .......... .......... ..........
The first operation paints cells in an X shape centered at (3,5), resulting in the following:
..#...#... ...#.#.... ....#..... ...#.#.... ..#...#... .#.....#.. #.......#.
The second operation paints cells in an X shape centered at (5,1), resulting in the following:
..#.#.#... ...#.#.... ..#.#..... .#.#.#.... #.#...#... .#.....#.. #.#.....#.
The third operation paints cells in an X shape centered at (4,9), resulting in the following:
..#.###... ...#.##... ..#.#..#.# .#.#.#..#. #.#...##.# .#....##.. #.#..#..#.
Print the cells in the 2-th through 6-th rows form the top and the 3-th through 9-th columns from the left, as shown below:
.#.##.. #.#..#. .#.#..# #...##. ....##.