Blog Rating Game

Petya and Vasya are ordinary boys and the only readers of Seryozha's ordinary blog. Petya likes the blog very much, and Vasya dislikes it exactly as much. The two love to argue. $N$ days ago, when the blog rating was $R$, they argued about how much the rating would change over these $N$ days.

On some days Petya pressed the "+1" button and raised the rating by 1. Likewise, Vasya sometimes pressed the "-1" button and lowered the rating by 1. If on some day Petya pressed "+1" and Vasya pressed "-1" as well, the server could not handle the load, a system failure happened, and the rating changed by an arbitrary integer whose absolute value does not exceed a given number $K$.

Today Petya and Vasya decided to settle the argument. However, a third reader joined the blog, the server stopped working altogether, and the final rating is unknown. So they agreed that Petya wins if on some day the rating is greater than $M$, and Vasya wins if on some day the rating is less than $-M$. Using the days on which each of them pressed the buttons, find who had a chance to win, and the earliest day on which that could have happened.

The first line contains four integers $N$, $M$, $K$, and $R$ ($1 \le N,M,K \le 10^5$, $|R| \le 1000$, $|R| \le M$). $R$ is the rating of Seryozha's blog at the start of the argument.

Each of the next $N$ lines contains two integers $a_i$ and $b_i$. $a_i = 1$ if Vasya pressed his button on day $i$, and $a_i = 0$ otherwise. Likewise, $b_i = 1$ if Petya pressed his button on day $i$, and $b_i = 0$ otherwise.

Print two numbers. The first is the smallest day number on which Petya could have won, and the second is the smallest day number on which Vasya could have won. If a player could not win, print $-1$ in place of that day number.