题目描述

位于郊区的动物园很早就采用了当时先进的自动化管理设施对动物进行管理。但是由于当时的系统没有考虑 $2000$ 年问题，使得管理人员十分担心。虽然采取了很多防范措施，系统还是在世纪之交出现了一些 BUG，部分动物的笼子门自动打开了，关在里面的动物都跑出来了。

幸好动物园已经关闭，动物不会跑出动物园。警长 Still 接到报警后率领一支干警奔赴现场。这时动物已经跑出了笼子，所以干警们花了很多时间才控制住了局势，所有的动物都己经送到动物园的广场。但是此时有一个棘手的问题，由于系统完全崩溃，无法得知动物是从哪个笼子里面跑出来的。此时，干警们记得动物的一些行动，都是如下的形式：

第 $t$ 分钟看到某某动物在某个位置。

Still 希望通过这些零碎的信息得到动物是从哪个笼子跑出来的。

任务

根据给出的信息，编程求出每个动物的笼子的位置。

动物园的地形描述为一个 $n\times n$ 的网格，一个格子可以是建筑物或者平地。笼子的位置只可能在平地，动物也只在平地运动。每种动物的奔跑速度不一样，例如老虎一分钟可以跑 $5$ 个格子，猫一分钟只可以跑 $2$ 个格子等等。以下是一个例子（其中阴影部分是建筑物）：

每个笼子只关一只动物，不同的笼子关不同的动物。不同的笼子可能在同一个格子里。

输入格式

第一行为自然数 $n$，表示网格的边长

以下 $n$ 行为一个 $n\times n$ 的字符串矩阵，表示动物园的地形。其中 . 表示空地，* 表示建筑物。

接着一行是自然数 $p$，表示笼子的数目（同时也是动物的数目）。

以下 $p$ 行，每行两个自然数 $R,C$，表示一个笼子处于网格的第 $R$ 行，第 $C$ 列。

以下 $p$ 行，每行一个整数 $V_i$，依次表示编号为 $i$ 的动物的速度（格子/分钟），每个动物用它的编号表示。

接着一行是自然数 $r$，表示干警们提供的信息数目。

以下 $r$ 行，每行四个自然数，$t,x, y, j$，表示第 $t$ 分钟在网格的 $(x, y)$ 位置看到动物 $j$。

具体格式参照样例。

输出格式

输出任意一个可行解。

包括 $p$ 行，每行三个整数 $i,x,y$，表示动物 $i$ 原来在格子 $(x,y)$。

5
.....
.***.
.....
.***.
.....
2
1 3
5 2
1
2
2
5 3 1 2
4 5 5 1

1 5 2
2 1 3

提示

$1\leq n,p\leq 100$，$x,y\leq n$。

注：对于特定的数据可能有多解，输出任意一解即可。