시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB58216013133.333%

문제

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

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

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

입력

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

출력

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

예제 입력 1

5
1
2
4
8
16
30

예제 출력 1

01111

예제 입력 2

24
19226985
123697
67356296
19721773
1113273
69335448
23680077
9029881
85168664
93676782
5253843
77616588
78572630
13375812
17199980
101508862
59248276
3505733
35790095
62028546
85726819
56462819
103373994
91757169
667509506

예제 출력 2

110001000101101100010101
W3sicHJvYmxlbV9pZCI6IjIwODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NTRcdWQ2MzhcdWJiMzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjliMCBcdWM2NTVcdWM3OTBcdWIyOTQgXHVjODA0XHViYjM4XHVjODAxXHVjNzc4IFx1ZDU3NFx1Y2VlNFx1Yzc3NFx1YjJlNC4gXHVjNWI0XHViOWIwIFx1YzY1NVx1Yzc5MFx1YjI5NCBcdWNkNWNcdWFkZmNcdWM1ZDAgbi1iaXRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1Yzc3NFx1YzljNCBcdWM1NTRcdWQ2MzhcdWJiMzhcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ2MDhcdWM1NDhcdWM3NzQgXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzU1NFx1ZDYzOFx1YmIzOFx1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YjJlOFx1YzExY1x1Yjk3YyBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YzViYlx1YzVjOFx1YjI5NFx1YjM3MCwgblx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI0ZTRcdWFjZmMgXHVjNzc0IFx1YzU1NFx1ZDYzOFx1YmIzOFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNTU0XHVkNjM4XHVkNjU0XHViNDFjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NTRcdWQ2MzhcdWQ2NTRcdWI0MWMgXHVjMjJiXHVjNzkwIEsgPSBhPHN1Yj4xPFwvc3ViPnQ8c3ViPjE8XC9zdWI+ICsgYTxzdWI+MjxcL3N1Yj50PHN1Yj4yPFwvc3ViPiArIC4uLiArIGE8c3ViPm48XC9zdWI+dDxzdWI+bjxcL3N1Yj4mbmJzcDtcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgdDxzdWI+MTxcL3N1Yj4gfiB0PHN1Yj5uPFwvc3ViPlx1Yzc0MCAwIFx1YjYxMFx1YjI5NCAxXHViODVjIFx1YzZiMFx1YjlhY1x1YWMwMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IG4tYml0XHVjNzU4IFx1Yzc3NFx1YzljNCBcdWM1NTRcdWQ2MzhcdWJiMzhcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjliMCBcdWM2NTVcdWM3OTBcdWIyOTQgYTxzdWI+MTxcL3N1Yj4gfiBhPHN1Yj5uPFwvc3ViPlx1YWNmYyBLXHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YzljNCBcdWM1NTRcdWQ2MzhcdWJiMzhcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIGJpdFx1Yzc1OCBcdWMyMTggbiAoNSAmbGU7IG4gJmxlOyA0MClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPlx1Yzc3NCBcdWFjMDEgXHVjOTA0XHVjNWQwIDFcdWFjMWNcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBhPHN1Yj5pPFwvc3ViPlx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViYTcwLCBuXHVhYzFjXHVjNzU4IFx1YzIxOCBcdWM4MDRcdWNjYjRcdWM3NTggXHVkNTY5XHVjNzQwIDIsMDAwLDAwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG4tYml0XHVjNzU4IFx1Yzc3NFx1YzljNCBcdWM1NTRcdWQ2MzhcdWJiMzhcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc3YyBcdWFjYmRcdWM2YjAgXHVkNTU4XHViMDk4XHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2lwaGVyIiwiZGVzY3JpcHRpb24iOiI8cD5XZSBhcmUgZ2l2ZW4gYSBzZXF1ZW5jZSBvZiBwb3NpdGl2ZSBpbnRlZ2VycyBhPHN1Yj5pPFwvc3ViPiAoZm9yIGkgPSAxLCAyLCAuLi4sIG4pLiBUaGlzIHNlcXVlbmNlIGlzIHVzZWQgdG8gZW5jcnlwdCBuLWJpdCBtZXNzYWdlcy4gSWYgd2UgaGF2ZSBhIG1lc3NhZ2UgY29uc2lzdGluZyBvZiBjb25zZWN1dGl2ZSBiaXRzKHQ8c3ViPjE8XC9zdWI+LCAuLi4sIHQ8c3ViPm48XC9zdWI+KSAodDxzdWI+aTxcL3N1Yj4gaXMgZWl0aGVyIDAgb3IgMSksIHRoZW4gaXRzIGVuY3J5cHRpb24gaXQgdGhlIG51bWJlci48XC9wPlxyXG5cclxuPHA+UyA9IHQ8c3ViPjE8XC9zdWI+YTxzdWI+MTxcL3N1Yj4gKyB0PHN1Yj4yPFwvc3ViPmE8c3ViPjI8XC9zdWI+ICsgLi4uICsgdDxzdWI+bjxcL3N1Yj5hPHN1Yj5uPFwvc3ViPjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIGVuY3J5cHRlZCBtZXNzYWdlcyBhbmQgc2VxdWVuY2VzIG9mIG51bWJlcnMgKGE8c3ViPmk8XC9zdWI+KSwgdGhhdCBoYXZlIGJlZW4gdXNlZCB0byBlbmNyeXB0IHRoZSBtZXNzYWdlcy4gWW91ciB0YXNrIGlzIHRvIGRlY3J5cHQgdGhlIGVuY3J5cHRlZCBtZXNzYWdlcyBhbmQgdG8gc2F2ZSB0aGVtIGluIHBhcnRpY3VsYXIgZmlsZXMuIFlvdSBhcmUgbm90IGV4cGVjdGVkIHRvIHByZXNlbnQgYW55IHByb2dyYW0uIEl0IGlzIHN1ZmZpY2llbnQgdGhhdCB5b3Ugd3JpdGUgdGhlIGRlY3J5cHRlZCBtZXNzYWdlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGVyZSBpcyBvbmUgaW50ZWdlciBuLCA1ICZsZTsgbiAmbGU7IDQwLiBJbiB0aGUgc3VjY2Vzc2l2ZSBuIGxpbmVzIHRoZXJlIGlzIGEgc2VxdWVuY2Ugb2YgbnVtYmVycyAoYTxzdWI+aTxcL3N1Yj4pIHdyaXR0ZW46IGluIHRoZSBsaW5lIG9mIG51bWJlciBpKzEgdGhlcmUgaXMgb25lIHBvc2l0aXZlIGludGVnZXIgYTxzdWI+aTxcL3N1Yj4uIFRoZSBzdW0gb2YgdGhlIG51bWJlcnMgYTxzdWI+aTxcL3N1Yj4gZG9lcyBub3QgZXhjZWVkIDIgMDAwIDAwMCAwMDAuIEluIHRoZSBsaW5lIG9mIG51bWJlciBuKzIgdGhlcmUgaXMgb25lIGludGVnZXIgUyAtIHRoZSBlbmNyeXB0ZWQgbWVzc2FnZSwgMCAmbGU7IFMgJmxlOyBhPHN1Yj4xPFwvc3ViPiArIGE8c3ViPjI8XC9zdWI+ICsgLi4uICsgYTxzdWI+bjxcL3N1Yj4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb2Ygc3RhbmRhcmQgb3V0cHV0IHlvdSBzaG91bGQgd3JpdGUgdGhlIHN1Y2Nlc3NpdmUgbnVtYmVycyB0PHN1Yj5pPFwvc3ViPiwgd2l0aG91dCBhbnkgc3BhY2VzIGJldHdlZW4gdGhlbS4gVGhlIHRlc3QgZGF0YSB3ZXJlIGNob3NlbiBzbyB0aGF0IHRoZSBlbmNyeXB0ZWQgbWVzc2FnZXMgYXJlIHVuYW1iaWd1b3VzbHkgZGV0ZXJtaW5lZC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==