Một công ty đầu tư xây dựng một khu nhà gồm L căn nhà nằm cạnh nhau trên một con đường. Có N người muốn mua nhà ở khu nhà này, biết rằng người thứ i muốn mua ai căn nhà và mỗi người đều muốn mua những căn nhà nằm cạnh nhau. Do số căn nhà cần mua có thể nhỏ hơn tổng số căn nhà (L) nên sẽ có một số căn nhà chưa được bán. Để đảm bảo mỹ quan của khu nhà, công ty sẽ luôn luôn bán căn nhà đầu tiên (theo thứ tự từ trái sang phải).

Biết yêu cầu của những người mua, một cách bán những căn nhà của công ty có thể được biểu diễn bằng 1 dãy gồm L số. Trong đó số thứ i bằng 0 nếu căn nhà thứ i chưa được bán và bằng k nếu căn nhà thứ i được bán cho người thứ k.

Ví dụ: khi L=4, N=2, a1 = 2, a2=1, dãy “2 0 1 1” thể hiện một cách bán những căn nhà của công ty: căn nhà đầu tiên bán cho người thứ 2, căn nhà thứ 3 và thứ 4 bán cho người đầu tiên và căn nhà thứ 2 được để lại.

Yêu cầu: Hãy giúp công ty liệt kê các cách bán những căn nhà. Các cách bán căn nhà được liệt kê theo thứ tự từ điển của dãy số biểu diễn. Nếu số cách bán căn nhà lớn hơn 1000, chỉ cần liệt kê 1000 cách đầu tiên. (Biết rằng dãy a có thứ tự từ điển đứng trước dãy b nếu và chỉ nếu tồn tại chỉ số j, sao cho ai = bi với mọi i < j và aj < bj).

Dữ liệu

• Dòng đầu tiên: chứa 2 số nguyên L, N.
• Dòng thứ 2 chứa N số nguyên, tương ứng là các giá trị a1, a2, …, an.

Hạn chế

• 1 ≤ L ≤ 100.
• 1 ≤ N ≤ 20.
• a1 + a2 + … + aN ≤ L.

Kết quả

Gồm nhiều dòng, mỗi dòng tương ứng với dãy số biểu diễn một cách bán những căn nhà của công ty, 2 số liên tiếp của dãy số được cách nhau bởi một khoảng trắng. Các dãy số được liệt kê theo thứ tự từ điển.

Ví dụ

Input
4 2
2 1

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