11월의 비

현대 건축물의 지붕은 매우 복잡한 모양일 수 있다. 이런 지붕을 수직으로 자른 단면은 여러 개의 기울어진 선분으로 이루어진다. 비가 오면 빗방울은 하늘에서 지붕으로 곧장 수직으로 떨어진다. 어떤 선분은 비에 완전히 노출되어 있지만, 어떤 선분은 위쪽의 다른 선분에 의해 일부 또는 전부 가려진다.

한 선분 위에 떨어진 물은 모두 그 선분을 따라 흘러내려, 선분의 아래쪽 끝에서 하나의 물줄기가 되어 수직으로 떨어진다. 이 물줄기는 땅으로 떨어지거나 다른 선분 위로 떨어진다. 특히, 물줄기가 어떤 선분의 끝점에 정확히 떨어지는 경우에도 그 선분이 물을 받는 것으로 본다.

배수 설비를 설계하기 위해, 각 선분에서 흘러내리는 물의 양을 알고자 한다. 1초 동안 수평면의 폭 1미터마다 물 1리터가 내린다고 하자.

지붕의 정보를 읽어, 각 선분에서 1초 동안 흘러내리는 물의 양(리터)을 구하는 프로그램을 작성하시오.

첫째 줄에 지붕을 이루는 선분의 개수 n (1 ≤ n ≤ 40000)이 주어진다. 다음 n개의 줄에는 각 선분을 나타내는 네 정수 x1, y1, x2, y2 (0 ≤ x1, y1, x2, y2 ≤ 1000000, x1 < x2, y1 ≠ y2)가 공백 하나로 구분되어 주어진다. (x1, y1)은 선분의 왼쪽 끝점, (x2, y2)는 오른쪽 끝점이며, x는 수평 위치, y는 높이를 나타낸다.

어떤 두 선분도 공통점을 갖지 않으며, 수평인 선분은 없다. 또한 땅의 어떤 한 점 위에도 선분은 최대 25개까지만 존재한다.

n개의 줄을 출력한다. i번째 줄에는 i번째 선분에서 1초 동안 흘러내리는 물의 양(리터)을 출력한다. 이 값은 항상 정수이다.