Thi lập trình trực tuyến

Houses

A construction company invested in building a row of L houses in a street. There are N people who want to buy these houses. The i^th buyer will buy a_i houses and each one will only buy consecutive houses. Because the number of houses to be sold may be smaller than the total number of houses (L), there are some houses not to be sold. To ensure the beauty of the area, the company will always sell the first house (in left to right order).

Given the requirements of each buyer, a way for the company to sell houses can be represented by a sequence of L numbers, in which the i^th number is 0 if the i^th house will not be sold and is k if the i^th house will be sold to the k^th buyer.

For example, if L=4, N=2, a₁ = 2, a₂=1, the sequence "2 0 1 1" represents a way to sell houses for the company: the first house will be sold to the second buyer, the 3^rd and 4^th houses will be sold to the first buyer and the second house will not be sold.

Help the company to enumerate the ways to sell houses. The ways to sell houses should be enumerated by the lexicographical order of the corresponding sequences. If there are more than 1000 ways to sell houses, only enumerate the first 1000 ways (sequence a preceeds sequence b in lexicographical order iff there exists j so that a_i=b_i for all i < j and a_j < b_j).

Input

• First line: two integers L, N.
• Second line: N integers a₁, a₂, ..., a_n.

Constraints

• 1 ≤ L ≤ 100.
• 1 ≤ N ≤ 20.
• a₁ + a₂ + ... + a_N ≤ L.

Output

Each line of the output corresponds to a sequence representing a way for the company to sell houses. Two consecutive numbers are separated by a space. The sequences are enumerated by lexicographical order.

Example

Input
4 2
2 1

Output
1 1 0 2
1 1 2 0
2 0 1 1
2 1 1 0