Cho số nguyên dương \(N\). Hãy tìm ra dãy số thoả mãn:

• Số lượng các phần tử lớn hơn \(2\), tất cả phần tử của dãy là số nguyên dương;
• Dãy số là dãy tăng dần vè chênh lệch giữa hai phần tử liên tiếp bằng nhau;
• Tổng tất cả các phần tử của dãy số là \(N\);
• Nếu có nhiều dãy có tổng bằng \(N\), tìm ra dãy có số lượng phần tử lớn nhất;
• Nếu có nhiều hơn một dãy thoả mãn, chọn dãy có phần tử đầu tiên là bé nhất.

Dữ liệu vào từ tệp văn bản DCD.INP:

Một dòng duy nhất chứa số nguyên dương \(N\) \((N \le 10^9)\).

Dữ liệu ghi ra tệp văn bản DCH.OUT:

Gồm một dòng là dãy số thoả mãn. Nếu không có dãy số thoả mãn, ghi ra \(-1\).

Ví dụ

Input

12

Output

1 4 7

Giải thích

Dãy \(2, 4, 6\) hoặc \(3, 4, 5\) cũng có tổng là \(12\) và số lượng phần tử là \(3\). Nhưng dãy số \(1, 4, 7\) là dãy có phần tử đầu tiên bé nhất.

Input

20

Output

2 3 4 5 6

Giải thích

Dãy \(2, 4, 6, 8\) cũng có tổng là \(20\) và số lượng phần tử là \(4\). Nhưng dãy số \(2, 3, 4, 5, 6\) là dãy có số lượng phần tử lớn hơn.

Ràng buộc

• Có \(40\%\) số test ứng với \(40\%\) số điểm thoả mãn: \(N \le 10^3\);
• \(30\%\) số test khác ứng với \(30\%\) số điểm thoả mãn: \(N \le 10^5\);
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm không có ràng buộc gì thêm.

Cho một tập \(S\) gồm \(N\) xâu ký tự \(S_1, S_2, ..., S_N\). Mỗi xâu trong tập \(S\) chỉ chứa các chữ cái tiếng Anh in thường. Với xâu \(S_i\) \((1\le i\le N)\), chọn ra một xâu con không rỗng gồm các ký tự liên tiếp, gọi xâu con đó là \(T_i\). Sau đó, nối các xâu \(T_1, T_2, ..., T_N\) theo thứ tự từ trái qua phải tạo thành xâu \(P\).

Yêu cầu: Cho số nguyên dương \(K\), hãy tìm xâu \(P\) có độ dài đúng bằng \(K\) và có thứ tự từ điển nhỏ nhất.

Dữ liệu vào từ tệp văn bản NX.INP:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) lần lượt là số lượng xâu trong tập \(S\) và độ dài xâu \(P\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) \((1\le i\le N)\) chứa xâu ký tự \(S_i\);

Dữ liệu đảm bảo \(1\le N\le K\le \displaystyle\sum^N_{i=1}|S_i|\le 4000\) với \(|S_i|\) là độ dài của xâu \(S_i\).

Dữ liệu ghi ra tệp văn bản NX.OUT:

Gồm một dòng là xâu \(P\) cần tìm.

Ví dụ

Input

2 3
aen
bbb

Output

abb

Giải thích

Chọn ra xâu con a của xâu aen.

Chọn ra xâu con bb của xâu bbb.

Input

2 3
bb
adh

Output

bad

Giải thích

Chọn ra xâu con b của xâu bb.

Chọn ra xâu con ad của xâu adh.

Ràng buộc

• Có \(30\%\) số test ứng với \(30\%\) số điểm thoả mãn: \(N=2; \ |S_1|, |S_2| \le 100\);
• \(30\%\) số test khác ứng với \(30\%\) số điểm thoả mãn: \(1\le N\le 50; \ |S_1|=|S_i|\le 10\) \((1\le i \le N)\);
• \(40\%\) số test còn lại ứng với \(40\%\) số điểm không có ràng buộc gì thêm.

Cho \(N\) đoạn thẳng song song với trục \(Ox\), các đoạn thẳng được đánh số từ \(1\) đến \(N\). Đoạn thẳng thứ \(i\) \((1\le i\le N)\) được xác định bởi điểm đầu và điểm cuối lần lượt là hai số nguyên dương \(l_i, r_i\). Hai đoạn thẳng \(i, j\) \((1\le i, j\le N)\) được gọi là giao nhau khi: \((r_i-l_i)+(r_j-l_j)\ge \max(r_i, r_j) - \min(l_i, l_j)\).

Ví dụ: như hình vẽ dưới, đoạn thẳng thứ \(1\) và \(4\), đoạn thẳng thứ \(2\) và \(3\), ... được gọi là giao nhau; đoạn thẳng thứ \(2\) và \(5\), đoạn thẳng thứ \(1\) và \(3\), ... không được gọi là giao nhau.

Yêu cầu: Hãy chọn ra hai tập đoạn thẳng \(S_1\) (có số lượng phần tử là \(x\)) và \(S_2\) (có số lượng phần tử là \(y\)) thoả mãn:

• Mỗi đoạn thẳng trong \(N\) đoạn thẳng thuộc tối đa một tập;
• Các đoạn thẳng trong cùng một tập đôi một giao nhau;
• \(x\ge y\) và \(y\) lớn nhất.

Dữ liệu vào từ tệp văn bản CT.INP:

• Dòng đầu chứa số nguyên dương \(N\) \((2\le N\le 5 \times 10^5)\) là số lượng đoạn thẳng;
• \(N\) dòng tiếp theo, dòng thứ \(i\) \((1\le i\le N)\) chứa hai số \(l_i, r_i\) \((1\le l_i\le r_i\le 10^9)\) mô tả điểm đầu và điểm cuối của đoạn thẳng thứ \(i\).

Dữ liệu ghi ra tệp văn bản CT.OUT:

Ghi ra giá trị \(y\) thoả mãn.

Ví dụ

Input

5
4 7
1 8
8 10
2 6
11 12

Output

2

Giải thích

Có thể có nhiều cách lựa chọn ra hai tập.

Nếu chọn tập \(S_1\) gồm \(3\) đoạn thẳng thứ \(1, 2\) và \(4\); tập \(S_2\) gồm \(1\) đoạn thẳng thứ \(3\) hoặc \(5\); cách này có \(x=3, y=1\).

Nếu chọn tập \(S_1\) gồm \(2\) đoạn thẳng thứ \(1\) và \(4\); tập \(S_2\) gồm \(2\) đoạn thẳng thứ \(2\) và \(3\); cách này có \(x=2, y=2\).

Ràng buộc

• Có \(25\%\) số test ứng với \(25\%\) số điểm thoả mãn: \(N\le 500\);
• \(25\%\) số test khác ứng với \(25\%\) số điểm thoả mãn: \(N\le 5000\);
• \(25\%\) số test khác ứng với \(25\%\) số điểm thoả mãn: \(N\le 10^5\);
• \(25\%\) số test còn lại ứng với \(25\%\) số điểm không có ràng buộc gì thêm.