Cho số nguyên dương \(N\), dãy Catalan cấp \(n\) là dãy \(C(1),C(2)…C(2n+1)\) gồm các số nguyên không âm thoả mãn: \(C(1)=C(2n+1)=0\) với \(i\) bất kì \(1\leq i\leq 2n\) thì \(C(i),C(i+1)\) hơn kém nhau 1 đơn vị.

Với mỗi \(n\) ta sắp xếp các dãy Catalan theo thứ tự từ điển, đánh số từ 1 trở đi. Yêu cầu:

1. Cho một dãy Catalan, hãy tìm thứ tự của dãy.
2. Cho số nguyên dương k hãy tìm dãy có thứ tự \(k\).

Input

• Dòng đầu ghi \(n\) (\(n\le 15\)).
• Dòng hai ghi một dãy Catalan cấp \(n\).
• Dòng 3 ghi một số nguyên dương \(k\) (\(k\) có thể rất lớn nhưng đảm bảo luôn có nghiệm).

Output

• Dòng 1 ghi số thứ tự dãy ở dòng 2 của input.
• Dòng 2 ghi dãy ứng với số thứ tự.

Example

4
0 1 2 3 2 1 2 1 0
12

12
0 1 2 3 2 1 2 1 0

Nguồn: SPOJ