C

Save the President Input: Standard Input Output: Standard Output

You have to save the president, who is now living in a very dangerous world. Helps are coming as members of the elite force are on the way, but till then you must save him and take him to a place that is secured for sometime. As a programmer and scientist you have some means that are unique (No other person can achieve): You can travel through hyperspace- (a) Reach the same location at a different time (b) Reach a different place at the same time (c) Reach a different place at a different time. So you can save the President in situations where others have no hope. But like the elite force you cannot defuse any bomb or use some protective shield to save the President.

To make things simple you can assume that your world is a three dimensional grid as shown in figure 1.

Figure 1: The world can be viewed as a three dimensional grid.	Figure 2: An object in 3 dimensional space. The corner nearest to the origin has coordinate (p,q,r) and the corner farthest from the origin has coordinate

In this three dimensional space objects are placed in axis parallel positions and for simplicity all the objects are box shaped and have integer dimensions and all the eight corners of the box have integer coordinates (In three dimensional Cartesian coordinate system) when placed. So if the object has a dimension (That is the dimension of the box along x, y and z axis is , and respectively) and if coordinate of its nearest to the origin ((0,0,0)) corner is (p, q, r) then the coordinate of the corner which is farthest from the origin would be .

But many bombs have also been placed in this three dimensional world which are causing security problems for the president. Given the dimensions of the three dimensional world, and the position and possible explosion time range of the bombs, you have to find total number of safe time and space positions (The coordinate of the location and the time when the coordinate is safe) for the president for a given duration.

Input

The input file contains at most 5 sets of inputs. The description of each set is given below.

Each case starts with five positive integers N, dimx, dimy dimz, Q. 
Here N (0<N<2500) is the total number of bombs in the grid. 
The integers dimx, dimy, dimz (0 ≤ dimx, dimy, dimz ≤ 18) denote that 3D world you are considering can be viewed as a three dimensional grid. 
Q (Q ≤ 5) is the total number security queries to follow after the bomb descriptions. 

Next N lines describe N bombs. 
Each bomb description consists six non negative integers  and two strings of the format hour:minute. 
The two strings denote the time span when the bomb can explode. 
The time is written in 24 hour clock format but the only exception is 24:00 which denotes the end of the day. and the minute part is always a multiple of 15. 
The six integer  denotes that the bomb explodes within the box area denoted by the two corners  and . 
For example the description of the first bomb is given by the line 
 
0 0 4 1 1 6 23:15 24:00
 

This means that when the bomb explodes it can destroy anything within the box whose two corners are (0,0,4) (The corner nearest to the origin) and (1,1,6) (The corner farthest from the origin). And this bomb can explode at any time between 23:15 and 24:00 (inclusive). So any point within this box is unsafe between 23:15 and 24:00. At other times this location is safe if not threatened by other bombs.

Each of the next Q lines describes a security query. The first three integers denote the minimum 3D dimension required by the president to survive. These three integers are followed by a string which denotes the time length for which the president must be kept secured. This time length is also always multiple of 15 minutes. Let is time length be T. Note that everything happens in a single day. So if you are supposed to keep the president secured for 30 minutes, you cannot keep him secured for 15 minutes today and 15 minutes after midnight.

Input is terminated by a line containing five zeroes.

Output

For each set input produce Q+1 lines of outputs. The first line is the serial of output. Each of the next lines is the output for one query. This line is of the format “N safe places found”. Here N is the total number of location and times where you can take the president to keep him safe for time length T. Please note again that to keep the president safe for time length T you can jump to another 3D location (Denoted by the coordinate of the nearest to origin point) and even go to a different time and 3D location for safety. After reaching there your goal is to stay safe for time T without moving or traveling through time. If no safe place is found print “No safe place(s) found” instead.

Look at the output for sample input for formatting details.

Sample Input Output for Sample Input

10 6 7 6 2 0 0 4 1 1 6 23:15 24:00 1 2 1 3 3 2 23:30 24:00 3 2 0 4 4 1 16:15 16:45 2 5 0 3 7 2 07:15 09:45 4 3 4 5 4 6 09:30 10:45 2 5 2 4 6 4 16:00 17:00 2 4 0 4 6 1 08:00 08:30 2 3 4 4 5 5 14:30 17:00 0 4 4 2 5 5 14:15 15:45 2 0 3 4 2 5 02:30 03:45 1 6 3 03:15 5 2 3 00:15 0 0 0 0 0

3D World 1: 2539 safe place(s) found 3831 safe place(s) found

---

Problemsetter: Shahriar Manzoor, Special Thanks: Rujia Liu, Abdullah al Mahmud.