Magic Portals

There is a kingdom with $n$ cities connected by magic portals. Every pair of distinct cities is joined by exactly one magic portal, which lets a traveler move instantly from one city to the other.

Because of how the magic works, each portal can be used in only one direction. For every pair of cities A and B, it is known whether the portal allows a direct move from A to B or from B to A.

Because of these rules, moving residents from one city to another sometimes requires several portals. Some pairs of cities may also have no route between them using only portals.

Residents call a city perfect if they can reach every other city in the kingdom using only portals. Let the initial number of perfect cities be $k$.

The king has decided to pick a pair of cities and reverse the allowed direction of the portal connecting them. To choose the best option, the king wants to know how many perfect cities the kingdom can have after reconfiguring exactly one portal.

The king can request either a partial report or a full report. The contents depend on parameter $L$: for a partial report $L = k + 1$, and for a full report $L = 1$.

The report contains, for each integer $m \ge L$, the number of pairs of cities A and B that satisfy both conditions:

• Originally, the portal allows a direct move from A to B.
• If the portal is reversed so that it allows a direct move from B to A, the number of perfect cities becomes $m$.

A partial report therefore covers only the single-portal changes that strictly increase the number of perfect cities. A full report covers all single-portal changes.

Write a program that takes the allowed directions and the report type, builds the report, and prints it in the format below.

The first line contains two integers: $n$ ($2 \le n \le 2000$), the number of cities, and $p$, which is 0 for a partial report or 1 for a full report.

Each of the next $n$ lines contains $n$ characters. The $j$-th character of line $i$ is + if the portal allows a direct move from city $i$ to city $j$, – if it allows a direct move from city $j$ to city $i$, and . if $i = j$.

The first line contains $k$, the number of perfect cities.

If $p = 0$, the second line contains $n - k$ nonnegative integers separated by spaces. The $i$-th number is the number of city pairs whose reversal makes the number of perfect cities equal to $k + i$. If $k = n$, the second line may be omitted or empty.

If $p = 1$, the second line contains $n$ nonnegative integers separated by spaces. The $i$-th number is the number of city pairs whose reversal makes the number of perfect cities equal to $i$.

In the samples, only city 2 is perfect at first. Reversing the portals between the pairs (2, 3), (2, 4), or (2, 5) makes every city perfect. Reversing any other portal makes exactly one more city perfect.