[USACO17DEC] A Pie for a Pie G

原翻译出锅严重且有机翻痕迹，请尽快更换新的翻译 ```plain Bessie和Elsie各自烤了$N\:(1≤N≤10^5)$个馅饼）。Bessie 会这$2N$个馅饼打分，Elsie 也会。二者的打分均为一个$\le 10^9$的非负整数。由于她们口味不同，每个派的两个分数可能不同。 她们想互赠礼物。开始时，Bessie 送给 Elsie 一个馅饼。她们收到礼物（对方做的馅饼）后都会回赠对方一个自己做的馅饼。 她们选择回礼的方法相同。以 Elsie 为例，Elsie **根据自己的打分**来选择回礼。回礼的分数至少要大于她收到的馅饼的分数，但两个馅饼的分数差不能大于$D\:(0≤D≤10^9)$。如果有多个馅饼满足要求，Elsie 可以选择其中的任意一个作为回礼。若没有馅饼满足要求，Elsie 会放弃。Bessie 选择回礼的方法同理。 她们之间的礼物交换将持续到一头牛放弃（Bad End），或一头牛收到一个她自己打分为$0$的馅饼，此时礼物交换愉快结束（Happy End）。 请注意，不能把一个馅饼赠送两次，不能把馅饼送给自己。 Bessie 想知道：对于每个她做的馅饼，如果她将这个馅饼作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼（Bessie 给 Elsie 算一次，Elsie 回赠 Bessie 又算一次），才能 Happy End 。如果不可能 Happy End，请输出 `-1`。 #### 输入格式 第一行有两个整数 $N, D$。 在接下来的$2N$行中，每行有两个整数，表示对于某个馅饼，Bessie 的打分和 Elsie 的打分。其中，前$N$行表示 Bessie 做的馅饼，后$N$行则是 Elsie 做的馅饼。 #### 输出格式 输出共$N$行，每行一个整数。 第$i$行的整数表示：如果 Bessie 将馅饼$i$作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼才能 Happy End 。如果不可能 Happy End，请在该行输出 `-1`。 ``` Bessie和Elsie各自烤了 $N\:(1≤N≤10^5)$ 个馅饼）。Bessie 会这 $2N$ 个馅饼打分，Elsie 也会。二者的打分均为一个 $\le 10^9$ 的非负整数。由于她们口味不同，每个派的两个分数可能不同。 她们想互赠礼物。开始时，Bessie 送给 Elsie 一个馅饼。她们收到礼物（对方做的馅饼）后都会回赠对方一个自己做的馅饼。 她们选择回礼的方法相同。以 Elsie 为例，Elsie **根据自己的打分**来选择回礼。回礼的分数至少要大于她收到的馅饼的分数，但两个馅饼的分数差不能大于 $D\:(0≤D≤10^9)$ 。如果有多个馅饼满足要求，Elsie 可以选择其中的任意一个作为回礼。若没有馅饼满足要求，Elsie 会放弃。Bessie 选择回礼的方法同理。 她们之间的礼物交换将持续到一头牛放弃（Bad End），或一头牛收到一个她自己打分为 $0$ 的馅饼，此时礼物交换愉快结束（Happy End）。 请注意，不能把一个馅饼赠送两次，不能把馅饼送给自己。 Bessie 想知道：对于每个她做的馅饼，如果她将这个馅饼作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼（Bessie 给 Elsie 算一次，Elsie 回赠 Bessie 又算一次），才能 Happy End 。如果不可能 Happy End，请输出 `-1`。 #### 输入格式 第一行有两个整数 $N, D$。 在接下来的 $2N$ 行中，每行有两个整数，表示对于某个馅饼，Bessie 的打分和 Elsie 的打分。其中，前 $N$ 行表示 Bessie 做的馅饼，后 $N$ 行则是 Elsie 做的馅饼。 #### 输出格式 输出共 $N$ 行，每行一个整数。 第 $i$ 行的整数表示：如果 Bessie 将馅饼 $i$ 作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼才能 Happy End 。如果不可能 Happy End，请在该行输出 `-1`。 翻译者：Planet6174

Bessie and Elsie have each baked $N$ pies ($1 \leq N \leq 10^5$). Each of the $2N$ pies has a tastiness value according to Bessie and a (possibly different) tastiness value according to Elsie. Bessie is thinking about giving one of her pies to Elsie. If Elsie receives a pie from Bessie, she will feel obligated to give one of her pies to Bessie. So as to not appear stingy nor flamboyant, Elsie will try to pick a pie that is at least as tasty (in Elsie's eyes) as the pie she received, but no more than $D$ units tastier ($0 \leq D \leq 10^9$). Such a pie may not exist, in which case Elsie will adopt a pseudonym and exile herself to Japan. But if Elsie does give Bessie a pie in return, Bessie will similarly try to give Elsie a pie which is at least as tasty but no more than $D$ units tastier (in Bessie's eyes) as the pie Elsie just gave her. Should this be impossible, Bessie too will exile herself. Otherwise she will give her chosen pie to Elsie. This cycle will continue until one of the cows is exiled, an unhappy outcome, or one of the cows receives a pie which she accords a tastiness value of $0$, in which case the gift exchange will end and both cows will be happy. Note that a pie may not be gifted twice, nor can either cow return a pie gifted to her. For each of the $N$ pies Bessie could select as her initial gift to Elsie, determine the minimum number of pies that could possibly be gifted in the resulting exchange before the cows are happy.

The first line contains the two integers $N$ and $D$. The next $2N$ lines contain two space-separated integers each, respectively denoting the value of a particular pie according to Bessie, and the value of that pie according to Elsie. The first $N$ lines refer to Bessie's pies, and the remaining $N$ lines refer to Elsie's pies. It is guaranteed that all tastiness values are in the range $[0,10^9]$.

There should be $N$ lines in the output. Line $i$ should contain a single integer: the minimum number of pies that could be gifted in a happy gift exchange started with Bessie's pie $i$. If no gift exchange starting with pie $i$ is happy, then line $i$ should contain the single integer $-1$ instead.

2 1
1 1
5 0
4 2
1 4

3
1