To ask why we fight?
Is to ask why the leaves fall?
It is in the nature.
Perhaps there is a better question.
Why do we fight?
To protect home and family,
To preserve balance and bring harmony.
For my kind,
The true question is what is worth fighting for.
——CG《Mists of Pandaria》
Chen is practicing Kungfu. He uses Chi Burst to make energy points split.
Initially, there are nn energy points on the infinite 2D plane, in every second, every energy point will check its four neighbouring positions (up (0, 1), down (0, -1), left (-1, 0), right (1, 0) ) If there is no energy point at that position, a new energy point will be generated at that position.
Chen would like to know the progress of the practice in advance. He will give you qqqueries, each query consists of a single integer t, and you need to find the area of the convex polygon constructed by all energy points after t seconds.
The input consists of multiple test cases.
The first line contains a single integer T (1≤T≤11), denoting the number of test cases.
In each test case, the first line contains two integers n,q(1≤n,q≤2∗105), denoting the number of points initially and the number of queries.
The following n lines, the i-th line contains two integers x,y(0≤x,y≤108), denoting the coordinate of the i-th initial energy point.
Then following q lines, each line contain one integer t(0≤t≤108), denoting the number of seconds.
It's guaranteed that ∑n≤5∗105,∑q≤5∗105.
2
3 3
2 3
4 3
1 1
1
2
3
3 3
4 1
3 4
2 1
2
3
411.0
24.0
41.0
27.0
45.0
67.0