CATALAN Dãy số Catalan

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 ≤ i ≤ 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 ≤ 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 INPUT
• Dòng 2 ghi dãy ứng với số thứ tự.

Input	Output
4 0 1 2 3 2 1 2 1 0 12	12 0 1 2 3 2 1 2 1 0