Description

To maintain the flourish of the NTHU great lawn, there are some automatic sprinklers installed on the lawn.

Specifically, there are \(N\) automatic sprinklers, the \(ith\) one is installed at the position \((x[i], y[i])\) with the range \(r[i]\) -- meaning that it can water the grass inside the circle of radius \(r[i]\) centered at \((x[i], y[i])\)

For it may hurt the grass if it has been watered too much, the Director of General Affairs, \(DYY\), wants to know if some sprinklers' ranges are intersecting with any other sprinkler. So \(\forall i \in [1, N]\), you should print \(1\) if the \(ith\) sprinkler is intersecting with some other sprinkler, or print \(0\) otherwise.

Since programming is so trivial for \(DYY\) that it is such an abasement to do it himself, \(DYY\) asks you to do it for him.

And he will plus \(0.2\) points to your final score in return.

Hint 1: sprinklers \( i, j \) are intersecting if and only if \( (x[i]-x[j])^2+(y[i]-y[j])^2 < (r[i]+r[j])^2 \)

Hint 2: You may want to use the "sqrt()" function in math.h library, though I personally not recommend to use it in this problem for its precision problem.

Hint 3: All the discrete system is trivial, only calculus is the real technique, said \(DYY\).

Hint 4: There's no further hint.

Input

The first line of input contains an integer N, which is guaranteed to be less than or equal to 3000.

The following N lines, each contains 3 integers x[i], y[i], r[i].

It is guaranteed that 1 <= x[i], y[i], r[i] <= 10⁹ 

Output

For each sprinkler, you should print that whether it is intersecting with some other sprinkler or not.

Print your answer in one line, separated with single space character.

Please remember to print '\n' at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After finishing Gregory's task, you feel like a genius and have a strong desire to solve more challenging problems. The next thing you want to do is a bit similar to the previous task: given a 2-dimensional array A, with size n * n, you want to

1. find the subarray of A, with size m * m, that has the largest "first element" (i.e., the uppermost and the leftmost element) than any other m * m subarray;
2. rotate this subarray in a certain degree b counterclockwise.

The following shows some 3 * 3 subarray examples for a given 5 * 5 array. 

 

 

Since in this case, the 3 * 3 subarray at the lower right corner has the maximum first element, you should rotate it.

The subarray would be rotated counterclockwise and will only be rotated by a degree that is a multiple of 90:

Note:

1. If there is more than one subarray with the maximum value, rotate the uppermost one.
2. If there is still more than one subarray that satisfies the condition, rotate the leftmost one.

Input

The first line contains an integer n, which means the size of A is n * n.
Each of the following n lines contains n positive integers, representing A.
The last line contains two integers m and b, which means the subarray size and the angle you want to rotate, respectively.

It is guaranteed that all numbers in A are less than 10³.

Constraints:
3 ≤ n ≤ 100
1 ≤ m ≤ n
0 ≤ b ≤ 10⁴
b ≡ 0 (mod 90)

Output

Output contains n lines, each having n integers that represent the rotated array.

Sample Input  Download

Sample Output  Download

Tags

Discuss