Pie Exchange

Bessie and Elsie have each baked \(N\) pies (\(1 \le N \le 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 considering 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. In order not to appear stingy nor flamboyant, Elsie will try to pick a pie which, according to her own judgement, is at least as tasty as the one she received, but no more than \(D\) units tastier (\(0 \le D \le 10^9\)). If such a pie does not exist, Elsie will adopt a pseudonym and exile herself to Japan.

If Elsie does give Bessie a pie in return, then Bessie will similarly try to give Elsie a pie that is at least as tasty (in Bessie's eyes) as the pie Elsie just gave her, but no more than \(D\) units tastier. If this is impossible, Bessie too will exile herself. Otherwise the cycle continues.

The exchange stops in one of two ways:

• If one of the cows receives a pie which she accords a tastiness value of \(0\), then the gift exchange ends and both cows are happy.
• If at any step the cow whose turn it is cannot find a valid pie to give, she exiles herself and the exchange is unhappy.

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 that 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. If it is impossible to reach a happy outcome for a given starting pie, output \(-1\) for that pie.

Input and output are described below.

inputFormat

The first line contains two integers \(N\) and \(D\), where \(N\) is the number of pies each cow baked and \(D\) is the maximum allowed tastiness increase in any gift (\(1 \le N \le 10^5\), \(0 \le D \le 10^9\)).

The next \(N\) lines each contain two integers. The \(i\)th line describes one of Bessie's pies with two integers \(B_i\) and \(E_i\) denoting its tastiness value according to Bessie and Elsie respectively.

The following \(N\) lines each contain two integers. The \(j\)th line describes one of Elsie's pies with two integers \(E^B_j\) and \(E^E_j\) denoting its tastiness value according to Bessie and Elsie respectively.

You may assume that all tastiness values are non‐negative integers.

outputFormat

Output \(N\) lines. The \(i\)th line should contain a single integer: the minimum number of pies that must be gifted (including the initial gift) in order for the exchange to result in a cow receiving a pie with tastiness \(0\) from her own perspective. If it is impossible for the exchange to end happily when starting with the \(i\)th Bessie pie, output \(-1\) instead.

sample

3 1
5 1
3 0
4 2
0 4
6 3
5 5

-1
1
-1

</p>