Balanced Bus Route Sign Assignment

A certain city is arranged in a grid. There are \(n+1\) north-south roads and \(n+1\) east-west roads, which partition the city into \(n^2\) blocks (regions) and \((n+1)^2\) intersections. Both the blocks and the intersections are numbered in row‐major order (from top to bottom and from left to right).

The city administration has selected several blocks as tourist destinations. Each tourist block will have exactly one bus route circling its perimeter. The route stops at the four intersections surrounding the block. Note that if two adjacent blocks are both tourist destinations, they share the bus stops along their common border.

There are three bus companies, each imposing a different requirement on the ordering of stop sign numbers along a bus route. A bus route (which is cyclic) is described by the four stop sign numbers at the four intersections on its block. For each route, one is allowed to choose a starting intersection and then traverse the stops in order (either clockwise or counterclockwise, as required) until returning to the starting point. The conditions are:

1. Company A: There must exist a starting stop such that, when taken in clockwise order, the three stops visited (in order) have strictly decreasing sign numbers.
2. Company B: There must exist a starting stop such that, when taken in counterclockwise order, the three stops visited (in order) have strictly decreasing sign numbers.
3. Company C: There must exist a starting stop such that, when taken in clockwise order, the three stops visited have sign numbers which first decrease, then increase, then decrease, then increase (cyclically). [Note: This pattern is imposed on the cyclic order of four stops.]

The government plans to assign sign numbers to the bus stops in all of the \(K\) intersections that are involved with the tourist blocks. The sign numbers are the natural numbers \(1, 2, \dots, K\) (each used exactly once). The goal is to balance the number of valid bus routes for the three companies. Let \(X, Y, Z\) be the number of blocks where the conditions for companies A, B, and C (respectively) are met (each block, if it is a tourist destination, provides one route for a company if its ordering condition is satisfied). The objective is to minimize the quantity:

[ S = (X - Y)^2 + (Y - Z)^2 + (Z - X)^2. ]

Your task is to compute an assignment of sign numbers to the involved intersections. In this problem, you are given the city grid in which tourist blocks are marked. You should assign sign numbers to all intersections that are adjacent to at least one tourist block.

Note: A trivial assignment is acceptable as long as the output meets the format. (In an actual competition, a better assignment may be required to minimize \(S\), but here any valid assignment is accepted.)

inputFormat

The input begins with an integer \(n\) (\(1 \leq n \leq 1000\)), meaning that the city is divided into \(n^2\) blocks by \(n+1\) roads in each direction.

The next \(n\) lines each contain \(n\) integers. Each integer is either 0 or 1. A value of 1 indicates that the corresponding block is chosen as a tourist destination; 0 indicates it is not.

Blocks are given in row‐major order (from top to bottom, and within a row from left to right).

outputFormat

Let \(K\) be the number of intersections (bus stops) that are adjacent to at least one tourist block. First, output \(K\) in a line. Then, output \(K\) lines, each line containing three integers \(r\), \(c\), and \(s\). Here, \(r\) and \(c\) (1-indexed) denote the row and column of an intersection in the city (with intersections arranged in \((n+1)\) rows and \((n+1)\) columns in row‐major order), and \(s\) is the sign number assigned to that intersection. The intersections must be output in row‐major order (from top to bottom, and within a row from left to right) among those that are used (i.e. adjacent to at least one tourist block).

You do not need to actually compute the value of \(S\); any valid complete permutation assignment is accepted.

sample

3
1 0 1
0 1 0
1 0 1

13
1 1 1
1 2 2
1 4 3
2 1 4
2 2 5
2 3 6
2 4 7
3 1 8
3 2 9
3 3 10
3 4 11
4 1 12
4 2 13

</p>