블로그 게임

Petya와 Vasya는 평범한 소년이고, 평범한 소년 Seryozha 블로그의 유일한 독자다. Petya는 이 블로그를 아주 좋아하고, Vasya는 정확히 같은 정도로 싫어한다. 둘은 논쟁을 아주 좋아한다. $N$일 전 블로그 레이팅이 $R$이었을 때, 둘은 이 $N$일 동안 레이팅이 얼마나 바뀔지를 두고 다퉜다.

어떤 날에는 Petya가 "+1" 버튼을 눌러 레이팅을 1 올렸다. 마찬가지로 Vasya는 가끔 "-1" 버튼을 눌러 레이팅을 1 내렸다. 어떤 날 Petya가 "+1"을 누르고 Vasya도 "-1"을 누르면, 서버가 부하를 견디지 못해 시스템 장애가 일어나고, 레이팅은 절댓값이 주어진 $K$를 넘지 않는 임의의 정수만큼 바뀐다.

오늘 Petya와 Vasya는 논쟁을 끝내기로 했다. 하지만 블로그에 세 번째 독자가 생기면서 서버가 완전히 멈췄고, 최종 레이팅은 알 수 없게 되었다. 그래서 둘은 어떤 날 레이팅이 $M$을 초과하면 Petya가 이기고, 어떤 날 레이팅이 $-M$ 미만이면 Vasya가 이기는 것으로 정했다. 각자 언제 버튼을 눌렀는지를 바탕으로, 누가 이길 가능성이 있었는지, 그리고 그 일이 가장 일찍 일어날 수 있었던 날은 언제인지 구하라.

첫 줄에 정수 $N$, $M$, $K$, $R$이 주어진다 ($1 \le N,M,K \le 10^5$, $|R| \le 1000$, $|R| \le M$). $R$은 논쟁이 시작될 때의 Seryozha 블로그 레이팅이다.

다음 $N$개의 줄에는 정수 $a_i$와 $b_i$가 차례로 주어진다. $a_i = 1$이면 $i$번째 날 Vasya가 버튼을 눌렀고, $a_i = 0$이면 누르지 않았다. 마찬가지로 $b_i = 1$이면 $i$번째 날 Petya가 버튼을 눌렀고, $b_i = 0$이면 누르지 않았다.

출력 파일에 두 수를 출력한다. 첫 번째 수는 Petya가 이길 수 있었던 가장 이른 날 번호이고, 두 번째 수는 Vasya가 이길 수 있었던 가장 이른 날 번호이다. 해당 참가자가 이길 수 없었다면 그 자리에 $-1$을 출력한다.