题目描述

本题的所有讨论均在平面直角坐标系上进行。

有 $N$ 个人，每个人有一个视野，同时每个人在 $(x_i,0)$ 的位置上。

视野可抽象为一个角。

注意，组成角的两条射线未在视野内。

现在，您可以站在 $(a,Y)$ 上，其中 $L\le a\le R$。

请求出，对于每个 $i(0\le i\le N)$，您可以站在多少个位置，使得您至多在 $i$ 个人的视野内。

输入格式

第一行为一个整数 $N$。

第二行为三个整数 $L,R,Y$。

接下来 $N$ 行，每行三个整数，分别为 $x_i,v_i,h_i$，其中 $v_i$ 和 $h_i$ 表示，组成角的两条射线的斜率分别为 $\frac{v_i}{h_i},\frac{-v_i}{h_i}$，一端的端点为 $(x_i,0)$。

输出格式

共 $N+1$ 行，每行一个整数，第 $i$ 行的数表示您可以站在的位置个数，使得您至多在 $i-1$ 个人的视野内。

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

5
12
15
15

提示

样例解释

子任务

本题采用捆绑测试。

• Subtask 1（$60$ 分）：保证 $-10^6\le L\le R\le 10^6$。
• Subtask 2（$40$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le N\le 10^5$，$-10^9\le L \le R\le 10^9$，$1\le Y\le 10^6$，$1\le x_i\le R$，$1\le v_i,h_i\le 100$。

说明

本题译自 Canadian Computing Olympiad 2020 Day 1 T1 A Game with Grundy。