Imprecise Location

A reverse geocoding service maps coordinates to geographic regions. In this problem, you must implement such a service.

You are given $N$ geographic regions. Each region is an axis-aligned rectangle in the plane: its sides are parallel to the coordinate axes. It is described by two opposite corners $(X_1,Y_1)$ and $(X_2,Y_2)$, with $X_1 < X_2$ and $Y_1 < Y_2$. For any two regions, either one is strictly contained in the other or they are disjoint. Their boundaries do not touch or cross.

The service must answer $Q$ location queries. Each query is given by three integers $X$, $Y$ and $R$. The point $(X,Y)$ is the measured location, and $R$ describes the uncertainty of the measurement: the actual location can be any point inside or on the boundary of the axis-aligned query square with opposite corners $(X-R,Y-R)$ and $(X+R,Y+R)$. When $R=0$, the query square consists of the single point $(X,Y)$.

It is guaranteed that no corner of a query square lies on the boundary of any region. However, the boundary of a query square may intersect region boundaries.

For each query, determine the region of smallest area that is guaranteed to contain the actual location. In other words, find the region of smallest area that contains the entire query square, or report that no such region exists.

Input

The first line contains an integer $N$ ($1 \leq N \leq 2 \times 10^{5}$) indicating the number of geographic regions. Each region is identified by a distinct integer from $1$ to $N$.

The $i$-th of the next $N$ lines describes region $i$ with four integers $X_1$, $Y_1$, $X_2$ and $Y_2$ ($-10^{9} \leq X_1,Y_1,X_2,Y_2 \leq 10^{9}$, $X_1 < X_2$ and $Y_1 < Y_2$), where $(X_1,Y_1)$ and $(X_2,Y_2)$ are two opposite corners of the corresponding rectangle.

The next line contains an integer $Q$ ($1 \leq Q \leq 2 \times 10^{5}$) indicating the number of location queries.

Each of the next $Q$ lines describes a query with three integers $X$, $Y$ and $R$ ($-10^{9} \leq X,Y \leq 10^{9}$ and $0 \leq R \leq 10^{9}$), representing the query square with opposite corners $(X-R,Y-R)$ and $(X+R,Y+R)$. The corners of this square may lie outside the coordinate range given for $X$ and $Y$.

Output

For each query in the input, output a line with an integer identifying the region of smallest area that contains the entire query square. If no region contains the entire query square, output a line with the character “*” (asterisk) instead.

2
0 0 10 10
2 2 6 6
3
4 4 1
4 4 3
9 5 2

2
1
*

3
2 2 4 4
8 0 14 6
0 0 6 6
4
3 3 0
1 1 0
11 3 1
7 3 2

1
3
2
*

1
-1 -1 1 1
3
0 0 0
1 3 0
0 0 2

1
*
*