Mabư Béo đang rất tức giận. Hắn ta có ~M~ giá để tạ đã được phân theo đúng quy tắc. Nhưng ai đó đã vào phòng gym của hắn để xáo tung các quả tạ với nhau, khiến cho hắn ta phải xếp lại chỗ tạ đó.

Mabư Béo có ~N - 1~ quả tạ, với cân nặng lần lượt là ~1~, ~2~, ~\ldots~, ~N - 1~. ~N~ luôn là số nguyên tố được viết dưới dạng ~3k+1~ với ~k~ nguyên. Hắn cần xếp tạ vào ~M~ giá để tạ, sao cho giá thứ ~i~ có đúng ~a_i~ quả tạ. Mabư Béo muốn tổng cân nặng của các quả tạ trên một giá để tạ phải chia hết cho ~N~.

Hãy chỉ cho hắn một cách xếp tạ lên giá bất kỳ thỏa mãn điều kiện trên.

Input

Dòng đầu tiên chứa ~N~ và ~M~ (~7 \le N \le 99\ 991~, ~N~ là số nguyên tố có dạng ~3k+1~, ~1 \le M \le \lfloor \frac{N}{2} \rfloor~) - thể hiện thông tin về bộ tạ mà Mabư Béo có, và số giá tạ.

Dòng thứ hai chứa ~M~ số nguyên: ~a_1, a_2, \ldots, a_M~ (~2 \le a_i \le N - 1~, tổng các ~a_i~ đúng bằng ~N - 1~) - số quả tạ cần phải xếp lên từng giá tạ.

Output

~M~ dòng, dòng thứ ~i~ chứa đúng ~a_i~ số nguyên, thể hiện ~a_i~ quả tạ bạn muốn xếp lên giá thứ ~i~. Câu trả lời của bạn sẽ được coi là đúng khi:

• Tổng cân nặng các quả tạ trên mỗi giá chia hết cho ~N~.

• Mỗi quả tạ từ ~1~ đến ~N-1~ xuất hiện duy nhất ~1~ lần giữa tất cả các giá tạ.

Sample Input 1

7 3
2 2 2

Sample Output 1

3 4
2 5
1 6

Sample Input 2

13 4
5 2 3 2

Sample Output 2

5 6 7 9 12
3 10
1 4 8
2 11

Sample Input 3

13 3
3 4 5

Sample Output 3

5 9 12
3 6 7 10
1 2 4 8 11

Sample Input 4

19 3
4 11 3

Sample Output 4

10 9 11 8 
14 5 15 4 16 3 17 2 18 13 7 
12 6 1

Sample Input 5

7 2
3 3

Sample Output 5

1 2 4
3 5 6

Notes

Lưu ý rằng: mỗi input có thể có rất nhiều đáp án.