예산
면접 대비시간 제한2초메모리 제한1024 MB
n개의 금액마다 수입 또는 지출을 정해 잔액이 매 연산 후 a 이상 b 이하로 유지되게 합니다. 가능한 방법이 없으면 Impossible을 출력합니다.
문제
탐정 에르퀼 푸아로는 피해자의 개인 소지품을 조사하다가 피해자의 1년 치 수입과 지출을 모두 적은 목록을 발견했다. 금전은 살인의 동기가 되는 경우가 많으므로, 이런 문서는 사건의 핵심 단서다.
목록은 두 조각으로 찢겨 있었고, 탐정이 가진 것은 한 조각뿐이었다. 목록의 각 줄에는 연산의 종류(수입 또는 지출)와 연산의 크기를 나타내는 양의 정수가 적혀 있다. 푸아로가 가진 것은 오른쪽 절반으로, 모든 연산의 크기만 들어 있다.
나중에 피해자의 비서에게 피해자의 예산을 물어본 푸아로는, 첫 연산을 마친 뒤의 모든 시점에서 피해자의 총 자금이 최소 이상이고 최대 이하였다는 사실을 알게 되었다. 피해자의 예산은 처음에 0코인이다. 연산이 수입이면 총 자금이 그 크기만큼 늘고, 지출이면 줄어든다.
잃어버린 절반을 복원할 수 있도록, 각 연산이 수입인지 지출인지 알아내라.
입력
첫 줄에 정수 , , 가 주어진다 (, ).
둘째 줄에는 연산의 크기를 나타내는 정수 개 이 주어진다 ().
출력
공백 없이 0 또는 1로 이루어진 자리 수를 출력한다. 번째 숫자가 1이면 번째 연산은 수입이고, 0이면 지출이다.
답이 여러 개라면 그중 아무거나 출력해도 된다. 답이 존재하지 않으면 Impossible을 출력한다.