Giải bài trực tuyến

Xét tất cả các hoán vị của dãy số tự nhiên (1, 2,..., n) (1 <= n <= 12)

Giả sử rằng các hoán vị được sắp xếp theo thứ tự từ điển.

Yêu cầu:

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

2: 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ị đó

Input

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ử )

Output

Dòng 1: Ghi số q ( số hiệu của dãy hoán vị a_i )

Dòng 2: Ghi n số b₁, b₂, …, b_n ( dãy hoán vị có số hiệu p )

Example

Input:
2 1 3
4

Output:
3
2 3 1