Force Fields

In the future, all cities will be protected by force fields.

We say there is a safe passage between two cities if the force fields of the two cities intersect in at least one point.

A group of cities is called a safe component if any two cities from the group are connected directly or indirectly by safe passages. A single city is always a safe component if the radius of the force field is not 0.

Given the number n of the cities and their (x, y) coordinates, and assuming each city has a force field of the same radius, answer the following questions:

• Q1: Given the radius of the force fields, how many safe components exist?
• Q2: Given the radius of the force fields and two cities, is there a safe passage between the two cities?

Input Specification

The first line of the input contains an integer n, the number of cities (1 ≤ n ≤ 1000).

Each of the next n lines contains two integers x_i and y_i, the coordinates of ith city (0 ≤ x_i, y_i ≤ 2000, 0 ≤ i ≤ n – 1).

The next line contains an integer m, the number of questions (1 ≤ m ≤ 400 000).

Each of the next m lines starts with an integer t, the type of question.

• If t = 0, there is only a real number r after t, the radius of the force fields.
• If t = 1, t is followed by a real number r (the radius of the force fields) and two integers i and j, the indexes of two cities (0 ≤ i, j ≤ n – 1).

Output Specification

For each of the m questions, output a line containing the answer to the question. For t = 0, answer Q1, and for t = 1, answer Q2. For Q2, if there is a safe passage between the two cities, output 1, otherwise 0.

Sample Input

1. 4
2. 3 3
3. 2 2
4. 3 2
5. 4 2
6. 4
7. 0 0.5
8. 1 10 3 1
9. 1 5.1 2 0
10. 1 0.49 2 3

download as text file

Output for Sample Input

1. 1
2. 1
3. 1
4. 0

download as text file