Needle Leaf Game

In the Needle Leaf Game, you are given n needle leaves, which are modeled as non‐intersecting line segments in the plane. The game is played in n rounds. In each round, a student chooses a particular needle leaf by its id and attempts to move it in either a horizontal or vertical direction. When moving a segment, it is continuously translated (without rotation) to infinity (i.e. the segment is removed).

The movement is legal if and only if during the entire translation, the moving segment does not collide with any other segment that has not yet been removed (touching at endpoints is allowed). Formally, when a segment S with endpoints \( (x_1,y_1) \) and \( (x_2,y_2) \) is moved horizontally (to the left) its position at time \(t\) is \(S(t)=\{(x-t,y):(x,y)\in S\}\). The move is legal if for every \(t>0\), the interior of \(S(t)\) does not intersect the interior of any other segment that remains. Similarly, for a vertical (downward) move, the moving segment becomes \(S(t)=\{(x,y-t):(x,y)\in S\}\>.

Your task is two‐fold:

1. Simulate the moves provided by Will and determine the earliest round (1-indexed) at which an illegal move occurs. If all rounds are legal, output 0.
2. Output a legal sequence of moves that removes all needle leaves. In this valid move plan, you may choose any legal order. One simple strategy is to always remove a segment having the minimum \(x\) coordinate (i.e. minimum \(x_{min}\)) by moving it horizontally (to the left). Because the segments do not intersect, such a move is always legal.

Input constraints: n is a positive integer. All coordinates are real numbers. It is guaranteed that the segments do not intersect initially.

inputFormat

The input begins with an integer \(n\) (the number of needle leaves). The next \(n\) lines each contain four numbers \(x_1\), \(y_1\), \(x_2\), \(y_2\) representing the endpoints of the \(i\)-th needle leaf. Then follow \(n\) lines, each containing an integer id (1-indexed) and a character (either H or V) representing the move direction that Will wants to make in that round. For the purpose of simulation, assume that H denotes a horizontal move (to the left) and V denotes a vertical move (downward).

outputFormat

The output consists of two parts:

1. A single integer indicating the earliest round number in which an illegal move occurs. If all moves are legal, output 0.
2. A legal move plan to remove all the segments. Output exactly \(n\) lines, each containing a segment id and a move direction (use H for horizontal moves). A valid strategy is to remove the segments in increasing order of their minimum \(x\)-coordinate.

sample

3
0 0 1 0
2 0 3 0
1 1 2 1
2 H
3 V
1 H

1
1 H
3 H
2 H