Dividing the Kingdom: Canal Construction

Consider a feudal lord who rules over n independent city‐states, each represented as a circle in the plane. The i-th circle has center \((x_i, y_i)\) and radius \(r_i\). No two circles intersect or touch. One of these city‐states, with index s, is the national capital.

The lord wishes to construct a straight canal (represented by a line in the plane) that does not intersect or even touch any of the circles. The canal divides the territory into two open half‐planes. The half‐plane that contains the capital \(s\) is given to the elder son, and the other half to the younger son. In order for the younger son to be able to select his own capital later, each half‐plane must contain at least one circle.

Two canal‐construction methods are considered essentially the same if they yield the same partition of the city‐states (that is, if the same set of circles lies on the side of the canal that does not contain \(s\)). The younger son now wonders, for each city‐state, in how many essentially different ways of constructing the canal can he have that city become his capital (i.e. be in the half–plane that does not contain \(s\))?

More formally, let a valid division be a partition of the set of \(n\) circles into two nonempty parts \(A\) and \(B\) such that there exists a line \(L\) in the plane satisfying:

• For every city \(i\) in \(A\), \(\mathbf{n} \cdot (x_i, y_i) - d > r_i\).
• For every city \(j\) in \(B\), \(d - \mathbf{n} \cdot (x_j, y_j) > r_j\).

The line is allowed to be perturbed slightly so that it does not touch any circle. We always assign the part containing the designated capital \(s\) to the elder son. For every city \(u\), if there exists a valid division in which \(u\) lies in the part not containing \(s\), then the younger son may choose \(u\) as his capital. Count the number of essentially different valid divisions (i.e. distinct partitions) that allow each city to be chosen as the capital for the younger son. (Note that since \(s\) is always in the elder son’s part, the answer for \(s\) is always 0.)

The formula for a valid division can be summarized as: there exists a unit vector \(\mathbf{n} = (\cos\theta,\sin\theta)\) and a scalar \(d\) such that \[ \min_{i\in A}\{\mathbf{n}\cdot(x_i,y_i)-r_i\} > \max_{j\in B}\{\mathbf{n}\cdot(x_j,y_j)+r_j\}. \]

inputFormat

The input begins with a line containing two integers \(n\) and \(s\) (1-indexed), where \(n\) is the number of cities and \(s\) is the index of the capital.

Then follow \(n\) lines, each containing three real numbers: \(x_i\), \(y_i\), and \(r_i\), representing the center and radius of the \(i\)th city’s circle.

outputFormat

Output a single line containing \(n\) integers. The \(i\)th integer is the number of essentially different canal‐construction methods by which city \(i\) can become the capital of the younger son. (Remember that the designated capital \(s\) will always have 0 as its answer.)

sample

3 1
0 0 0.1
10 0 0.1
-10 0 0.1

0 1 1