A park can be viewed as an infinite two-dimensional plane. There are $n$ street lamps in the park, labeled $1, 2, \dots, n$. Each street lamp can be viewed as a point in the two-dimensional plane.

Little A and his mother are visiting this park. His mother tells Little A not to run too far, so he can only play within a rectangular region with its bottom-left corner at $(0, 0)$ and its top-right corner at $(X, Y)$ (Little A can reach the boundary of the rectangle).

Little A is very interested in the $i$-th street lamp. He wants to find a location (let's call it point $P$) within the rectangle, and then let $d_k(P)$ be the distance from the $k$-th ($1 \le k \le n$) street lamp to $P$. After that, if $d_i(P)$ is the $j$-th smallest distance, meaning there are exactly $j-1$ distances strictly smaller than $d_i(P)$, then $P$ is called a "good point".

Little A wants to know: what is the total area formed by all good points $P$? If no good points exist, the area is 0. You need to find the corresponding answer for every pair $(i, j)$ ($1 \le i, j \le n$).

Input

Read the data from the file park.in.

The first line of the input contains three positive integers $n, X, Y$, representing the number of street lamps in the park and the coordinates of the top-right corner of the rectangular region where Little A can play.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th street lamp. It is guaranteed that all street lamp coordinates are distinct.

The street lamps are not necessarily outside the rectangular region; they may be on the boundary or inside.

Output

Output to the file park.out.

Output an $n \times n$ matrix of real numbers (it is recommended to keep no more than 10 decimal places for each real number to prevent the output file from becoming too large), where the $i$-th row and $j$-th column represent the answer for the pair $(i, j)$. Separate two numbers in the same row with a space.

The contestant's output is considered correct if the relative or absolute error compared to the standard program's output does not exceed $10^{-6}$.

Examples

Input 1

1 3 1 1
2 -1 0
3 0 1
4 1 -1

Output 1

0.00000000 0.50000000 0.50000000
0.93750000 0.06250000 0.00000000
0.06250000 0.43750000 0.50000000

Note 1

Example 1 is shown in Figure 1. Region 1 is the trapezoid BGHD, Region 2 is the polygon GFJIH, and Region 3 is the triangle JEI, with areas $S_1 = \frac{1}{2}$, $S_2 = \frac{7}{16}$, and $S_3 = \frac{1}{16}$, respectively. These regions do not include their boundaries.

Figure 1: Illustration of Example 1

For points $P$ in Region 1, $d_1(P) > d_2(P)$, $d_1(P) > d_3(P)$, and $d_2(P) > d_3(P)$ are satisfied. For points $P$ in Region 2, $d_1(P) > d_2(P)$, $d_3(P) > d_1(P)$, and $d_2(P) > d_3(P)$ are satisfied. For points $P$ in Region 3, $d_1(P) > d_2(P)$, $d_3(P) > d_1(P)$, and $d_3(P) > d_2(P)$ are satisfied.

Therefore, for the first point: There is no region where $d_1(P)$ is the 1st smallest, so output 0. In Regions 2 and 3, $d_1(P)$ is the 2nd smallest, so output $\frac{7}{16} + \frac{1}{16} = \frac{1}{2}$. * In Region 1, $d_1(P)$ is the 3rd smallest, so output $\frac{1}{2}$.

Input 2

3 2 2
-2 1
2 4
4 1

Output 2

1.73958333 0.77083333 1.48958333
0.76041667 1.89583333 1.34375000
1.50000000 1.33333333 1.16666667

Input 3

3 3 3
3 5
-4 3
3 -5

Output 3

8.27678571 0.72321429 0.00000000
0.72321429 5.84598214 2.43080357
0.00000000 2.43080357 6.56919643

Examples 4

See park/park4.in and park/park4.ans in the contestant directory. This example satisfies the constraints for test cases 1 ~ 4.

Examples 5

See park/park5.in and park/park5.ans in the contestant directory. This example satisfies the constraints for test cases 5 ~ 7.

Examples 6

See park/park6.in and park/park6.ans in the contestant directory. This example satisfies the constraints for test cases 8 ~ 10.

Examples 7

See park/park7.in and park/park7.ans in the contestant directory. This example satisfies the constraints for test cases 11 ~ 12.

Examples 8

See park/park8.in and park/park8.ans in the contestant directory. This example satisfies the constraints for test cases 13 ~ 14.

Examples 9

See park/park9.in and park/park9.ans in the contestant directory. This example satisfies the constraints for test cases 15 ~ 20.

Constraints

For all test data, it is guaranteed that: $1 \le n \le 200$, $X, Y, |x_i|, |y_i| \le 10^6$.

Special Property A: These $n$ points all lie on the same circle. Special Property B: These $n$ points all lie on the same straight line.