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ố \(a_1,a_2,...,a_n\) (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\))
• Dòng 2: Ghi \(n\) số \(b_1,b_2,...,b_n\) (dãy hoán vị có số hiệu \(p\))

Example

2 1 3
4

 3
2 3 1