You want to arrange people at a table. The table has rows and columns. Some of the cells are free and some of them are blocked.
The score of the arrangement is based on two factors:
Your task is to print an arrangement with as high a score as possible. Note that you can drop a person and do not give him a seat at the table.
Input format
Output format
Print lines. In each line, print the row and column of the person in the arrangement. Otherwise, print "0 0" if you do not want to include this person in the arrangement.
Constraints
Note that the output is not necessarily the best solution.
The first two persons create a component, the sum of equals 3, so it adds 9 to the score.
The third one creates a component with size 1 and sum 3, adds 9 to the score.
The first two persons are adjacent, which decreases the score by 20.
The total score is -2.