本题没有可用的提交语言。

描述

Zing Zhu 拥有一座平坦的岛屿。每天涨潮时，海水会淹没岛屿。经过深思熟虑并咨询家人意见后，Zing Zhu 决定在岛上建立牡蛎养殖场。他使用一套复杂的防水塑料模块化围栏系统来控制涨潮时被淹没和未被淹没的区域。这些围栏是水平或垂直的条状物，具有不同的长度和高度。两条围栏最多只能在一个点相交，不一定是端点。

你需要为 Zing Zhu 计算，在给定潮水高度及所有围栏条的位置和高度后，岛屿中在涨潮时不会被淹没的区域总面积。假设围栏的宽度相对于岛屿的尺寸非常细小，因此在计算总面积时，可将围栏视为宽度为 0 的线段。

输入

输入包含多个测试用例。每个测试用例的第一行是一个整数 N，表示岛屿上的围栏条数（1≤N≤2000）。接下来 N 行，每行包含五个整数 X1、Y1、X2、Y2 和 H，分别表示围栏条的起点 (X1,Y1)、终点 (X2,Y2) 和围栏高度（H）。每个测试用例的最后一行是一个整数 W，表示潮水高度。坐标单位为米，高度单位为厘米。保证 X1=X2 或 Y1=Y2（但不同时满足）；−500≤X1,Y1,X2,Y2≤500；且 1≤W,H≤1000。输入以 N=0 结束。

输出

对于每个测试用例，输出一行，包含一个整数，表示未被淹没的区域总面积（单位为平方米）。

输入样例

4
-20 20 20 20 200
20 20 20 -20 200
0 0 0 20 100
-10 0 20 0 200
100
4
-20 20 20 20 200
20 20 20 -20 200
0 0 0 20 100
-10 0 20 0 200
101
0

输出样例

400
0

来源

南美洲区域赛 2004