The one half of the figure can be translated into the other by some linear transformation. Let's iterate over all possible transformations. There are three important parameters of a transformation:

1) translation by X axis from -50 to 50 and by Y axis from -50 to 50

2) rotation on 0/90/180/270 degrees

3) mirroring — yes or no

This gives us a total of 101x101x4x2 transformations.

For each transformation, let's consider an oriented graph, where vertices are cells of the figure and edge (u,v) means that cell u is transformed to cell v by this transformation.

Our transformations are invertable, so there are at most one incoming and at most one outcoming edge for each vertex.

Because of this, the graph is formed by cycles and chains. If all cycles and chains are of even length, we can color the graph vertices in red and blue so that no edge connects vertices of same color. The red and blue parts of graph would mean the two parts of the input figure.

If for each transformation there is at least one cycle or chain of odd length, the answer is Impossible.

Answer is YES if there is cycle in graph or cell with three or four free neighbours.

For size i we need to find i-th smallest index of friend among friends going to the party of that size.

It can be done next way: iterate over party size from 1 to N. For size i:

1. remove from data structure friends, whose maxSize[friend] == i — 1;
2. add to data structure friends, whose minSize[friend] == i;
3. ask data structure i-th smallest index in it.

Segment tree can perform these operations with O(logN) complexity, it is enough in this problem.

Let's build data structure, that can perform next operations on array 'a':

1. a[l..r] += value;
2. index of max(a[1..n]);
3. a[i] = value; // can be done as a[i] += (value — a[i]);

Segment tree can perform all these operations with O(logN) or O(sqrtN) complexity, it is enough in this problem.

Idea of solution:

Initialize out data structure with values (-1, -2, -3, ..., -n) for indexes 1..n.

Iterate over friends from 1 to N, for friend with index i do:

1. a[minSize[friend]..maxSize[friend]] += 1;
2. Let's j = index of max(a[1..n]).
3. If (a[j] < 0) — continue.
4. Else a[j] == 0 — phone calls about party with size j will be stopped at i-th friend — we can update answer[j] = i.
5. Set a[j] = NEGATIVE_INFINITY (some value < -n) — each party size can be stopped only once (we 'remove' party size j from next answer updating).

is parallel binary search. For every k = 1... N, set initial lower and upper bound as 1 and N. Then iterate over the array times, and using an auxiliary data structure like a BIT narrow the range for each query down as you arrive at its mid-point. This is O(N × log²N), read more about the technique here

p1 is moving with velocity vector v1 and p2 is moving with velocity vector v2. Relative to p1, p2 starts at p2 — p1, and is moving with velocity vector v2 — v1, Then, you want the closest point on this ray to the origin, which is almost the same as the point-line segment distance problem and can be solved using a very similar formula.

We need to make observation that function of different characters in suffix of any string is increasing with length of suffix increasing (in other words, it's monotonic).

Then, let dp[i] be the optimal answer for i-th prefix of string, dp[0] = 0. Let's imagine we're standing at the end of i-th prefix of string. Now, we need to find such positions l and r that l is the leftest position at which substring [l; i] has exactly k different characters and r is the rightest position at which substring [r; i] has exactly k different characters. Now, dp[i] = min(dp[l-1]..dp[r-1]), because all substrings from [l; i] to [r; i] are good (due to function mentioned earlier being monotonic), and we can concatenate any of them with shorter prefix. You can get min(dp[l-1]..dp[r-1]) with segment tree. Now we only need to find such l and r. You can do it using two pointers or binary search with some data structure that can answer queries like "how many different characters there are on segment [l..r]". For example, it can be sparse table with bitmasks of length 26 to get O(1) time for query.

Total complexity is O(N log N).

Sorry for bad English :)

Sort tasks by deadline. Not by "deadline — time" or any other shit.

Then process them in this order. If a task requires some dependencies, do them. If you can't do some task in time, output "NO".