Description

有$N$幢大楼和$M$个避难所。第$i$大楼的坐标为$(X_i,Y_i)$，有$B_i（1≤B_i≤1000）$个人在里面工作，第$i$个避难所的容纳人数为$C_i$。位于$(X_i,Y_i)$的大楼和位于$（P_j,Q_j）$的避难所之间的时间为$D_i,j=|X_i-P_j|+|Y_i-Q_j|+1$分钟。在理想情况下，某一大楼的所有工人都应跑向最近的避难所。然而，这将导致一些避难所过度拥挤，另一些避难所半空。为了解决这个问题，市议会制定了一个疏散计划，在该计划中指定了应该从大楼i到避难所j避难的人数$E_{ij}$。判断所有人避难的所有时间的总和是不是最小。

Format

Input

第$1$行包含两个数字$N$和$M（1≤N，M≤100）$。

下面的$N$行，每行都包含整数$Xi、Yi$和$Bi$，其中$X_i、Y_i（-1000≤X_i,Y_i≤1000）$是大楼的坐标，$B_i（1≤Bi≤1000）$是该大楼的工人人数。

后面的$M$行，每行都包含三个整数$P_j、Q_j$和$C_j$，其中$Pi、Qi（-1000≤P_j，Q_j≤1000）$是避难所的坐标，$C_j（1≤Cj≤1000）$是该避难所的容量。

市议会疏散计划的描述包括$N$行。每行都代表一个大楼的疏散计划（按照城市描述中给出的顺序）。第$i$个大楼的疏散计划包含$M$个整数$E_{ij}（0≤E_{ij}≤1000）$，表示从第$i$个大楼疏散到第$j$个避难所的工人人数。输入文件中的计划保证有效。

Output

若市议会的计划是最优的，则给输出写一个单词“$OPTIMAL$”；否则在第$1$行输出“$SUBOPTIMAL$”；然后是$N$行，用与输入文件相同的格式描述计划。你的计划自身不一定是最优的，但必须是有效的，比市议会的计划更好。

Samples

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

SUBOPTIMAL
3 0 1 1
0 0 6 0
0 4 0 1

来源

POJ2175