시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 247 52 47 27.485%

문제

어린 왕자는 전문적인 해커이다. 어린 왕자는 최근에 n-bit로 이루어진 이진 암호문을 알아내기 위해 혈안이 되어 있다. 이 암호문을 알아내기 위한 단서를 한 가지 얻었는데, n개의 숫자들과 이 암호문을 이용해서 암호화된 숫자를 알아낸 것이다.

암호화된 숫자 K = a1t1 + a2t2 + ... + antn 으로 표현된다. 여기서 t1 ~ tn은 0 또는 1로 우리가 알아내려고 하는 n-bit의 이진 암호문을 순서대로 이루는 숫자들이다.

어린 왕자는 a1 ~ an과 K를 알고 있다. 이진 암호문을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 bit의 수 n (5<=n<=40)이 주어진다. 둘째 줄부터 n개의 줄에 a1 ~ an이 각 줄에 1개씩 주어진다. 마지막 줄에는 K가 주어진다. a1 ~ an은 모두 자연수이며, n개의 수 전체의 합은 2,000,000,000을 넘지 않는다.

출력

첫째 줄에 n-bit의 이진 암호문을 출력한다. 답이 여러 개일 경우 하나만 출력한다.

예제 입력 1

5
1
2
4
8
16
30

예제 출력 1

