Onions are widely used in cuisines around the world. This problem is about an "onion peeling" process in geometry.
A set of points in a two-dimensional plane is convex if, for any pair of points and in the set, the line segment connecting and is entirely contained in the set. For a set of points , its convex hull is the smallest convex set containing all points in .
You are given four integers , , , and . You have a set of points, initialized as follows:
You apply the following operation times: let be the convex hull of the set , and then remove from all points that lie on the boundary of the convex hull .
Note that can become empty. In that case, its convex hull is also empty, and its area is zero.
For each operation, determine the doubled area of the convex hull . It can be shown that this value is always an integer.
输入格式
The input consists of a single line containing four integers , , , and ( ; ; ).
输出格式
Output lines. The -th line should contain an integer representing the doubled area of the convex hull in the -th operation.
样例
样例输入 1
4 1 2 1
样例输出 1
8
样例输入 2
37 14 7 5
样例输出 2
2257
1406
592
74
0
数据范围与提示
Explanation for the sample input/output #1
Figure L.1 illustrates the points in and the boundary of the convex hull in the first operation. The area of the convex hull is , and thus the doubled area is .
Figure L.1: Illustration of Sample Input #1.Explanation for the sample input/output #2
Figure L.2 illustrates the boundaries in the first four operations. The set becomes empty after the fourth operation. The area for the fifth operation is .
