There are $n$ streetlights on a straight road. The road can be represented as a number line. The $i$-th streetlight is located at coordinate $x_i$ and illuminates the segment $[\ell_{i}, r_{i}]$ of the road. Initially, at time $0$, all streetlights are on. Then streetlights go out (turn themselves off) automatically at regular intervals, and sometimes are turned back on.

Each streetlight turns itself off at regular intervals. The $i$-th streetlight turns itself off at times $a_i$, $a_i + t$, $a_i + 2 t$, $a_i + 3 t$, and so on. The values $a_i$ for all streetlights are known, as well as the constant $t$, which is the same for all streetlights.

Azber the Timid lives at the origin of the road, at coordinate $x = 0$. Azber is too scared to pass a point that is not illuminated by any streetlight, except for the origin where he lives. However, if Azber notices a turned off streetlight that he can reach from the origin, he runs very fast, turns the streetlight back on, and comes back directly to the origin. Azber moves so fast that the time he spends on this can be ignored.

Over time, some streetlights go out and are never turned on again. Your task is, for each streetlight, to find the last moment when it is on, or determine that such a moment never comes.

Input

The first line contains two integers: $n$ and $t$ ($1 \leq n \leq 3 \cdot 10^5$, $1 \leq t \leq 10^9$).

The next $n$ lines describe streetlights. The $i$-th of these lines describes the $i$-th streetlight and contains four integers: $x_i$, $\ell_i$, $r_i$, and $a_i$ ($0 < x_i \leq 10^9$, $0 \leq \ell_i < r_i \leq 10^9$, $0 < a_i \leq t$).

Output

Print $n$ lines. On the $i$-th line, if the $i$-th streetlight never goes out permanently, print $-1$. Otherwise, print a single integer: the last moment the $i$-th streetlight is on.

Examples

Input 1

4 10
5 0 4 3
2 0 3 1
7 2 6 9
3 7 8 4

Output 1

13
21
9
24

Input 2

4 10
3 4 5 5
7 0 4 6
5 0 6 5
8 0 7 7

Output 2

25
16
25
7

Input 3

2 7
2 0 5 3
3 0 2 4

Output 3

-1
-1