Tách xâu số của bé Mì

Bé Mì viết các số nguyên từ \(1\) đến \(N\), mỗi số đúng một lần, theo một thứ tự tùy ý và viết liền sát nhau, không có khoảng cách, thành một xâu chữ số rất dài. Chẳng hạn với \(N = 5\), Mì có thể viết 53214 (các số \(5, 3, 2, 1, 4\)).

Vì chỉ có xâu chữ số nên có khi ta tách ra được nhiều dãy số khác nhau. Hãy giúp Mì tìm tất cả các cách tách xâu đó thành các số, sao cho các số thu được là một hoán vị của \(1, 2, \dots, N\) (mỗi số từ \(1\) đến \(N\) xuất hiện đúng một lần, không có số nào bắt đầu bằng chữ số \(0\)).

Input

• Dòng đầu tiên gồm số nguyên \(N\).
• Dòng thứ hai là xâu chữ số mà Mì đã viết (có ít nhất một cách tách hợp lệ).

Output

Mỗi dòng in một cách tách: các số theo thứ tự từ trái sang phải, cách nhau một dấu cách. Các cách được in theo thứ tự từ điển tăng dần (so sánh các số theo giá trị số, từ trái sang phải).

Constraints

• \(1 \le N \le 40\)

Sample Input 1

12
311287112109465

Sample Output 1

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

Sample Input 2

10
11023456789

Sample Output 2

1 10 2 3 4 5 6 7 8 9

Explanation

Ở ví dụ 1, các dòng \(3\ 1\ 12\ 8\ldots\) và \(3\ 11\ 2\ 8\ldots\) cho cùng một xâu 311287112109465. Ở ví dụ 2, số \(0\) không thể đứng đầu một số nên chữ số 0 bắt buộc phải đi liền sau chữ số 1 để tạo thành \(10\).