Grundy 正在玩他最喜欢的游戏——捉迷藏。

他的 $N$ 个朋友站在二维平面的 $x$ 轴上，第 $i$ 个朋友位于坐标 $(x_i, 0)$。每个朋友都能看到从他们所在位置垂直向上延伸的三角形区域内的物体——第 $i$ 个朋友的三角形视野由两条直线确定：一条斜率为 $v_i/h_i$，另一条斜率为 $-v_i/h_i$。如果一个点恰好位于这两条直线上，则朋友无法看到该点。

Grundy 可以选择躲在任何位置 $(a, Y)$，其中 $a$ 是满足 $L \le a \le R$ 的整数，$L, R$ 和 $Y$ 是给定的整数常量。

每个可能的位置都可能处于 Grundy 的某些朋友的视野内（即严格位于他们的三角形视野内）。

Grundy 想知道，对于从 $0$ 到 $N$ 的每一个可能的 $i$，他有多少种不同的站立位置，使得他处于至多 $i$ 个朋友的视野内。

输入格式

第一行包含整数 $N$ ($1 \le N \le 100\,000$)。

第二行包含三个整数：$L, R$ 和 $Y$ ($-1\,000\,000\,000 \le L \le R \le 1\,000\,000\,000$，$1 \le Y \le 1\,000\,000$)。

接下来的 $N$ 行，每行包含三个整数：第 $i$ 行包含朋友 $i$ 的位置的 $x$ 坐标 $x_i$ ($L \le x_i \le R$)，以及两个整数 $v_i$ 和 $h_i$ ($1 \le v_i, h_i \le 100$)。斜率 $v_i/h_i$ 和 $-v_i/h_i$ 定义了朋友 $i$ 的三角形视野。

对于 25 分中的 15 分，满足 $-1\,000\,000 \le L \le R \le 1\,000\,000$。

输出格式

输出共 $N+1$ 行，其中第 $i$ 行（$0 \le i \le N$）包含 Grundy 可以站立且处于至多 $i$ 个朋友视野内的位置数量。

样例

输入 1

3
-7 7 3
0 2 3
-4 2 1
3 3 1

输出 1

5
12
15
15

说明

有三位朋友，他们的三角形视野以及 Grundy 可以放置的位置如下图所示：

注意，点 $(2, 3)$ 和 $(4, 3)$ 仅被位于位置 $0$ 的朋友看到，因为它们位于位于位置 $3$ 的朋友的三角形视野边界上。