Space Walls

Place-Y Technology Corp. plans to launch a new space station soon. The company CEO is known for being obsessed with perfection. For example, he insists that all the outer surfaces of the space station are regularly polished and cleaned of what he calls "space debris," mainly so the station looks good in photos. The engineering team tried to convince the CEO that this was not needed, but failed. So instead they developed a new technology that maintains the surfaces while minimizing human work outside the station. Several small robots perform the maintenance by moving over the station surface, much like robotic vacuum cleaners. Before the first flight, Place-Y needs to assess the risk of collisions during robot operation. That is where you come in.

In this problem, the space station is modeled as a collection of axis-aligned unit cubes. The cubes do not need to be connected. Each robot starts at time $t = 0$ at the center of an exposed face of one of the station's unit cubes. An exposed face is a face that is not shared with another station cube. The robot faces one of the four directions parallel to an edge of that face. Every time unit, the robot moves straight ahead to another cube face. It may pivot 90 degrees across a station edge so that it always stays in contact with the station. If two cubes share an edge, the robot cannot pass between them, because there is no gap.

Figure K.1: Illustration of Sample Input 1. The dots mark the starting points of two robots.

Given the station layout and the starting positions of all robots, find the time of the earliest collision, if any. A collision happens at a time unit when two or more robots are inside the same cube face, or when two robots try to swap locations. See Sample Input 3 for the swap case.

The first line contains two integers $n$ and $k$. Here $n$ ($1 \le n \le 100$) is the number of regions that describe the station shape, and $k$ ($0 \le k \le 100$) is the number of robots.

Each of the next $n$ lines contains six integers $x_1$, $y_1$, $z_1$, $x_2$, $y_2$, and $z_2$ with $0 \le x_1 < x_2 \le 10^6$, $0 \le y_1 < y_2 \le 10^6$, and $0 \le z_1 < z_2 \le 10^6$. Each line describes one region. Every point $(x, y, z)$ with $x_1 \le x \le x_2$, $y_1 \le y \le y_2$, and $z_1 \le z \le z_2$ belongs to the station. A unit cube may be covered by more than one region.

Each of the next $k$ lines gives the starting position of one robot. The line contains coordinates $x$, $y$, $z$, and two directions $\overrightarrow{f}$ and $\overrightarrow{d}$. The robot starts on the face of the unit cube $(x, y, z)$-$(x+1, y+1, z+1)$ determined by $\overrightarrow{f}$. Its initial direction of movement is $\overrightarrow{d}$. Each direction is one of the strings x+, x-, y+, y-, z+, or z-. For example, x+ means the positive x-axis direction $(1, 0, 0)$. The axis letters of $\overrightarrow{f}$ and $\overrightarrow{d}$ are always different. The starting cube belongs to the station, and the given face is exposed.

Print the time of the first collision. If no collision ever happens, print ok.