01111
W3sicHJvYmxlbV9pZCI6IjIwODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NTRcdWQ2MzhcdWJiMzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjliMCBcdWM2NTVcdWM3OTBcdWIyOTQgXHVjODA0XHViYjM4XHVjODAxXHVjNzc4IFx1ZDU3NFx1Y2VlNFx1Yzc3NFx1YjJlNC4gXHVjNWI0XHViOWIwIFx1YzY1NVx1Yzc5MFx1YjI5NCBcdWNkNWNcdWFkZmNcdWM1ZDAgbi1iaXRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1Yzc3NFx1YzljNCBcdWM1NTRcdWQ2MzhcdWJiMzhcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ2MDhcdWM1NDhcdWM3NzQgXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzU1NFx1ZDYzOFx1YmIzOFx1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YjJlOFx1YzExY1x1Yjk3YyBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YzViYlx1YzVjOFx1YjI5NFx1YjM3MCwgblx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI0ZTRcdWFjZmMgXHVjNzc0IFx1YzU1NFx1ZDYzOFx1YmIzOFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNTU0XHVkNjM4XHVkNjU0XHViNDFjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NTRcdWQ2MzhcdWQ2NTRcdWI0MWMgXHVjMjJiXHVjNzkwIEsgPSBhPHN1Yj4xPFwvc3ViPnQ8c3ViPjE8XC9zdWI+ICsgYTxzdWI+MjxcL3N1Yj50PHN1Yj4yPFwvc3ViPiArIC4uLiArIGE8c3ViPm48XC9zdWI+dDxzdWI+bjxcL3N1Yj4mbmJzcDtcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgdDxzdWI+MTxcL3N1Yj4gfiB0PHN1Yj5uPFwvc3ViPlx1Yzc0MCAwIFx1YjYxMFx1YjI5NCAxXHViODVjIFx1YzZiMFx1YjlhY1x1YWMwMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IG4tYml0XHVjNzU4IFx1Yzc3NFx1YzljNCBcdWM1NTRcdWQ2MzhcdWJiMzhcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjliMCBcdWM2NTVcdWM3OTBcdWIyOTQgYTxzdWI+MTxcL3N1Yj4gfiBhPHN1Yj5uPFwvc3ViPlx1YWNmYyBLXHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YzljNCBcdWM1NTRcdWQ2MzhcdWJiMzhcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIGJpdFx1Yzc1OCBcdWMyMTggbiAoNSZsdDs9biZsdDs9NDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBhPHN1Yj4xPFwvc3ViPiB+IGE8c3ViPm48XC9zdWI+XHVjNzc0IFx1YWMwMSBcdWM5MDRcdWM1ZDAgMVx1YWMxY1x1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGE8c3ViPjE8XC9zdWI+IH4gYTxzdWI+bjxcL3N1Yj5cdWM3NDAgXHViYWE4XHViNDUwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YmE3MCwgblx1YWMxY1x1Yzc1OCBcdWMyMTggXHVjODA0XHVjY2I0XHVjNzU4IFx1ZDU2OVx1Yzc0MCAyLDAwMCwwMDAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuLWJpdFx1Yzc1OCBcdWM3NzRcdWM5YzQgXHVjNTU0XHVkNjM4XHViYjM4XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3N2MgXHVhY2JkXHVjNmIwIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjA4NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNpcGhlciIsImRlc2NyaXB0aW9uIjoiPHA+V2UgYXJlIGdpdmVuIGEgc2VxdWVuY2Ugb2YgcG9zaXRpdmUgaW50ZWdlcnMgYTxzdWI+aTxcL3N1Yj4gKGZvciBpID0gMSwgMiwgLi4uLCBuKS4gVGhpcyBzZXF1ZW5jZSBpcyB1c2VkIHRvIGVuY3J5cHQgbi1iaXQgbWVzc2FnZXMuIElmIHdlIGhhdmUgYSBtZXNzYWdlIGNvbnNpc3Rpbmcgb2YgY29uc2VjdXRpdmUgYml0cyh0PHN1Yj4xPFwvc3ViPiwgLi4uLCB0PHN1Yj5uPFwvc3ViPikgKHQ8c3ViPmk8XC9zdWI+IGlzIGVpdGhlciAwIG9yIDEpLCB0aGVuIGl0cyBlbmNyeXB0aW9uIGl0IHRoZSBudW1iZXIuPFwvcD5cclxuXHJcbjxwPlMgPSB0PHN1Yj4xPFwvc3ViPmE8c3ViPjE8XC9zdWI+ICsgdDxzdWI+MjxcL3N1Yj5hPHN1Yj4yPFwvc3ViPiArIC4uLiArIHQ8c3ViPm48XC9zdWI+YTxzdWI+bjxcL3N1Yj48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiBlbmNyeXB0ZWQgbWVzc2FnZXMgYW5kIHNlcXVlbmNlcyBvZiBudW1iZXJzIChhPHN1Yj5pPFwvc3ViPiksIHRoYXQgaGF2ZSBiZWVuIHVzZWQgdG8gZW5jcnlwdCB0aGUgbWVzc2FnZXMuIFlvdXIgdGFzayBpcyB0byBkZWNyeXB0IHRoZSBlbmNyeXB0ZWQgbWVzc2FnZXMgYW5kIHRvIHNhdmUgdGhlbSBpbiBwYXJ0aWN1bGFyIGZpbGVzLiBZb3UgYXJlIG5vdCBleHBlY3RlZCB0byBwcmVzZW50IGFueSBwcm9ncmFtLiBJdCBpcyBzdWZmaWNpZW50IHRoYXQgeW91IHdyaXRlIHRoZSBkZWNyeXB0ZWQgbWVzc2FnZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlcmUgaXMgb25lIGludGVnZXIgbiwgNSAmbGU7IG4gJmxlOyA0MC4gSW4gdGhlIHN1Y2Nlc3NpdmUgbiBsaW5lcyB0aGVyZSBpcyBhIHNlcXVlbmNlIG9mIG51bWJlcnMgKGE8c3ViPmk8XC9zdWI+KSB3cml0dGVuOiBpbiB0aGUgbGluZSBvZiBudW1iZXIgaSsxIHRoZXJlIGlzIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIGE8c3ViPmk8XC9zdWI+LiBUaGUgc3VtIG9mIHRoZSBudW1iZXJzIGE8c3ViPmk8XC9zdWI+IGRvZXMgbm90IGV4Y2VlZCAyIDAwMCAwMDAgMDAwLiBJbiB0aGUgbGluZSBvZiBudW1iZXIgbisyIHRoZXJlIGlzIG9uZSBpbnRlZ2VyIFMgLSB0aGUgZW5jcnlwdGVkIG1lc3NhZ2UsIDAgJmxlOyBTICZsZTsgYTxzdWI+MTxcL3N1Yj4gKyBhPHN1Yj4yPFwvc3ViPiArIC4uLiArIGE8c3ViPm48XC9zdWI+LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIHN0YW5kYXJkIG91dHB1dCB5b3Ugc2hvdWxkIHdyaXRlIHRoZSBzdWNjZXNzaXZlIG51bWJlcnMgdDxzdWI+aTxcL3N1Yj4sIHdpdGhvdXQgYW55IHNwYWNlcyBiZXR3ZWVuIHRoZW0uIFRoZSB0ZXN0IGRhdGEgd2VyZSBjaG9zZW4gc28gdGhhdCB0aGUgZW5jcnlwdGVkIG1lc3NhZ2VzIGFyZSB1bmFtYmlndW91c2x5IGRldGVybWluZWQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==