전구 숫자

스위칭 박스에는 위쪽에 (N)개의 스위치가 있고 아래쪽에 (N)개의 전구가 있다. 스위치는 왼쪽부터 (1,2,dots,N)으로 번호가 붙어 있다. 전구는 왼쪽부터 (B_N,B_{N-1},dots,B_1) 순서로 놓여 있으므로, (B_1)은 가장 오른쪽 전구이다.

각 스위치는 정확히 하나의 전구와 전선으로 연결되어 있다. 여러 스위치를 동시에 누르면, 어떤 전구는 그 전구에 연결된 전선이 동시에 눌린 다른 전선과 하나도 만나지 않을 때만 켜진다. 그 전선이 다른 눌린 전선과 하나라도 만나면 해당 전구는 켜지지 않는다.

전구 (B_i)가 켜져 있으면 (i)번째 비트를 1, 꺼져 있으면 0으로 표시한다. 이렇게 얻은 (N)비트 이진수 (B_NB_{N-1}dots B_1)을 전구 숫자라고 하며, (B_1)이 가장 낮은 자리 비트이다. 아무 스위치도 누르지 않은 상태의 전구 숫자는 0이다.

스위칭 박스의 연결 구조와 정수 (K)가 주어진다. 만들 수 있는 모든 전구 숫자를 십진수 값 기준 오름차순으로 정렬했을 때, (K)번째 값을 구하라. 만들 수 있는 전구 숫자가 (K)개보다 적으면 -1을 출력한다.

첫째 줄에 스위치와 전구의 수 (N)이 주어진다. (3 le N le 30)

둘째 줄에는 전구 (B_N,B_{N-1},dots,B_1)에 각각 연결된 스위치 번호가 이 순서대로 공백으로 구분되어 주어진다.

셋째 줄에 정수 (K)가 주어진다. (1 le K le 1,000,000,000)

만들 수 있는 전구 숫자를 십진수 값 기준으로 오름차순 정렬했을 때 (K)번째 값을 출력한다. 그런 값이 없으면 -1을 출력한다.