Moving Between Circles 2

On the coordinate plane there are $N$ circles whose centers lie on the x-axis. Any two of the $N$ circles have no intersection point, whether internal or external tangency. One circle may be contained inside another.

You want to move from the interior of one circle to the interior of another. Each circle interior may be visited only once, and you may not visit it twice or more.

For convenience, treat the coordinate plane itself as one circle with center (0, 0) and infinite radius.

When only two circles A and B exist on the coordinate plane, the correct ways to move from the interior of A to the interior of B are as follows.

1. A and B are not nested in each other and do not meet

The first case moves from the interior of A $\rightarrow$ the coordinate plane $\rightarrow$ the interior of B. No correct path other than this exists.

2. B is inside A

The second case moves from the interior of A $\rightarrow$ the interior of B. No correct path other than this exists.

3. A is inside B

The third case also moves from the interior of A $\rightarrow$ the interior of B. No correct path other than this exists.

The cases below are incorrect moves from the interior of A to B.

4. Circles A, B, C exist on the coordinate plane, are not nested in each other, and do not meet

This path goes from the interior of A $\rightarrow$ the coordinate plane $\rightarrow$ the interior of C $\rightarrow$ the coordinate plane $\rightarrow$ the interior of B. The coordinate plane is visited twice, so this is not a correct move.

4. Circles A, B exist on the coordinate plane and B is inside A

This path goes from the interior of A $\rightarrow$ the coordinate plane $\rightarrow$ the interior of A $\rightarrow$ the interior of B. The interior of A is visited twice, so this is not a correct move.

Given $N$ circles on the coordinate plane, find the number of circles visited when moving from the interior of circle A to the interior of circle B.

The first line gives the number of circles $N$.

From the second line to the $N + 1$-th line, the circle number $k$, the $x$-coordinate of the circle center, and the circle radius $r$ are given, separated by spaces.

The last line gives the numbers of the two circles $A$ and $B$, separated by a space.

The given circle numbers are all distinct.

The coordinate plane is assumed to have number 0.

On the first line, print the number of circles visited.

On the second line, print the numbers of the visited circles in order, separated by spaces.

• $2 \le N \le 200,000$
• $-1,000,000 \le x \le 1,000,000$
• $1 \le r \le 10,000$
• $1 \le A, B \le N$, $A \ne B$
• $1 \le k \le N$
• $x, r$ are integers

Relative position of two circles

Use the following to determine the relative position of two circles.

Let the radius of circle A be $r_A$, the radius of circle B be $r_B$, and the distance between the centers of A and B be $d$.

Distance between two points

The distance $d$ between $(x_1, y_1)$ and $(x_2, y_2)$ is computed as follows.

$d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$