All Tracks Math Problem

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\)