题目描述

给定一些建筑物和防空洞的位置、容量以及初始分配方案，判断该方案是否为最优（即所有人移动到防空洞的总距离最小）。若不是最优，输出一个更优的方案；若是最优，输出 "OPTIMAL"。输入格式第一行：两个整数 N（建筑物数量）和 M（防空洞数量）。接下来 N 行：每行三个整数 $X_i, Y_i, B_i$，表示第 i 个建筑物的坐标和人数。接下来 M 行：每行三个整数 $P_j, Q_j, C_j$，表示第 j 个防空洞的坐标、容量。最后 N 行：每行 M 个整数 $E_{i,j}$，表示从建筑物 i 分配到防空洞 j 的人数（初始方案）。输出格式若初始方案非最优，输出 "SUBOPTIMAL"，并按输入顺序输出调整后的 $E_{i,j}$ 矩阵（每个建筑物对应的行用空格分隔，行末无多余空格）。若初始方案最优，输出 "OPTIMAL"。

样例输入

3 4

-3 3 5

-2 -2 6

2 2 5

-1 1 3

1 1 4

-2 -2 7

0 -1 3

3 1 1 0

0 0 6 0

0 3 0 2

样例输出

plaintextSUBOPTIMAL
3 0 1 1

0 0 6 0

0 4 0 1