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

문제

Super Maroje živi u svom dvodimenzionalnom svijetu koji prikazujemo tablicom i u kojem, kao i u našem, postoji gravitacija koja objekte vuče prema dolje lijevo. Da bi joj se odupro i da bi se mogao kretati gdje i kako želi, nabavio je uređaj, jetpack, koji mu omogućuje da leti u svim smjerovima u kojima to želi, gore, dolje, lijevo, desno, dijagonalno. Njegov jetpack je u početku napunjen s $K$ jedinica goriva.

U tom svijetu postoji $N$ postaja zadanih svojim koordinatama $(x_i, y_i)$ pri čemu vrijedi pravilo: veći x znači da smo više desno u tom svijetu, a veći y znači da smo više gore u tom svijetu. Tajna tih postaja je da se u njima Maroje može odmoriti, a i jetpack mu se opet potpuno napuni do $K$ jedinica goriva.

Promotrimo malo jetpackove mogućnosti. Za pomak u Marojevom svijetu:

  • prema gore desno za jedno polje, tj. da se $x$ i $y$ povećaju za jedan, jetpack potroši $2 \times A$ jedinica goriva;
  • prema gore ili desno, tj. da se $x$ ili $y$ povećaju za jedan, jetpack potroši $A$ jedinica goriva;
  • prema gore lijevo ili dolje desno, tj. da se jedno od $x$ i $y$ povećaju za jedan, a ono drugo onda smanji za jedan, jetpack potroši $B$ jedinica goriva;
  • prema lijevo, dolje ili dolje lijevo, tj. da se $x$ i/ili $y$ smanje za $1$, jetpack ne troši gorivo (zbog gravitacije, jasno).

Super Maroje se nalazi na prvoj postaji i kreće na putovanje. Do kojih sve postaja može doći na tom putovanju?

입력

U prvom su retku prirodni brojevi $N$, $K$, $A$ i $B$ ($2 ≤ N$, $1 ≤ K, A ≤ 1\,000\,000$, $0 ≤ B ≤ A$), brojevi iz teksta zadatka.

U sljedećih $N$ redaka nalaze se po dva prirodna broja $X_i$ i $Y_i$ ($0 ≤ X_i, Y_i ≤ 1\,000\,000$), $x$ i $y$ koordinate $i$-te postaje.

Napomena: za ograničenja broja $N$ obratite pozornost na sekciju bodovanje!

출력

U prvi i jedini redak ispiši $N$ brojeva bez razmaka, gdje je $i$-ti broj $1$ ako može doći do $i$-te postaje, a $0$ je ako ne može.

서브태스크

번호배점제한
110

$N, X_i, Y_i ≤ 100$

215

$N ≤ 200$

320

$N ≤ 2\,000$ i $B = 0$

430

$N ≤ 2\,000$

525

$B = 0$ i $N ≤ 100\,000$

예제 입력 1

7 20 6 0
3 3
2 6
8 6
10 5
7 3
8 10
1 3

예제 출력 1

1100101

예제 입력 2

7 20 6 3
3 3
2 6
8 6
10 5
7 3
8 10
1 3

예제 출력 2

1100001

예제 입력 3

7 20 5 5
3 3
2 6
8 6
10 5
7 3
8 11
1 3

예제 출력 3

1111101

채점 및 기타 정보

  • 예제는 채점하지 않는다.