题目描述

Place-Y 科技有限公司计划近期发射一个新的空间站。这个公司的 CEO 以其对完美的痴迷而为人所知。例如，他坚持空间站的所有外表面都要定期抛光和清理他所谓的「空间碎片」，主要是为了空间站在照片里显得好看。这种维护由一些在空间站外表面工作的小机器人进行，这些小机器人就像扫地机器人一样。在首次飞行前，Place-Y 需要评估机器人在工作时相撞的风险。这就是你需要介入的事情了。

为了本题需要，我们将空间站建模成一些平行于坐标轴的单位立方体集合（不一定是连通的）。每个机器人从时刻 $t=0$ 开始，从某个空间站的单位立方体暴露在外的面（这指的是不和第二个空间站所属的单位立方体共享的面）开始运动。机器人面向平行于立方体表面的四条边所指的四个方向之一。每个单位时间，机器人总会前进到另一个立方体表面，也可能沿空间站的某条边旋转 $90$ 度，以保持始终和空间站表面接触。注意如果两个立方体共用一条边，机器人是无法从它们之间滑落的（两个立方体间没有空隙）。

给出空间站的形状和所有清洁机器人的其实位置，确定最早可能发生碰撞的时间（如果存在的话）。一次碰撞发生的时间是指当两个或以上机器人在这个时刻处于同样一个立方体表面或当两个机器人试图交换位置的时刻（后者情况可参考样例 3）。

输入格式

输入第一行包含两个整数 $n$ 和 $k$，其中 $n\ (1\le n\le 100)$ 是描述空间站形状的立方体个数，$k\ (0\le k\le 100)$ 是表面上机器人的个数。

接下来 $n$ 行，每行包含六个整数坐标 $x_1,y_1,z_1,x_2,y_2,z_2\ (0 \le x_1 < x_2 \le 10^6, 0 \le y_1 < y_2 \le 10^6, 0 \le z_1 < z_2 \le 10^6)$，描述一个立方体区域，并且表示所有点 $x,y,z$ 满足 $x_1\le x\le x_2,y_1\le y\le y_2,z_1\le z\le z_2$ 都是空间站的一部分。注意一些单位立方体可能会被多于一个区域所包含。

接下来 $k$ 行，每行描述一个机器人的起始坐标。每行包含三个整数坐标 $x,y,z$ 和两个方向 $\vec f$ 和 $\vec d$。这个坐标表示机器人从单位立方体 $(x,y,z) - (x+1,y+1,z+1)$ 的表面开始运动。这个特定的表面由 $\vec f$ 确定，初始的运动方向由 $\vec d$ 确定。$\vec f$ 和 $\vec d$ 由以下六个字符串之一确定：$\texttt{x+},\texttt{x-},\texttt{y+},\texttt{y-},\texttt{z+},\texttt{z-}$。其中 $\texttt{x+}$ 代表 $x$ 轴的正方向 $(1,0,0)$，以此类推。$\vec f$ 中代表轴的字母会和 $\vec d$ 中代表轴的字母不同。保证起点所在的立方体属于空间站，给定的面是暴露在外的面。

输出格式

输出第一次碰撞出现的时间。如果永远不会发生碰撞，输出 $\texttt{ok}$。

9 2
1 1 1 7 7 7
0 0 0 3 3 3
5 0 0 8 3 3
0 5 0 3 8 3
0 0 5 3 3 8
5 5 0 8 8 3
5 0 5 8 3 8
0 5 5 3 8 8
5 5 5 8 8 8
0 1 0 z- x+
3 5 1 z- y+

44

1 3
0 0 0 1 1 1
0 0 0 x+ z+
0 0 0 y+ x+
0 0 0 z- y+

ok

1 2
0 0 0 2 1 1
0 0 0 y+ x+
1 0 0 y+ x-

0