Read and implement.

There are only two cases, so just draw them on draft paper.

The resistance of the n-th section is a multiplicative function of n, which only depends on distinct prime factors.

BFS is enough.

Be careful with leading whitespaces and too many test cases.

Picking half of points from every boundary is enough.

Let f(n) be the minimal integer t such that .

If the first died monster has p health points and the second one has q, the best strategy should lead the former one to die at f(p)-th second and lead the latter one to die at f(p + q)-th second.

The rest is just to enumerate which one should die firstly, and construct the lexicographical smallest strategy greedily.

Be careful when the received damages are equal in these two cases.

One observation is that coordinates of rooks in each type form a permutation.

If split the area into 9 grid regions, one can find rooks can only collide in at most 4 regions.

Coordinates are easy to maintain as well.

Suffix structures may help counting distinct contiguous subsequences (intervals).

Segment tree (or fenwick tree) with stack may help maintaining maximum values of intervals offline.

Let f(n) be the number of labelled forests having n vertices, g(n) be the number of pairs of reachable vertices in labelled forests having n vertices, and h(n) be the sum of lengths of the shortest path between every pair of reachable vertices in labelled forests having n vertices.

Calculating f(n) is typical: Enumerate the size of component containing label 1, and conclude . Speed it up by divide and conquer (or Newton iteration).

For g(n), one can conclude by enumerating contributions of each component.

For h(n), it can be reduced into counting the number of ways to pick k ordered edges on the shorest path between every ordered pair of vertices (k = 1, 2). Imagine these k edges split a component (tree) into (k + 1) components (trees), and one can conclude calculating the number of ways is equivalent to calulcate the (k + 1)-th power of the polynoimial .

There are two cases which depend on if carpets intersect, so we need to know the number of squares covered by exact k carpets (k = 1, 2).

It is easy to show the number of useful pairs of 2 carpets is at most m², so the difficulty of this problem is only counting the number of squares covered by exact k carpets.

Sweep line with segment tree can do this in , while maintaining some statistics obtained from 2-dimensional partial sum and solving equations for each square can do this in O(k(n + m²)).

One can easily determine if a substring forms a matching path starting from node 0 by binary search with hashing, so for each left endpoint, one can find the mismatched right endpoint quickly.

Then for each query, binary lifting could speed up the process of failed matching.

There are 5 types of connected subgraphs, one can count them using inclusion-exclusion principle, which leads to count the number of k-cycles in the graph (k = 3, 4).

One can solve the typical counting problem in .