一条直线上有 $n$ 盏路灯。这条路可以用一个数轴来表示。第 $i$ 盏路灯位于坐标 $x_i$ 处，并照亮道路的区间 $[\ell_{i}, r_{i}]$。最初，在时刻 $0$，所有路灯都是亮着的。随后，路灯会定期自动熄灭（关闭），并且有时会被重新打开。

每盏路灯都会定期自动熄灭。第 $i$ 盏路灯会在时刻 $a_i, a_i + t, a_i + 2 t, a_i + 3 t$ 等时刻自动熄灭。所有路灯的 $a_i$ 值以及常数 $t$ 都是已知的，其中 $t$ 对所有路灯都是相同的。

胆小的 Azber 住在道路的起点，即坐标 $x = 0$ 处。除了他居住的起点外，Azber 非常害怕经过任何没有被任何路灯照亮的位置。然而，如果 Azber 发现了一盏熄灭的路灯，且他能够从起点到达该路灯的位置，他就会跑得非常快去把这盏路灯重新打开，然后直接返回起点。Azber 移动得非常快，以至于他在这上面花费的时间可以忽略不计。

随着时间的推移，一些路灯会永久熄灭，再也不会被重新打开。你的任务是，对于每盏路灯，求出它处于亮起状态的最后一个时刻，或者确定这样的时刻永远不会到来。

输入格式

第一行包含两个整数 $n$ 和 $t$（$1 \leq n \leq 3 \cdot 10^5$，$1 \leq t \leq 10^9$）。

接下来的 $n$ 行描述路灯。其中第 $i$ 行描述第 $i$ 盏路灯，包含四个整数：$x_i$、$\ell_i$、$r_i$ 和 $a_i$（$0 < x_i \leq 10^9$，$0 \leq \ell_i < r_i \leq 10^9$，$0 < a_i \leq t$）。

输出格式

输出 $n$ 行。在第 $i$ 行中，如果第 $i$ 盏路灯永远不会永久熄灭，则输出 $-1$。

否则，输出一个整数：第 $i$ 盏路灯处于亮起状态的最后一个时刻。

样例

输入样例 1

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

输出样例 1

13
21
9
24

输入样例 2

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

输出样例 2

25
16
25
7

输入样例 3

2 7
2 0 5 3
3 0 2 4

输出样例 3

-1
-1