그런디와의 게임
시간 제한1초메모리 제한512 MB
L 이상 R 이하인 정수 x마다 N개의 삼각형 시야 안에 엄격히 들어가는 친구 수를 세고, 0부터 N까지 각 i 이하인 위치의 개수를 구한다.
문제
그런디는 자신이 가장 좋아하는 게임인 숨바꼭질을 하고 있다.
그런디의 친구 N명이 2차원 평면의 x축 위에 서 있다. i번째 친구는 좌표 (xi, 0)에 있다. 각 친구는 자신의 위치에서 수직으로 위쪽으로 뻗어 나가는 삼각형 모양의 영역을 볼 수 있다. i번째 친구의 시야 삼각형은 기울기가 vi/hi인 직선과 기울기가 −vi/hi인 직선 두 개로 정해진다. 친구는 이 두 직선 위에 정확히 놓인 점은 볼 수 없다.
그런디는 (a, Y) 위치에 숨을 수 있다. 여기서 a는 L ≤ a ≤ R을 만족하는 정수이고, L, R, Y는 주어지는 정수 상수이다.
각 위치는 그런디의 친구 일부의 시야에 들어갈 수 있다. 정확히는 친구의 시야 삼각형 내부에 엄격하게 들어갈 때이다.
그런디는 i가 0부터 N까지일 때, 친구가 많아야 i명인 위치가 몇 군데인지 알고 싶어 한다.
입력
첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 100 000)
다음 줄에 세 정수 L, R, Y가 주어진다. (−1 000 000 000 ≤ L ≤ R ≤ 1 000 000 000, 1 ≤ Y ≤ 1 000 000)
다음 N개 줄에는 각각 세 정수가 주어진다. i번째 줄에는 친구 i의 위치의 x값 xi (L ≤ xi ≤ R)와 두 정수 vi, hi가 순서대로 주어진다. (1 ≤ vi, hi ≤ 100) 기울기 vi/hi와 −vi/hi가 친구 i의 시야 삼각형을 정한다.
출력
N + 1개 줄을 출력한다. i번째 줄 (0 ≤ i ≤ N)에는 그런디가 서 있을 수 있으면서 친구가 많아야 i명인 위치의 개수를 정수로 출력한다.
힌트
세 친구의 시야 삼각형과 그런디가 있을 수 있는 위치가 아래 그림에 나와 있다.
점 (2, 3)과 (4, 3)은 위치 3에 있는 친구의 시야 삼각형 경계 위에 있으므로, 위치 0에 있는 친구만 볼 수 있다.