#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int maxn=1000;const int INF=0x3f3f3f3f;struct Edge{ int to,next,cap,flow,cost;}edge[maxn*maxn];int Adj[maxn],Size,N;void init(){ Size=0; memset(Adj,-1,sizeof(Adj));}void addedge(int u,int v,int cap,int cost){ edge[Size].to=v; edge[Size].next=Adj[u]; edge[Size].cost=cost; edge[Size].cap=cap; edge[Size].flow=0; Adj[u]=Size++;}int Add_Edge(int u,int v,int cap,int cost){ addedge(u,v,cap,cost); int tk=Size-1; addedge(v,u,0,-cost); return tk;}int dist[maxn],vis[maxn],pre[maxn];bool spfa(int s,int t){ queue<int> q; for(int i=0;i<N;i++) { dist[i]=INF; vis[i]=false; pre[i]=-1; } dist[s]=0; vis[s]=true; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; for(int i=Adj[u];~i;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap>edge[i].flow&& dist[v]>dist[u]+edge[i].cost) { dist[v]=dist[u]+edge[i].cost; pre[v]=i; if(!vis[v]) { vis[v]=true; q.push(v); } } } } if(pre[t]==-1) return false; return true;}int MinCostMaxFlow(int s,int t,int &cost){ int flow=0; cost=0; while(spfa(s,t)) { int Min=INF; for(int i=pre[t];~i;i=pre[edge[i^1].to]) { if(Min>edge[i].cap-edge[i].flow) Min=edge[i].cap-edge[i].flow; } for(int i=pre[t];~i;i=pre[edge[i^1].to]) { edge[i].flow+=Min; edge[i^1].flow-=Min; cost+=edge[i].cost*Min; } flow+=Min; } return flow;}int n,m;struct PT{ int x,y,c;}Build[maxn],She[maxn];int Dist[maxn][maxn],mp[maxn][maxn],liu[maxn][maxn];int main(){ while(scanf("%d%d",&n,&m)!=EOF) { init(); for(int i=1;i<=n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); Build[i]=(PT){a,b,c}; } for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); She[i]=(PT){a,b,c}; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { Dist[i][j]=abs(Build[i].x-She[j].x)+abs(Build[i].y-She[j].y)+1; int t=Add_Edge(i,n+j,INF,Dist[i][j]); mp[i][j]=t; } } for(int i=1;i<=n;i++) { Add_Edge(0,i,Build[i].c,0); } for(int i=1;i<=m;i++) { Add_Edge(i+n,n+m+1,She[i].c,0); } N=n+m+2; int flow,cost; flow=MinCostMaxFlow(0,n+m+1,cost); int C=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&liu[i][j]); C+=liu[i][j]*Dist[i][j]; } } if(C==cost) { puts("OPTIMAL"); } else { puts("SUBOPTIMAL"); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { printf("%d%c",edge[mp[i][j]].flow,(j!=m)?' ':'n'); } } } } return 0;}
