Desktop
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, with the fewest possible keystrokes. You can navigate using the letter keys a-z or the arrow keys "↑", "↓", "←", and "→".
When using letter keys, the transition follows these rules:
If there are shortcuts on the desktop 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). For instance, with shortcuts a, ab, b, pressing a will toggle between a and ab.
If the current 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 transition occurs.
When using an arrow key, the selection moves to the nearest shortcut in the direction of the arrow, within a right-angle sector originating from the selected shortcut. The bisector of this angle aligns with the arrow direction. If a shortcut lies on the boundary of the sector, it is considered part of the upper or lower sector (not the left or right). If no shortcuts exist in the sector, no movement occurs. If multiple shortcuts are equidistant, the one with the smallest x coordinate is chosen, and if still tied, the one with the smallest y coordinate is selected.
For example, if the shortcut a is selected (refer to the figure), the following transitions occur with arrow key presses:
Arrow "←": The selection moves to shortcut b, the closest in this sector. Another "←" press selects shortcut c.
Arrow "↑": Shortcuts d and e are in this sector. The selection moves to d, which is nearer.
Arrow "→": 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, as no other shortcuts are in the lower sector.
Write a program named DESKTOP that, given the shortcut names and their positions, calculates the minimum number of keystrokes needed to move from shortcut S to shortcut F.
Input Data
The first line of the input file contains three integers: N (1 ≤ N ≤ 1000) – the number of shortcuts on the desktop, S (1 ≤ S ≤ N) – the index of the currently selected shortcut, and F (1 ≤ F ≤ 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 ≤ x, y ≤ 10^6), and the text is a string of 1 to 50 lowercase Latin letters a-z.
No two shortcuts have the same coordinates or the same names. The coordinate grid is standard, meaning "↑" increases the y coordinate, and "→" increases the x coordinate.
Output Data
The output file should contain a single integer – the minimum number of keystrokes required to move from shortcut S to shortcut F.