Bài tập

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\).

Cho hai xâu \(u\) và \(v\), mỗi xâu chỉ gồm các chữ số thập phân và biểu diễn một số nguyên không âm; các xâu có thể chứa các chữ số 0 vô nghĩa ở đầu (ví dụ 0089 biểu diễn số \(89\)).

Hãy so sánh giá trị của hai số và in ra số lớn hơn, viết dưới dạng chuẩn: đã bỏ hết các chữ số 0 vô nghĩa ở đầu (nếu giá trị bằng \(0\) thì in 0). Nếu hai số bằng nhau, in ra giá trị chung đó.

Gợi ý: viết hàm \(NORM(S)\) bỏ các chữ số 0 vô nghĩa và hàm \(COMP(u, v)\) so sánh hai số.

Input

• Dòng thứ nhất chứa xâu \(u\).
• Dòng thứ hai chứa xâu \(v\).

Output

• In ra số lớn hơn ở dạng chuẩn.

Constraints

• Mỗi xâu có độ dài từ \(1\) đến \(10^6\) và chỉ gồm các chữ số từ 0 đến 9.

Sample Input 1

0007
35

Sample Output 1

35

Sample Input 2

000480
0479

Sample Output 2

480

Một cửa hàng điện máy phát cho mỗi khách mua hàng một tấm phiếu ghi số may mắn. Các phiếu được ghi lại theo đúng thứ tự khách đến mua, và không có hai phiếu nào trùng số. Cuối đợt khuyến mãi, cửa hàng công bố một số trúng thưởng, chắc chắn là số có trên phiếu của một khách nào đó.

Hãy cho biết khách trúng thưởng là người thứ mấy (tính từ \(1\) theo thứ tự mua hàng).

Input

• Dòng đầu chứa số nguyên \(n\) là số khách hàng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\), trong đó \(a_i\) là số may mắn của khách thứ \(i\).
• Dòng thứ ba chứa số nguyên \(k\) là số trúng thưởng.

Output

In ra một số nguyên là số thứ tự của khách hàng trúng thưởng.

Constraints

• \(1 \le n \le 4999\)
• \(1 \le a_i \le 5000\), các \(a_i\) đôi một khác nhau
• \(k\) bằng đúng một trong các số \(a_i\)

Sample Input

5
7 1 9 4 6
9

Sample Output

3

Explanation

Số \(9\) nằm ở vị trí thứ \(3\) trong dãy các phiếu.

Cho dãy gồm \(m\) số nguyên \(B_1, B_2, \ldots, B_m\). Hãy sắp xếp dãy thành dãy không giảm và in ra.

Gợi ý: có thể cài đặt sắp xếp nổi bọt (Bubble sort) và dùng một chương trình con \(Swap(a, b)\) để hoán đổi giá trị của hai phần tử; tuy nhiên chỉ cần in đúng kết quả.

Input

• Dòng đầu chứa số nguyên dương \(m\).
• Dòng thứ hai chứa \(m\) số nguyên \(B_1, B_2, \ldots, B_m\).

Output

• In ra dãy sau khi sắp xếp không giảm, các số cách nhau một dấu cách, trên một dòng.

Constraints

• \(1 \le m \le 10^3\)
• \(|B_i| \le 10^{18}\)

Sample Input 1

5
9 -2 7 7 0

Sample Output 1

-2 0 7 7 9