Desktop#4681

Desktop

1 second

64 megabytes

Hard

On the desktop of the operating system, there are $N$ shortcuts, each defined by integer coordinates $x$ and $y$ , along with a name. The name of each shortcut consists of lowercase Latin letters ( $a$ – $z$ ). Your task is to move from the currently selected shortcut $S$ to the target shortcut $F$ using the keyboard, making as few keystrokes as possible. Movement is performed using the letter keys $a$ – $z$ or the arrow keys " $↑$ ", " $↓$ ", " $\leftarrow$ ", and " $\to$ ".

When using letter keys, the selection changes according to the following rules:

If there are shortcuts whose names start with the pressed letter and one of them is currently selected, the selection moves to the next shortcut (in lexicographical order among those starting with that letter; after the last one, it cycles back to the first which starts with this letter). For instance, if there are shortcuts $a$ , $ab$ , $b$ , pressing $a$ will toggle the selection between $a$ and $ab$ only.
If the currently selected shortcut's name does not start with the pressed letter, the selection jumps to the lexicographically smallest shortcut starting with that letter.
If no shortcuts start with the pressed letter, no change occurs.

When using an arrow key, the selection moves to the nearest shortcut (using Euclidean distance) in the direction of the arrow, within a right-angle sector originating from the current shortcut. The bisector of this angle is aligned with the arrow's direction. If a shortcut lies on the boundary of the sector, it is considered part of the upper/lower sector (not left or right). If no shortcuts are present in the sector, the selection remains unchanged. If multiple shortcuts are at the same minimum distance, the shortcut with the smallest $x$ coordinate is chosen; if there is still a tie, the one with the smallest $y$ coordinate is selected.

For example, if shortcut $a$ is currently selected (see the figure), the following transitions occur when pressing arrow keys:

Arrow " $\leftarrow$ ": The selection moves to shortcut $b$ , the closest in this sector. Another " $\leftarrow$ " press selects shortcut $c$ .
Arrow " $↑$ ": Shortcuts $d$ and $e$ are in this sector. The selection moves to $d$ as it is closer.
Arrow " $\to$ ": Only shortcut $g$ is in this sector, so the selection moves there.
Arrow " $↓$ ": Shortcuts $f$ and $h$ are equidistant from $a$ . The selection moves to $h$ , as it has a smaller $x$ coordinate. Another " $↓$ " press keeps the selection on $h$ since there are no other shortcuts in the lower sector.

Write a program named DESKTOP that, given the shortcut names and their positions, computes the minimum number of keystrokes required to move from shortcut $S$ to shortcut $F$ .

Input

The first line of the input file contains three integers: $N$ ( $1 \leq N \leq 1000$ 1 \le N \le 1000) — the number of shortcuts, $S$ ( $1 \leq S \leq N$ 1 \le S \le N) — the index of the currently selected shortcut, and $F$ ( $1 \leq F \leq N$ 1 \le F \le N) — the index of the target shortcut. Each of the next $N$ lines describes a shortcut in the format " $x y text$ ", where $x$ , $y$ are integers ( $0 \leq x, y \leq 1 0^{6}$ 0 \le x, y \le 10^6), and $text$ is a string consisting of $1$ to $50$ lowercase Latin letters ( $a$ – $z$ ).

No two shortcuts have the same coordinates or the same name. The coordinate grid is standard, i.e., " $↑$ " increases the $y$ coordinate, and " $\to$ " increases the $x$ coordinate.

Output

The output should contain a single integer — the minimum number of keystrokes required to move from shortcut $S$ to shortcut $F$ .

Examples

Example 1