Cho số nguyên dương n≤30, hãy tìm tất cả các cách phân tích số n thành tổng của các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính một cách.

Input

File ANALYSE.INP chứa số nguyên dương n≤30

Output

File ANALYSE.OUT ghi các cách phân tích số n.( Xem test để rõ cách ghi)

Example

Sample input

6

6 = 1+1+1+1+1+1
6 = 1+1+1+1+2
6 = 1+1+1+3
6 = 1+1+2+2
6 = 1+1+4
6 = 1+2+3
6 = 1+5
6 = 2+2+2
6 = 2+4
6 = 3+3
6 = 6

Cho \(n\) số tự nhiên \({1,2,3,4, ..., n}\). Tổ hợp chập \(k\) của \(n\) số này là một cách chọn ra \(k\) số khác nhau trong \(n\) số, không kể thứ tự (tức là: chọn \([1,2,3]\) cũng giống như chọn \([3,2,1], [2,3,1], [1,3,2], ...\)).

Cho biết trước \(n,k\). Em hãy in ra tất cả tổ hợp chập \(k\) của \(n\) theo thứ tự từ điển.

Nhắc lại, hai dãy số \(s,t\) có cùng độ dài \(k, s\) có thứ tự từ điển bé hơn \(t\) khi tồn tại duy nhất \(i (1 \le i \le k)\)

• \(s[j] = t[j]\) với mọi \(1 \le j < i\)
• \(s[i] < t[i]\)

Nói cách khác, \(s < t\) khi tại vị trí \(i\) đầu tiên mà \(s[i] \neq t[i]\), ta có \(s[i] < t[i]\).

Trong tất cả các tổ hợp (cách chọn), có bao nhiêu cách mà tích của các số được chọn là một số chính phương?

Input

• Một dòng duy nhất chứa hai số \(n,k (1 \le k \le n \le 16)\)

Output

• In ra các tổ hợp, mỗi cách trên một dòng
• Ở dòng cuối cùng, in ra số lượng tích là số chính phương

Example

5 3 

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
0

Sau một thời gian chuyển sang nuôi bò lấy sữa DeMen100ms thu được lợi nhuận rất tốt. DeMen100ms muốn chuyển giao đàn bò này cho hai con của mình tiếp tục nuôi.

Đàn bò của DeMen100ms có \(n\) con bò, con thứ \(i\) có trọng lượng \(a_i\). Bây giờ DeMen100ms muốn chia bò thành hai phần để cho hai con của mình. DeMen100ms muốn chia sao cho sự chênh lệch về tổng trọng lượng bò của hai phần là ít nhất có thể. Bạn hãy tính giúp cho DeMen100ms liệu chênh lệch hai phần này nhỏ nhất là bao nhiêu.

Input

• Dòng thứ nhất là hai số nguyên dương \(n (1 \le n \le 38)\)

• Dòng thứ hai là là \(n\) số nguyên dương \(a_1, a_2, ... a_n (1 \le a_i \le 10^9).\)

Output

• In ra một số nguyên duy nhất là chênh lệch bé nhất của hai tập bò.

Example

5
13 5 1 5 20

2