A Pie for a Pie

Bessie and Elsie have each baked $N$ pies ($1 \le N \le 10^5$). Every one of the $2N$ pies has a tastiness value according to Bessie and a tastiness value according to Elsie, and the two values may differ.

Bessie is thinking about giving one of her pies to Elsie. If Elsie receives a pie from Bessie, she feels obliged to hand back one of her own pies. So as to look neither stingy nor extravagant, Elsie picks a pie that in her own eyes is at least as tasty as the pie she received but no more than $D$ units tastier ($0 \le D \le 10^9$). If no such pie exists, Elsie gives up and the exchange ends unhappily.

If Elsie does hand back a pie, Bessie then picks one of her own pies that in her own eyes is at least as tasty as the pie Elsie just gave her but no more than $D$ units tastier. If she has no such pie, Bessie gives up too and the exchange again ends unhappily. Otherwise she gives the chosen pie to Elsie, and the cycle repeats until one cow gives up or until a cow receives a pie she values at $0$. Receiving a pie worth $0$ ends the exchange and both cows are happy.

A pie is never gifted twice, and neither cow hands back the pie she has just received.

For each of the $N$ pies Bessie could choose as her first gift, find the smallest number of pies that can change hands in a happy exchange.

The first line contains two integers $N$ and $D$.

Each of the next $2N$ lines contains two space separated integers: the value of one pie according to Bessie, then the value of that same pie according to Elsie.

The first $N$ of those lines describe Bessie's pies and the remaining $N$ lines describe Elsie's pies.

Every tastiness value is in the range $[0, 10^9]$.

Print $N$ lines. Line $i$ contains the smallest number of pies that can be gifted in a happy exchange that starts with Bessie's pie $i$, counting that first gift. If no exchange that starts with pie $i$ ends happily, print $-1$ on line $i$ instead.