Reconstruct the Snake on a 3×n Board

A snake occupies every square of a 3×n board. The snake is divided into 3×n segments which are numbered from 1 to 3n. Consecutive segments (i.e. segments numbered 1 and 2, 2 and 3, 3 and 4, etc.) must occupy squares that share a common edge.

Some of the segment numbers on the board may have been erased. Your task is to fill in the missing numbers so that the snake is correctly reconstructed. All given numbers must remain unchanged and the resulting numbering must form a continuous snake path (i.e. the cell containing k and the cell containing k+1 must be adjacent by an edge, for all 1 ≤ k < 3n).

Formally, if you denote the board as a 3×n grid where rows are numbered 0 to 2 and columns 0 to n−1, you are given an initial configuration where each cell contains either a number between 1 and 3n (fixed) or 0 meaning that the number is erased. You need to fill in the zeroes with appropriate numbers so that if C(k) is the cell containing number k then for every k from 1 to 3n−1, C(k) and C(k+1) are adjacent (i.e. share an edge). The reconstructed snake may be any valid one if multiple solutions exist.

inputFormat

The first line contains a single integer n (the number of columns). The next 3 lines describe the board configuration; each of these lines contains n integers separated by spaces. Each integer is either 0 (indicating an erased cell) or an integer between 1 and 3n corresponding to a fixed snake segment number. Note: It is guaranteed that the fixed numbers (if any) do not conflict with a valid snake path reconstruction.

outputFormat

Output the reconstructed board – 3 lines, each containing n integers separated by spaces – representing a valid snake configuration. If multiple solutions exist, any one is acceptable.

sample

3
1 2 3
6 5 4
7 8 9

1 2 3
6 5 4
7 8 9