Ферма Фермера Джона полна пышной растительности и каждая корова хочет
получить фото этой естественной красоты. К сожалению, Беси еще есть куда пойти,
но она не хочет мешать фотосессиям.
Беси расположена в точке \((X,0)\) на координатной XY-плоскости и хочет попасть
в точку \((0,Y)\) (\(1\le X,Y\le 10^6\)). К несчастью, \(N\) (\(1 \leq N \leq 3 \cdot 10^5\))
других коров решили позировать на оси \(X\). Точнее, корова \(i\) находится в точке
\((x_i,0)\) а фотограф находится в точке \((0,y_i)\) где \((1 \leq x_i,y_i \leq 10^6)\)
и он приготовился делать снимок. Они начинают съёмки перед моментом времени \(s_i\) (\(1 \leq s_i < T\))
и фоткаются очень долго, \(1\le T\le N+1\).
Беси знает расписание фотографирования всех коров, и хочет пройти по кратчайшему
Евклидовому расстоянию от своей начальной точки к своей конечной точке без пересечения
линии обзора между коровой и её фотографом (путь Беси может состоять из одного или более
отрезков прямой).
Если Беси выходит в момент времени \(t\), она избежит линии обзора для всех пар
корова/фотограф, которые начинают позировать в момент времени \(s_i \le t\),
и пусть расстояние к её конечной точке равно \(d_t\). Определите величины
\(\lfloor d_t\rfloor\) для каждого целого \(t\) от \(0\) до \(T-1\) включительно.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(N\) и
\(T\), представляющие количество коров на оси
\(x\)
и временной интервал в течение которого Беси может начать свой поход.
Вторая строка содержит \(X\) и \(Y\), представляющих стартовую \(X\)-позицию Беси
и финишную \(Y\)-позицию, соответственно.
Последующие \(N\) строк содержат \(s_i\) \(x_i\) \(y_i\). Гарантируется, что
все \(x_i\) различны и все \(y_i\) различны. Все \(s_i\) будут заданы в порядке
возрастания, где \(s_i \leq s_{i+1}\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(T\) строк, где \(t\)-ая строка (0-индексированная) содержит
\(\lfloor d_t\rfloor\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
6 7
1 7 5
2 4 4
3 1 6
4 2 9
|
9
9
9
10
12
|