만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

예산

면접 대비

시간 제한2초메모리 제한1024 MB

요약
n개의 금액마다 수입 또는 지출을 정해 잔액이 매 연산 후 a 이상 b 이하로 유지되게 합니다. 가능한 방법이 없으면 Impossible을 출력합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 배열
정답자
아직 제출이 없습니다

문제

탐정 에르퀼 푸아로는 피해자의 개인 소지품을 조사하다가 피해자의 1년 치 수입과 지출을 모두 적은 목록을 발견했다. 금전은 살인의 동기가 되는 경우가 많으므로, 이런 문서는 사건의 핵심 단서다.

목록은 두 조각으로 찢겨 있었고, 탐정이 가진 것은 한 조각뿐이었다. 목록의 각 줄에는 연산의 종류(수입 또는 지출)와 연산의 크기를 나타내는 양의 정수가 적혀 있다. 푸아로가 가진 것은 오른쪽 절반으로, 모든 연산의 크기만 들어 있다.

나중에 피해자의 비서에게 피해자의 예산을 물어본 푸아로는, 첫 연산을 마친 뒤의 모든 시점에서 피해자의 총 자금이 최소 aa 이상이고 최대 bb 이하였다는 사실을 알게 되었다. 피해자의 예산은 처음에 0코인이다. 연산이 수입이면 총 자금이 그 크기만큼 늘고, 지출이면 줄어든다.

잃어버린 절반을 복원할 수 있도록, 각 연산이 수입인지 지출인지 알아내라.

입력

첫 줄에 정수 nn, aa, bb가 주어진다 (1≤n≤100001 \le n \le 10000, −100≤a≤b≤100-100 \le a \le b \le 100).

둘째 줄에는 연산의 크기를 나타내는 정수 nn개 f1,…,fnf_1, \dots, f_n이 주어진다 (1≤fi≤1001 \le f_i \le 100).

출력

공백 없이 0 또는 1로 이루어진 nn자리 수를 출력한다. ii번째 숫자가 1이면 ii번째 연산은 수입이고, 0이면 지출이다.

답이 여러 개라면 그중 아무거나 출력해도 된다. 답이 존재하지 않으면 Impossible을 출력한다.

예제1

  1. 예제 1

    입력
    5 -2 7
    2 4 3 8 1
    
    예상 출력
    01010