题目描述

现代建筑的屋顶结构可能非常复杂。如果我们对这样的屋顶进行垂直剖面，会得到许多倾斜的线段。下雨时，雨滴会从正上方的天空垂直落在屋顶上。有些线段完全暴露在雨中，但也可能有些线段被其他线段部分或完全遮挡。所有落在某一线段上的雨水会以垂直流的形式从该线段的较低端点流到地面，或者可能流到其他线段上。特别地，如果雨水流到某一线段的端点，则认为该线段收集了这部分雨水。

为了设计排水系统，需要计算屋顶每条线段流下的雨水量。为了应对11月的暴雨，你需要计算在1秒内每平方米水平面上落下的雨水为1升的情况下，每条线段流下的雨水量。

任务

编写一个程序：

1. 读取屋顶的描述；
2. 计算每条线段在1秒内流下的雨水量；
3. 输出结果。

输入格式

第一行包含一个整数n（1 ≤ n ≤ 40000），表示屋顶的线段数量。接下来的n行每行描述一条线段，包含四个整数x1, y1, x2, y2（0 ≤ x1, y1, x2, y2 ≤ 1000000，x1 < x2，y1 ≠ y2），用空格分隔。整数x1, y1分别是线段左端点的水平位置和高度，x2, y2分别是线段右端点的水平位置和高度。线段之间没有交点，且没有水平线段。此外，可以假设地面上任意一点上方最多有25条线段。

输出格式

输出包含n行，第i行表示第i条线段在1秒内流下的雨水量（单位为升）。

输入样例 1

6
13 7 15 6
3 8 7 7
1 7 5 6
5 5 9 3
6 3 8 2
9 6 12 8

输出样例 1

2
4
2
11
0
3

来源

中欧 2003