/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 266 点
問題文
高橋君は文化祭でスタンプラリーの係をしています。来場者には H 行 W 列のマス目が描かれた台紙が配られます。台紙の行には上から順に 1 から H の番号が、列には左から順に 1 から W の番号が付いています。最初、台紙のすべてのマスは .（空白）です。
スタンプラリーで使うスタンプは R 行 C 列のグリッドで表されます。スタンプの各マスは #（インクが付く部分）または .（インクが付かない部分）のいずれかです。スタンプの行にも上から順に 1 から R の、列にも左から順に 1 から C の番号が付いています。スタンプの第 i 行は文字列 S_i で表されます。
高橋君はある来場者の台紙に、同じスタンプを合計 N 回押します。j 回目（1 \leq j \leq N）のスタンプ押しは、整数の組 (r_j, c_j) で指定されます。ここで r_j および c_j は任意の整数であり、0 以下の値や台紙のサイズを超える値を取ることもあります。
(r_j, c_j) の意味は次の通りです。スタンプの第 1 行第 1 列（左上隅）が台紙の第 r_j 行第 c_j 列の位置に対応するようにスタンプを配置します。すなわち、スタンプの第 a 行第 b 列（1 \leq a \leq R, 1 \leq b \leq C）は、台紙の第 (r_j + a - 1) 行第 (c_j + b - 1) 列に対応します。
スタンプを押すと、スタンプの各マス（第 a 行第 b 列）について以下の処理が行われます。
- 対応する台紙上の位置 (r_j + a - 1,\; c_j + b - 1) が台紙の範囲外である場合、すなわち r_j + a - 1 < 1 または r_j + a - 1 > H または c_j + b - 1 < 1 または c_j + b - 1 > W のとき、そのマスは無視されます。
- 対応する台紙上の位置が台紙の範囲内であり、かつスタンプ上のそのマスが
#であるとき、台紙上の対応するマスを#に変更します（すでに#であればそのままです）。 - 対応する台紙上の位置が台紙の範囲内であり、かつスタンプ上のそのマスが
.であるとき、台紙上の対応するマスには何も変化を与えません。
N 回すべてのスタンプを押した後の台紙の最終的な状態を出力してください。
制約
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- 1 \leq R \leq 100
- 1 \leq C \leq 100
- S_i は
#と.からなる長さ C の文字列である（1 \leq i \leq R） - 1 \leq N \leq 1000
- -10^4 \leq r_j \leq 10^4（1 \leq j \leq N）
- -10^4 \leq c_j \leq 10^4（1 \leq j \leq N）
- 入力で与えられる値はすべて整数である（文字列を除く）
入力
H W R C S_1 S_2 \vdots S_R N r_1 c_1 r_2 c_2 \vdots r_N c_N
- 1 行目には、台紙の行数 H と列数 W がスペース区切りで与えられる。
- 2 行目には、スタンプの行数 R と列数 C がスペース区切りで与えられる。
- 続く R 行にわたって、スタンプの形状が与えられる。(2 + i) 行目（1 \leq i \leq R）には、スタンプの第 i 行の形状を表す文字列 S_i が与えられる。
- (3 + R) 行目には、スタンプを押す回数 N が与えられる。
- 続く N 行には、各スタンプ押しの位置が与えられる。(3 + R + j) 行目（1 \leq j \leq N）には、j 回目のスタンプ押しにおけるスタンプ左上隅の位置を表す整数 r_j（行番号）と c_j（列番号）がスペース区切りで与えられる。
出力
N 回のスタンプ押し後の台紙の状態を H 行で出力せよ。i 行目（1 \leq i \leq H）には、台紙の第 i 行の状態を # と . からなる長さ W の文字列として出力する。
入力例 1
5 5 2 2 #. .# 2 1 1 3 3
出力例 1
#.... .#... ..#.. ...#. .....
入力例 2
7 7 3 3 .#. ### .#. 3 1 1 5 5 0 -1
出力例 2
##..... ###.... .#..... ....... .....#. ....### .....#.
入力例 3
10 10 4 4 .##. #### #### .##. 4 -1 -1 2 7 8 3 1 1
出力例 3
###....... ####...##. ####..#### .##...#### .......##. .......... .......... ...##..... ..####.... ..####....
Score : 266 pts
Problem Statement
Takahashi is in charge of a stamp rally at a cultural festival. Visitors are given a sheet with an H \times W grid. The rows of the sheet are numbered 1 to H from top to bottom, and the columns are numbered 1 to W from left to right. Initially, all cells on the sheet are . (blank).
The stamp used in the stamp rally is represented by an R \times C grid. Each cell of the stamp is either # (inked part) or . (non-inked part). The rows of the stamp are numbered 1 to R from top to bottom, and the columns are numbered 1 to C from left to right. The i-th row of the stamp is represented by the string S_i.
Takahashi stamps a visitor's sheet a total of N times using the same stamp. The j-th stamping (1 \leq j \leq N) is specified by a pair of integers (r_j, c_j). Here, r_j and c_j can be any integers, including values that are 0 or less, or values that exceed the size of the sheet.
The meaning of (r_j, c_j) is as follows: the stamp is placed so that row 1, column 1 (the top-left corner) of the stamp corresponds to row r_j, column c_j of the sheet. That is, row a, column b of the stamp (1 \leq a \leq R, 1 \leq b \leq C) corresponds to row (r_j + a - 1), column (c_j + b - 1) of the sheet.
When the stamp is pressed, the following processing is performed for each cell (row a, column b) of the stamp:
- If the corresponding position on the sheet (r_j + a - 1,\; c_j + b - 1) is outside the sheet, i.e., r_j + a - 1 < 1 or r_j + a - 1 > H or c_j + b - 1 < 1 or c_j + b - 1 > W, that cell is ignored.
- If the corresponding position on the sheet is within bounds and the stamp cell is
#, the corresponding cell on the sheet is changed to#(if it is already#, it remains unchanged). - If the corresponding position on the sheet is within bounds and the stamp cell is
., no change is made to the corresponding cell on the sheet.
Output the final state of the sheet after all N stampings have been performed.
Constraints
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- 1 \leq R \leq 100
- 1 \leq C \leq 100
- S_i is a string of length C consisting of
#and.(1 \leq i \leq R) - 1 \leq N \leq 1000
- -10^4 \leq r_j \leq 10^4 (1 \leq j \leq N)
- -10^4 \leq c_j \leq 10^4 (1 \leq j \leq N)
- All given values are integers (except for strings)
Input
H W R C S_1 S_2 \vdots S_R N r_1 c_1 r_2 c_2 \vdots r_N c_N
- The first line contains the number of rows H and number of columns W of the sheet, separated by a space.
- The second line contains the number of rows R and number of columns C of the stamp, separated by a space.
- The following R lines give the shape of the stamp. The (2 + i)-th line (1 \leq i \leq R) contains the string S_i representing the shape of the i-th row of the stamp.
- The (3 + R)-th line contains the number of stampings N.
- The following N lines give the position of each stamping. The (3 + R + j)-th line (1 \leq j \leq N) contains the integers r_j (row number) and c_j (column number) representing the position of the top-left corner of the stamp for the j-th stamping, separated by a space.
Output
Output the state of the sheet after N stampings in H lines. The i-th line (1 \leq i \leq H) should contain a string of length W consisting of # and . representing the state of the i-th row of the sheet.
Sample Input 1
5 5 2 2 #. .# 2 1 1 3 3
Sample Output 1
#.... .#... ..#.. ...#. .....
Sample Input 2
7 7 3 3 .#. ### .#. 3 1 1 5 5 0 -1
Sample Output 2
##..... ###.... .#..... ....... .....#. ....### .....#.
Sample Input 3
10 10 4 4 .##. #### #### .##. 4 -1 -1 2 7 8 3 1 1
Sample Output 3
###....... ####...##. ####..#### .##...#### .......##. .......... .......... ...##..... ..####.... ..####....