Niuniu has N directed segments. Each segment has one color. He wants to make a powerful sword by connecting the segments. He can choose at most K segments. He isn’t allowed to choose more than one segment from each color, or rotate segments. The powerfulness of the sword is calculated by the square of the distance between the beginning of the first segment and the end of the last segment. Niuniu wants to know the largest powerfulness when K = 1,…, N.
The input has the format as described below.
N
x1 y1 c1
x2 y2 c2
...
xn yn cnN is the number of segments. (1 ≤ N ≤ 1000) The ith segment starts at (0,0), ends at(xi,yi), with color ci. (-1000000 ≤ xi,yi ≤ 1000000, xi2+yi2>0, 1 ≤ ci ≤ n)
You should output the answers in one line, separated by a space.
You can consider the segment in this problem as 2D vector.