OI题库

问题描述（背景）：

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

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

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

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

任务：

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

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

		笼子
	笼子

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

输入格式(sample.in)：

第一行为自然数n，表示网格的边长(n <= 100)

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

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

以下p行，每行两个自然数Row, Col，表示一个笼子处于网格的第Row行，第Col列。Row <= n Col<= n

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

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

以下r行，每行4个自然数，t, Row, Col, j，表示第t分钟在网格的(Row, Col)位置看到动物j .

具体格式参照样例。

输出格式(smple.out)：

输出任意一个可行解。

包括p行，每行3个整数i Row Col，表示动物i原来在格子(Row,Col)。

输入输出样例：

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