E. Pinball
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pinball is an arcade game. The player gets the points by manipulating the metal ball in the field by flippers. The main goal of the game is to get the maximum possible number of points.

The field usually contains many different objects, but in the problem the field has use only one kind of objects: bumpers.

Geometrically the bumper is the disk of the certain size. If the ball hits the bumper, the player earns some points. Then the ball may change its direction and moves till it hits another bumper.

The ball can move only to a bumper that is visible from the previous one i.e. it is possible to draw the straight line between centers of the bumpers that doesn't intersect and doesn't touch other bumpers. Also the ball can not return to the bumper that it hit before going to the current one. In other words if ball hit bumper $$$a$$$ then bumper $$$b$$$ then it can not go back to $$$a$$$.

Let the center of the first bumper has the coordinates ($$$x_1$$$, $$$y_1$$$) and its radius is equal to $$$r_1$$$, the center and radius of the second bumper are $$$x_2$$$, $$$y_2$$$ and $$$r_2$$$ correspondingly. Then the travel time between the bumpers is equal to $$$\mathcal{d}\frac{\sqrt{(x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2} - r_1 - r_2}{20}\mathcal{e}$$$seconds (rounded up to nearest integer).

The game starts at $$$t = 0$$$ where the ball hit the top bumper (the center of bumper has the maximum $$$y$$$ coordinate; if there are several such bumpers we take the bumper with maximum $$$y$$$ coordinate and maximum x coordinate), the player earns points for hitting the bumper and the direction of the ball hasn't been determined yet.

Write a program that will process two types of queries for the given field.

Input

The first line of the input file contains the integer number $$$n$$$ ($$$3 \leq n \leq 7$$$) denotes the number of bumpers. Each of the following $$$n$$$ lines contain $$$4$$$ integers $$$x_i$$$, $$$y_i$$$, $$$r_i$$$ and $$$s_i$$$ ($$$0 \leq x_i, y_i \leq 50$$$, $$$1 \leq r_i \leq 5$$$, $$$-100 \leq s_i \leq 100$$$) defining coordinates of $$$i$$$-th bumper, its radius and number of points that player gets when the ball hit that bumper. Bumpers don't intersect and don't touch each other.

The next line contains one number $$$q$$$ ($$$1 \leq q \leq 10\,000$$$) equals to the number of queries. The next $$$q$$$ lines contain the integer number defining type of the query and another integer $$$t_j$$$ ($$$0 \leq t_j \leq 10^9$$$) for the query of the first type and two integers $$$t_j$$$, $$$x_j$$$ ($$$0 \leq t_j \leq 10^9$$$, $$$1 \leq x_j \leq n$$$) for the query of the second type.

Output

For each query of the first type output one integer equals to the maximum possible number of game points that can be achieved among all moments of the first $$$t_j$$$ seconds. Formally, let $$$p(x)$$$ be the number of points at the moment $$$x$$$. Find $$$y$$$ where $$$p(y)$$$ is maximal and $$$y \in [0, t_j]$$$.

For each query of the second type output one integer equals to the maximum number of game points at $$$t_j$$$ second after the start of the game when the ball previously hit the bumper $$$x_j$$$. If the situation is impossible, output just one symbol "#".

All answers to the queries must be placed in different lines.

Example
Input
3
0 0 1 1
50 0 1 1
0 50 1 1
20
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 1 1
2 2 1
2 3 1
2 4 1
2 5 1
2 6 1
2 7 1
2 8 1
2 9 1
2 10 1
Output
1
1
2
2
2
3
3
3
3
4
#
#
2
2
2
#
3
3
3
#