Place-Y Technology Corp. 计划很快发射一个新的空间站。该公司的 CEO 以追求完美而闻名。例如，他坚持要求空间站的所有外表面都必须定期抛光，并清除他所谓的“太空碎片”，主要是为了让空间站在照片中看起来美观。工程团队尝试过但未能说服 CEO 认为这没有必要。因此，他们开发了一种创新技术来维护表面，同时最大限度地减少空间站外的各种人工操作。维护工作由几个在空间站表面移动的小型机器人执行，就像扫地机器人一样。在首次飞行之前，Place-Y 需要评估机器人运行期间的碰撞风险。而这正是你需要介入的地方。

为了解决这个问题，我们将空间站建模为一组轴对齐的单位立方体（不一定连通）。每个机器人在时间 $t = 0$ 时从空间站某个单位立方体的一个暴露面（即未被第二个空间站立方体共享的面）的中心开始。机器人面向平行于立方体面边缘的四个方向之一。每个时间单位，机器人都会径直向前移动到另一个立方体面，并可能沿着空间站边缘旋转 90 度，以便始终保持与空间站的接触。注意，如果两个立方体共享一条边，机器人无法从它们之间滑过（没有间隙）。

图 K.1：样例输入 1 的示意图。点表示两个机器人的起始位置。

给定空间站的布局和所有清洁机器人的起始位置，确定最早发生碰撞的时间（如果有）。碰撞发生的时间要么是两个或多个机器人在同一立方体面的内部的时间单位，要么是两个机器人试图交换位置的时间单位（参见样例输入 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_1 \le x \le x_2, y_1 \le y \le y_2, z_1 \le z \le z_2$ 的所有点都是空间站的一部分。注意，某些单位立方体可能包含在多个区域中。

随后是 $k$ 行，每行描述一个机器人的起始位置。该行包含三个坐标 $x, y, z$ 以及两个方向 $f$ 和 $d$。坐标指定机器人从单位立方体 $(x, y, z) - (x + 1, y + 1, z + 1)$ 的一个面开始。特定的面由 $f$ 确定，初始移动方向由 $d$ 确定。$f$ 和 $d$ 均由六个字符串之一指定：x+, x-, y+, y-, z+ 或 z-，其中 x+ 表示 x 轴的正方向 $(1, 0, 0)$，依此类推。$f$ 中的轴字母将与 $d$ 中的轴字母不同。保证起始立方体属于空间站，且给定的面是一个暴露面。

输出格式

输出第一次碰撞的时间。如果永远不会发生碰撞，则输出 ok。

样例

样例输入 1

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+

样例输出 1

44

样例输入 2

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

样例输出 2

ok

样例输入 3

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

样例输出 3

0