Số hiệu hoán vị

Xét mọi hoán vị của tập $\{1,2,\dots ,n\}$, sắp tăng theo thứ tự từ điển và đánh số từ $1$. Cho một hoán vị $a$ và một thứ hạng hợp lệ $p$; hãy tìm thứ hạng của $a$ và hoán vị đứng ở vị trí $p$.

Input

• Dòng đầu chứa một hoán vị của các số từ $1$ đến $n$; số lượng phần tử trên dòng xác định $n$.
• Dòng thứ hai chứa số nguyên $p$, là một thứ hạng hợp lệ.

Output

• Dòng đầu in thứ hạng $1$-based của hoán vị đã cho.
• Dòng thứ hai in hoán vị đứng ở vị trí $p$.

Constraints

• $1\le n\le 12$.
• Dòng đầu là một hoán vị của $1,\dots ,n$.
• $1\le p\le n!$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 8$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

3 1 2
6

5
3 2 1