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ị ai )
• Dòng 2: Ghi n số b1, b2, …, bn ( dãy hoán vị có số hiệu p )

Example

Input
2 1 3
4

Output
3
2 3 1