Line Segment Intersection Query Problem

You are given a series of operations in a 2D Cartesian coordinate system. There are two types of operations:

• Operation 1: Insert a line segment defined by its two endpoints. The first inserted segment is assigned the id \(1\), the second \(2\), and so on.
• Operation 2: Given a number \(k\), query all segments that intersect the vertical line \(x=k\). For each segment that intersects, the intersection point's y-coordinate is computed as follows:
  For a non-vertical segment with endpoints \((x_1, y_1)\) and \((x_2, y_2)\):
  \(y = y_1 + (y_2 - y_1) \times \frac{k - x_1}{x_2 - x_1}\).
  For a vertical segment (i.e. \(x_1 = x_2\)), if \(k=x_1\), consider the intersection y-coordinate as \(\max(y_1, y_2)\); otherwise, it does not intersect.
  The query should return the id of the segment with the maximum intersection y-coordinate. In case of a tie, choose the segment with the smaller id. If no segment intersects, output \(-1\).

inputFormat

The first line contains an integer \(Q\), the number of operations. Each of the next \(Q\) lines represents an operation.

• If the operation is of type 1, the line will be: 1 x1 y1 x2 y2.
• If the operation is of type 2, the line will be: 2 k.

outputFormat

For each operation of type 2, output the id of the segment that has the maximum intersection y-coordinate with the line \(x=k\) on a new line. If no segment intersects, output \(-1\).

sample

5
1 0 0 2 2
1 0 2 2 0
2 1
2 0
2 2

1
2
1