Xét tất cả các hoán vị của dãy số tự nhiên (1,2,3,…,n) với (1 ≤ n ≤ 12). Giả sử rằng các hoán vị đều được sắp xếp theo thứ tự từ điển.

Yêu cầu:

• Cho trước 1 hoán vị. Tìm số hiệu của hoán vị đó trong dãy đã sắp xếp.
• Cho trước số hiệu của 1 hoán vị trong dãy hoán vị đã sắp xếp. Tìm hoán vị đó.

Dữ liệu

• Dòng 1: Chứa n số a1, a2, . . . , an (dãy hoán vị n phần tử). • Dòng 2: Chứa số p (số hiệu của hoán vị trong dãy hoán vị n phần tử).

Kết quả

• Dòng 1: Ghi số q (số hiệu của dãy hoán vị a). • Dòng 2: Ghi n số b1, b2, . . . , bn (dãy hoán vị có số hiệu p).

Ví dụ

Input

2 3 1
5

Output

4
3 1 2