Skyscraper Towers Puzzle

Little Blue is obsessed with a puzzle game known as the Skyscraper Towers Puzzle. In this game, you are given an N×N board and towers of heights \(1,2,\ldots,N\). Each tower occupies a single cell on the board. The rules are as follows:

1. Each tower’s height is unique and must be one of \(1,2,\ldots,N\).
2. Every row and every column must contain each of the heights exactly once (i.e. no duplicate heights).
3. Numbers placed around the board act as clues. Each number indicates how many towers are visible when looking from that edge in a straight line. A tower is visible if it is taller than all towers before it in that direction. Formally, given a sequence \(a_1,a_2,\ldots,a_k\), the visible count is computed by iterating from the edge and counting how many times a value exceeds the maximum value seen so far.

You will be given the clues in the following order:

• Top: N numbers representing the clues for each column viewed from the top (from left to right).
• Bottom: N numbers representing the clues for each column viewed from the bottom (from left to right).
• Left: N numbers for each row viewed from the left (from top to bottom).
• Right: N numbers for each row viewed from the right (from top to bottom).

Your task is to fill the board with tower heights such that all rules are satisfied. It is guaranteed that the puzzle has a unique solution. Output the answer as a concatenated string of \(N^2\) digits by reading the board row by row from left to right and top to bottom.

For example, one sample puzzle (for a 4×4 board) has the answer:

\(1432432121433214\)

inputFormat

The input is given in the following format:

N
T1 T2 ... TN
B1 B2 ... BN
L1 L2 ... LN
R1 R2 ... RN

Where:

• N is the size of the board.
• The second line contains N space-separated integers representing the top clues.
• The third line contains N space-separated integers representing the bottom clues.
• The fourth line contains N space-separated integers representing the left clues.
• The fifth line contains N space-separated integers representing the right clues.

outputFormat

Output a single line containing a string of \(N^2\) digits that represents the unique solution. The towers in the board should be outputted row by row (from top to bottom) and, within each row, from left to right, with no spaces between digits.

sample

4
2 1 2 3
2 3 2 1
2 1 2 2
3 4 2 1

1432432121433214