Cloud Movement Planning

You are the God of Wind. In a 4×4 country labeled from 1 to 16 as shown below, you control a 2×2 cloud. The cloud, when placed over an area, makes it rain; all other areas receive sunshine.

On the first day the cloud is fixed at the central areas (cells 6, 7, 10, 11), i.e. with top‐left coordinate (2,2) if the grid is viewed as follows:

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

From day 2 onward, at the beginning of each day you may move the cloud in one of the four cardinal directions (North, South, West, East) by 1 or 2 squares, or opt to leave it in the same position. Diagonal moves are not allowed and the cloud must always remain entirely within the country.

There is a schedule of markets and festivals over a period of T days. On a day when an event is scheduled in an area, that area must not receive rain (i.e. it must be sunny). On days with no events in an area, it is acceptable if the area is under the cloud (raining), but there is an additional constraint:

No area is allowed to be without rain for a full week. Formally, if we define the day before the period (day 0) and the day after the period (day T+1) as days when every area receives rain, then for every area and for every day d within the period the following must hold: $$d - L \le 6,$$ where \(L\) is the most recent day on which that area received rain.

Your task is to produce a valid plan of movements (i.e. a cloud position for each day) that meets the following conditions:

• On day 1, the cloud position is fixed with top‐left coordinate (2,2).
• For each day, for every event in an area, the cloud must not cover that area.
• For every area, the gap between two days with rain (taking day 0 and day T+1 as having rain) does not exceed 6.

If a valid plan exists, output the top‐left coordinate (row and column) of the cloud for each day. Otherwise, output NO SOLUTION.

inputFormat

The first line contains an integer T (1 ≤ T ≤ 50), the number of days in the period.

Each of the next T lines describes one day. Each day’s description starts with an integer k (k ≥ 0) indicating the number of events on that day, followed by k distinct integers in the range [1,16] representing the areas where markets or festivals are held.

outputFormat

If a valid cloud movement plan exists, output T lines. On the i-th line, print two integers representing the row and column of the top‐left cell of the cloud on day i. (The first day must be 2 2.) If there is no valid solution, output a single line containing NO SOLUTION.

sample

3
0
1 1
0

2 2
2 2
2 2