Left‐Hand Wall Following

In this problem, a girl named Falok, who is afraid of the dark, finds herself alone in a suddenly darkened academic building. Fortunately, the building’s floor layout is very regular. Formally, the floor plan is drawn on a 2D grid where the top‐left vertex is (0,0) and the bottom‐right vertex is (n,m). The four sides of the rectangle (0,0)–(n,m) are always walls. In addition, some internal walls (which are impassable) may exist. Each wall is a line segment between two adjacent grid vertices (that is, two vertices (i,j) and (i′,j′) with |i−i′|+|j−j′| = 1, with 0 ≤ i,i′ ≤ n and 0 ≤ j,j′ ≤ m).

Falok holds the wall with her left hand (keeping her arm perpendicular to the wall) and walks forward, always keeping her left hand in contact with a wall – even at corners. Her hope is that by following this method she might eventually meet LiSe. Initially, you are given the structure of the floor (including the four boundary walls and possibly some extra walls). Then there are q operations.

The operations are as follows:

• Operation 1: 1 x₀ y₀ x₁ y₁ — add a wall between (x₀,y₀) and (x₁,y₁). It is guaranteed that this wall did not exist before and that it is not one of the four fixed boundary walls.
• Operation 2: 2 x₀ y₀ x₁ y₁ — remove an existing wall between (x₀,y₀) and (x₁,y₁). It is guaranteed that the wall exists and is not a boundary wall.
• Operation 3: 3 x₀ y₀ x₁ y₁ d₀ x₂ y₂ x₃ y₃ d₁ — a query. Falok is at the midpoint of the wall between (x₀,y₀) and (x₁,y₁), and d₀ indicates which side she is on: if the wall is vertical, 0 means she is to the left and 1 means to the right; if horizontal, 0 means she is above and 1 means below. LiSe is at the midpoint of the wall between (x₂,y₂) and (x₃,y₃) with d₁ defined similarly. It is guaranteed that both walls exist and that both midpoints lie in the interior of the rectangle (0,0)–(n,m) (note that the coordinate system is such that (0,0) is the top‐left vertex and (n,m) is the bottom‐right vertex; (i,j) denotes the vertex in the (i+1)th row and (j+1)th column).

Falok will start running from her starting wall following the left‐hand rule. That is, she first chooses an initial direction along the wall so that the wall remains on her left. When she is at a vertex, she chooses her next direction using the following priority (relative to her current direction): turn left, go straight, turn right, or turn back – but she can only continue along a wall (an edge exists in that direction).

More precisely, note that a valid wall edge always connects two adjacent grid vertices and has length 1. When Falok traverses an entire wall edge, she walks a distance of 1; if she starts (or stops) at the midpoint of an edge, the part traveled on that edge is counted as 1/2. In a query, if Falok enters the wall on which LiSe is located, she will meet LiSe exactly when she reaches its midpoint. Output the total distance Falok travels until she meets LiSe.

The initial input specifies the building: the first line contains four integers n, m, w, and q, where n and m define the grid (with vertices from (0,0) to (n,m)), w is the number of extra (internal) walls provided initially, and q is the number of subsequent operations. Then there are w lines each describing an extra wall in the format x0 y0 x1 y1. After that there are q lines; each line is either an operation of type 1, type 2, or a query of type 3 as described above.

Input Format (Summary):

n m w q
// w lines of extra walls:
  x0 y0 x1 y1
// q operations, one per line:
  op [parameters]

Output Format:

For each operation of type 3 (query), output the total distance Falok travels until she meets LiSe. Output the distance as a decimal number. It is guaranteed that Falok will eventually meet LiSe.

Note: All formulas must be written in LaTeX. For example, the length of a wall segment is $1$, and half a segment has length $\frac{1}{2}$.

inputFormat

The first line contains four integers: \(n\), \(m\), \(w\) and \(q\) — representing the grid size, the number of extra walls initially, and the number of operations, respectively. The grid has vertices with coordinates from \((0, 0)\) to \((n, m)\). The four boundary walls corresponding to the rectangle \((0,0)-(n,m)\) always exist.

Then follow \(w\) lines, each containing four integers x0 y0 x1 y1 describing an extra wall (which connects two adjacent grid vertices).

After that, there are \(q\) lines, each representing an operation. The operations have one of the following formats:

• Operation 1: 1 x0 y0 x1 y1
• Operation 2: 2 x0 y0 x1 y1
• Operation 3 (Query): 3 x0 y0 x1 y1 d0 x2 y2 x3 y3 d1

For the query, the wall \((x_{0},y_{0}) - (x_{1},y_{1})\) is where Falok is initially located (at its midpoint) and \(d_{0}\) indicates her side (for a vertical wall: 0 means left, 1 means right; for a horizontal wall: 0 means above, 1 means below). Similarly, LiSe is located at the midpoint of the wall \((x_{2},y_{2}) - (x_{3},y_{3})\) with parameter \(d_{1}\) defined in the same way.

outputFormat

For each query (operation type 3), output one line containing a decimal number — the total distance Falok travels (in units) until she meets LiSe. When Falok only traverses half of a wall edge, that distance counts as \(\frac{1}{2}\) (i.e. 0.5).

sample

3 3 0 1
3 0 0 0 1 1 0 0 1 0

1.0

</p>