题目描述

给定一个 $k×k$ 的图形，每个位置为黑色或白色。

给定一个 $n×m$ 的网格，初始全为白色。

有 $q$ 次操作，每次操作会以 $(x,y)$ 为中心，将 $k×k$ 的图形叠加在当前的网格之上，即对于所有图形中的黑色位置，使网格的对应位置被染黑。

求出依次执行 $q$ 次操作后得到的网格。

输入格式

从文件 $vision.in$ 中读入数据。

第一行四个整数 $n,m,k,q$，分别表示网格的边长、图形的边长与操作次数。

接下来 $k$ 行，每行一个长度为 $k$ 的字符串，表示给定图形。其中 . 表示空，# 表示黑色。

接下来 $Q$ 行，每行两个正整数 $x,y$，表示以 $(x,y)$ 为中心的一次图形叠加。

输出格式

输出到文件 $vision.out$ 中。

共 $n$ 行，每行一个长度为 $m$ 的字符串，表示叠加得到的图形，格式与输入一致。

样例输入

10 10 5 5
.###.
#...#
#.#.#
#...#
.###.
1 1
2 2
5 5
5 9
10 5

样例输出

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

数据范围与提示

对于所有测试数据，保证 $1 ≤ n,m ≤ 1000，1 ≤ k ≤ 15，2 ∤ k，1 ≤ Q ≤ 10^4，1 ≤ x ≤ n， 1 ≤y ≤m$。