In the country of Logoria there are $$$N$$$ independent towns. Each town is located at a point of the plane with integer coordinates $$$(x_i, y_i)$$$.
At first, each town forms its own community. Then an era of conflicts begins. Each conflict involves two towns $$$a$$$ and $$$b$$$: after it, the communities to which towns $$$a$$$ and $$$b$$$ belong become a single community (it does not matter who wins the dispute). If $$$a$$$ and $$$b$$$ already belong to the same community, the conflict produces no change.
The territory of a community is the smallest convex region that contains all of its towns. The boundary of this territory is known as the convex hull of its points.
After each conflict, determine twice the area of the territory of the resulting community. If all the towns of a community lie on the same line, its area is considered to be zero. It can be shown that twice the area is always an integer.

Three towns forming a triangle of area $$$6$$$.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 2000$$$, $$$1 \leq M \leq 100000$$$), where $$$N$$$ is the number of towns and $$$M$$$ is the number of conflicts.
Each of the following $$$N$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-1000000 \leq x_i, y_i \leq 1000000$$$), the coordinates of the $$$i$$$-th town. The towns are numbered from $$$1$$$ to $$$N$$$, and all of them have distinct coordinates: $$$(x_i, y_i) \neq (x_j, y_j)$$$ for $$$i \neq j$$$.
Each of the following $$$M$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq N$$$), meaning that the communities containing towns $$$a$$$ and $$$b$$$ merge. A conflict may involve two towns that already belong to the same community.
Print $$$M$$$ lines. The $$$j$$$-th line must contain twice the area of the territory of the community that contains the towns of the $$$j$$$-th conflict, immediately after applying that conflict.
5 40 04 00 34 32 11 22 34 51 4
0 12 0 24
4 40 01 02 00 21 21 22 31 4
0 0 0 4
6 50 06 03 42 -24 -23 71 21 34 54 61 4
0 24 0 18 58
Explanation for example 1
Initially there are five independent towns: $$$\{1\}$$$, $$$\{2\}$$$, $$$\{3\}$$$, $$$\{4\}$$$ and $$$\{5\}$$$.
After the conflict between towns $$$1$$$ and $$$2$$$, the resulting community has only two towns, so the answer is $$$0$$$.
The conflict between $$$2$$$ and $$$3$$$ joins $$$\{1,2\}$$$ with $$$\{3\}$$$: the three towns form a triangle of area $$$6$$$, so twice that value, $$$12$$$, is printed.

Community $$$\{1,2,3\}$$$ forms a triangle with twice the area equal to $$$12$$$.
The conflict between $$$4$$$ and $$$5$$$ forms a community of two towns and again produces $$$0$$$.

In the same plane, community $$$\{4,5\}$$$ is just a segment (2 towns, area 0); community $$$\{1,2,3\}$$$ is shown in gray for reference.
Finally, the conflict between $$$1$$$ and $$$4$$$ joins $$$\{1,2,3\}$$$ with $$$\{4,5\}$$$. Town $$$5 = (2,1)$$$ lies inside the rectangle formed by the other four towns and does not change the boundary; that rectangle has area $$$12$$$, so the answer is $$$24$$$.

When the two communities (dashed lines) merge, town $$$5$$$ ends up in the interior of the new boundary (solid line).
Explanation for example 2
The first three towns lie on the same line, so as long as the community does not include town $$$4$$$ the answer is $$$0$$$; in particular, the second conflict ($$$1$$$-$$$2$$$) does not change the community, because $$$1$$$ and $$$2$$$ already belonged to $$$\{1,2\}$$$. When town $$$4$$$ joins, the hull becomes the triangle with vertices $$$(0,0)$$$, $$$(2,0)$$$ and $$$(0,2)$$$, whose doubled area is $$$4$$$.
Explanation for example 3
Conflicts $$$1$$$-$$$2$$$ and $$$1$$$-$$$3$$$ form community $$$\{1,2,3\}$$$, whose boundary is triangle $$$P_1P_2P_3$$$ (twice the area: $$$24$$$).

Community $$$\{1,2,3\}$$$ forms a triangle with twice the area equal to $$$24$$$.
Independently, conflicts $$$4$$$-$$$5$$$ and $$$4$$$-$$$6$$$ form $$$\{4,5,6\}$$$, with boundary $$$P_4P_5P_6$$$ (twice the area: $$$18$$$).

In the same plane, community $$$\{4,5,6\}$$$ forms a triangle with twice the area equal to $$$18$$$ (community $$$\{1,2,3\}$$$ is shown in gray for reference).
Conflict $$$1$$$-$$$4$$$ joins both communities. The new boundary is pentagon $$$P_1P_4P_5P_2P_6$$$, and town $$$3$$$ ends up in its interior despite having been a vertex of its own community's boundary just before the merge: this is why it is not enough to combine the two previous boundaries; the convex hull of the union must be recomputed. Twice the area of the pentagon is $$$58$$$.

When the two communities (dashed lines) merge, town $$$3$$$ stops being a vertex of the new boundary (solid line).
| Название |
|---|


