#P3388. Japanese Puzzle

    ID: 2398 远端评测题 2000ms 64MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>Northeastern Europe 2006, Northern Subregion

Japanese Puzzle

Description

A brand-new Japanese puzzle is coming from the East to strike the world-popular Sudoku game and become an international hit. The rules of this puzzle are kept in secret yet, but the goal is already advertised: given a square grid n × n, where each square contains a block with one of k types of pictures, the player has to rearrange it to get the maximal possible number of equal first rows (two rows are considered equal if both of them are filled with the same pictures in the same order). An unnamed insider of the game production company told the press that the game is about moving blocks of pictures according to some rules, while the overall set of pictures isn’t changed (no pictures removed, no new pictures added). She also mentioned that the puzzle is so exciting because there are thousands of ways to swap two arbitrary pictures on a grid leaving the rest of the grid intact.

Andy works at the puzzles review magazine, and of course he got interest in this Japanese news. He realized that the information known so far is enough to find the number of equal first rows in a puzzle winning position. Now Andy wants to write a computer program for calculating this number for any given starting configuration.

For example, if you are given a puzzle which looks this way:

+

one of the optimal rearrangements could look like

+

Input

The first line of the input file contains two integers n (1 ≤ n ≤ 40 000) and k (1 ≤ k ≤ 50 000). Each of the next k lines contains the number of blocks with the corresponding type of picture li (li > 0, sum of all li is exactly n2).

Output

Output the maximal possible number of equal first rows at the first line of the output file. The following n lines must contain contents of the row which gives the maximum. Each line shows a single number of picture, in order they must appear. If there are many optimal solutions, any is acceptable.

3 4
3
3
2
1
2
1
2
3

Source

Northeastern Europe 2006, Northern Subregion