Magic Laser: Light the lights!

Time Limit: 10 Seconds Memory Limit: 32768 KB
Special Judge

Figure 1. Magic Laser Game

"Magic Laser" is really a funny game and now Riveria is addicted to it very much. The game happens on a plane map with height H and width W. There are some laser beams in this map, also some lights. The goal is to light all lights in the map with the ray of laser beams. The only tool you can use are some mirrors that can reflect all the rays.

Unfortunatly, the problem is not so easy. Each light requires a specific color of ray and each laser beam could only provide a ray with one kind of color. It makes the game quite difficult, which confounded Riveria a lot. He knows you are an expert on programming. So he comes to ask you for a programming solution for the game.

Some constraints you should know about the game:

1. There are some hills in the map which stops all the coming laser. At some locations, there are magic stones, which only could be gone through in one line and stop all other directions of coming laser.

2. There are two sorts of mirrors, one could change the direction of laser by 90, 180 or 270 degree, the other could change by 45, 135, 225, 315 degree (clockwise). The number of mirrors are limited.

3. All the colors could be decomposed into three element colors: red, green and blue. So we can treat each color as a 3-dimension vector (r, g, b) (r,g,b=0 or 1). Each laser beam has only one element color, but this condition does not fit in lights. There is only one beam of one element color at most.

4. A light cannot be lighted if an extra laser went through it. For example, if a light needs the red color but a red laser and a blue laser has gone through it, it will not be lighted.

5. A mirror could only change one direction of coming laser to a specific direction (Of course, the optical path is reversible.). All other directions will stop here. Similarly, you can treat a laser beam as a hill, which stops all the coming laser.

6. There could not be more than two things (hills, magic stones, lights, lazer beams or mirrors) at the same place. In the input, we assure that all the lights and beams are placed in spaces.

7. All the coordinates start from 1. Most parts of a map are spaces.

8. We assume that the up direction is direction 1, and then 2, 3, ..., 8 clockwise.

Directions

Input

The first line are two integers h and w (2<=h,w<=15), which means the height and width of the map. Then h lines follows, each line stands w characters, describing the map. A '.' represents a space and a '*' means a hill. A digit with value '1'-'4' represents a magic stone. The value means the direction of rays that allowd to go through this stone. '1' means the direction of 1 and 5, '2' means 2 and 6, and so on. (Remember that the optical path is reversible)

A number S (1<=S<=3) follows, which represents the number of lazer beams. Then S lines follows each contains 6 integers. The first three integer (r,g,b) is the color vector. (r,g,b=0 or 1) We assure that there is only one '1' in the vector. The fourth integer represents the direction of the beam's ray (1<=direction<=8). The last two (row, column) is the coordinate of the beam.

At the next there is a integer L (1<=L<=15) then L lines follows, which describe the situation of L lights in the map. In Each line there are 5 integers. The first three is the color vector (r,g,b) (r,g,b=0 or 1) which means the colors it requires and the last two is the coordinate.

At last there are two non-negative integers n1 and n2 (1<=n1+n2<=11), represents the numbers of each kind of mirros. (There are n1 mirrors could change the direction by 90, 180 and 270 degree)

Proceed to the end of file.

Output

At the beginning output a number m, the number of mirrors you have used. Then m lines follows, each contains 4 integers: row, column, in_dir and out_dir, which represents the location of mirror (row, column) and the directions of coming ray and reflected ray. (Never forget that the optical path is reversible.)

If there are more than one solutions, any one is acceptable. We insure that it has a solution.

Figure 2. Solutions for the samples

Sample Input

15 15
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
1
1 0 0 3 9 3
1
1 0 0 4 8
1 0
15 15
***************
*.............*
*.............*
*.............*
*.............*
*.............*
*.............*
*.............*
*.............*
*.............*
*.............*
*.............*
*.............*
*.............*
***************
2
1 0 0 5 2 4
0 0 1 5 2 11
4
1 0 0 11 6
1 0 0 5 12
0 0 1 4 8
0 0 1 6 5
0 3

Sample Output

Submit

Source: ZOJ Monthly, December 2004