Evacuation Plan
In the city, there are municipal buildings and bomb shelters designed for evacuating employees in the event of a nuclear war. Each bomb shelter has a limited capacity for the number of people it can accommodate. Ideally, all workers from a municipal building should head to the nearest bomb shelter. However, this could lead to some shelters being overcrowded while others remain underutilized.
To address this, the City Council has developed a special evacuation plan. Instead of assigning each employee to a specific bomb shelter, they have determined how many employees from each municipal building should go to each bomb shelter. The task of distributing employees individually is left to the internal management of the municipal buildings.
The evacuation plan considers the number of employees in each building, ensuring that every employee is accounted for and that no bomb shelter exceeds its capacity.
The City Council claims that their evacuation plan is optimal, meaning it minimizes the total evacuation time for all city employees.
The city mayor, who often disagrees with the City Council, is skeptical of this claim. He has hired you as an independent expert to verify the evacuation plan. Your task is to either confirm the optimality of the City Council's plan or demonstrate otherwise by providing an alternative evacuation plan with a shorter total evacuation time for all employees.
The city map is represented as a square grid. The locations of municipal buildings and bomb shelters are given by pairs of integers, and the evacuation time from a municipal building at coordinates (X_i, Y_i) to a bomb shelter at coordinates (P_j, Q_j) is calculated as Dij = |X_i-P_j| + |Yi-Q_j| + 1 minutes.
Input
The input file describes the city map and the evacuation plan proposed by the City Council. The first line contains two integers N (1 ≤ N ≤ 100) and M (1 ≤ M ≤ 100), separated by a space. N is the number of municipal buildings (numbered from 1 to N), and M is the number of bomb shelters (numbered from 1 to M).
The next N lines describe the municipal buildings. Each line contains integers X_i, Y_i, and B_i, separated by spaces, where X_i, Y_i (-1000 ≤ X_i, Y_i ≤ 1000) are the coordinates of the buildings, and B_i (1 ≤ B_i ≤ 1000) is the number of employees in the building.
The following M lines describe the bomb shelters. Each line contains integers P_j, Q_j, and C_j, separated by spaces, where P_j, Q_j (-1000 ≤ P_j, Q_j ≤ 1000) are the coordinates of the bomb shelter, and C_j (1 ≤ C_j ≤ 1000) is the capacity of the bomb shelter.
The next N lines provide the evacuation plan. Each line corresponds to a specific building's evacuation plan and consists of M integers E_ij, separated by spaces. E_ij (0 ≤ E_ij ≤ 10000) indicates the number of employees evacuating from the i-th building to the j-th bomb shelter.
It is guaranteed that the plan provided in the input file is correct.
Output
If the City Council's evacuation plan is optimal, output the single word OPTIMAL. Otherwise, output the word SUBOPTIMAL on the first line, and in the next N lines, provide your improved evacuation plan in the same format as the input file. Your plan does not need to be optimal, but it should be better than the City Council's plan.