Background

In the early Western Han Dynasty, Emperor Gaozu Liu Bang, in order to better control the land under the Liu family's rule, extensively enfeoffed Liu clan princes. However, as Liu Bang passed away, the princes became increasingly uncontrollable by the central government. To weaken the power of the vassal states, Emperor Wu Liu Che adopted the advice of his minister Zhu Fu Yan and implemented the Decree of Benevolence. This decree required the princes to distribute their land among all their descendants, rather than passing it solely to their eldest son. This way, large territories would be divided into smaller vassal states, thereby weakening the princes' power.

Problem Description

Consider a practical example: A prince has $n$ city-states in his domain, with city-state $s$ being the capital of his domain. We can describe his territory using a Cartesian coordinate system, where the $i$-th city-state is represented as a circle centered at $(x_i, y_i)$ with radius $r_i$. No two city-states overlap or touch each other.

The prince has two sons, and he wants to divide his land between them using a simple method: constructing a dividing canal. This canal can be represented by a straight line in the coordinate system, and it must not intersect or touch any city-state. The canal divides the land into two parts, with the part containing the capital $s$ going to the eldest son, and the other part to the younger son. To ensure the younger son can choose a city-state as his capital, both sides of the canal must contain at least one city-state.

There are many ways to construct the canal. To ensure fairness, the prince wishes to randomly select one from all essentially different ways. Two ways of constructing the canal are considered essentially the same if they divide the city-states into the same two parts.

The younger son has learned about the prince's division method. To choose his capital in advance, he wants to know the likelihood of each city-state becoming his capital. He assigns you the task of calculating, for each city-state, how many essentially different ways of constructing the canal would allow him to choose that city-state as his capital.

Input Format

The first line contains two integers $n$ and $s$, representing the number of city-states and the capital's index, respectively.

The next $n$ lines each contain three integers $x_i, y_i, r_i$, describing the center and radius of the $i$-th city-state.

Output Format

Output $n$ lines, each containing an integer $a_i$, where the $i$-th line indicates the number of essentially different canal construction methods that allow the younger son to choose the $i$-th city-state as his capital.

Sample Input and Output

Input Sample #1

4 1
0 0 0
0 1 0
1 0 0
1 1 0

Output Sample #1

0
3
3
4

Input Sample #2

3 1
0 0 1
0 3 1
0 6 1

Output Sample #2

0
1
2

Notes

[Sample 3]

See the attached files 3.in/ans in the problem package.

[Subtasks]

For $100\%$ of the data, it is guaranteed that $1 \leq s \leq n \leq 1000$, and $0 \leq |x_i|, |y_i|, r_i \leq 10^4$.

见题面 Input 部分

见题面 Output 部分