Country A and B are in war. Assumption, the battle field is in 2D coordinate. Country B have built a defend system containing "rocket defense system" (RDS) and "wall". A RDS has radius $R$, that means if a rocket is at distance less than or equals $R$ from the RDS then it is detected and destroyed. A wall can be considered as a straight segment, a rocket will be resisted if hitting it (both ends inclusive). At position $(0, 0)$, country A shoots rockets along a straight line to a target. You are given $Q$ queries of several types:

$1\ x\ y$: Country A shoot a rocket to position $(tx, ty)$, you must answer whether it sucessfully reaches the target or find position where it is destroyed by a RDS or hits a wall.

$2\ x\ y$: Country B builds a RDS at position $(x, y)$.

$3\ x\ y\ z\ t$: Country B builds a wall between two positions $(x, y)$ and $(z, t)$.

$4\ u$: $u$-th RDS is destroyed by an army of country A.

$5\ v$: $v$-th wall is destroyed by an army of country A.

Input Format

The first line contains four space-separated integers $N, M, R, Q$ denoting the number of RDSs, the number of walls, the radius of RDS and the number of queries, respectively.

Each of the $N$ next lines contains two space-separated integers $x, y$ denoting position of a RDS.

Each of the $M$ next lines contains four space-separated intergers $x, y, z, t$ denoting position of a wall.

$Q$ lines follow, each line contains a query as described above.

RDSs and walls are numbered according to their appearance.

Output Format

For each query of the first type, assuming $d$ is euclidean distance the rocket goes before stopping (it is destroyed or resisted or reaches the target). Print the nearest integer to $1000 \times d$ ($.5$ is rounded up).

Constraints

• $1 \le N, M \le 5\times10^4$
• $1 \le R \le 10^6$
• $1 \le Q \le 10^5$
• $1 \le x, y, z, t, tx, ty \le 10^6$
• No RDS covers point $(0, 0)$
• $1 \le u \le$ the number of RDSs at that time (destroyed include)
• $1 \le v \le$ the number of walls at that time (destroyed include)
• Total numbers of RDSs and walls is at most $5\times 10^4$