Робочий стол
На робочому столі операційної системи розміщено N ярликів, кожен з яких задано цілими координатами x та y, а також назвою. Назва ярлика складається з маленьких символів латинського алфавіту (a-z). Необхідно перейти (тобто перемістити виділення) з виділеного ярлика S до ярлика F, за допомогою клавіатури, використавши найменшу можливу кількість натиснень. Перехід здійснюється за допомогою натиснень на клавіші з буквами a-z, або на стрілки "↑","↓","←" и "→".
При натисненні на клавіші з буквами перехід відбуваєьбся за такими правилами:
Якщо на робочому столі знаходяться ярлики, назва яких починається на натиснену букву, і виділен один з них, то перехід відбувається на ярлык, з назвою, наступною у лексикографічному порядку серед тех, які починаються на цю букву (після останнього виділення переходить на перший). Тобто якщо є ярлики a, ab, b, то при натисненні a виділення буде переходить лише між a та ab.
Якщо назва поточного ярлика не починається на вибрану букву, то виділення переходить на лексикографічно найменший ярлик, який починається на натиснену букву.
Якщо на робочому столі немає ярликів, назва яких починається на натиснену букву, перехід не здійснюється.
При натисненні на стрілку перехід відбувається на найближчий у звичному геометричному змісті ярлик, який лежить у секторі стрілки. Визначимо сектор стрілки як прямий кут з вершиною у виділеному ярлиці, бісектрисою якого є промінь, що відповідає стрілці. Якщо ярлик лежить на границі сектора, то він відноситься до верхнього або нижнього сектору (а не до правого чи лівого). Якщо у визначеному секторі немає жодного ярлика, то перехід не здійснюється. Якщо найближчих ярликів декілька, то вибирається ярлик з найменшою x координатою, а якщо і таких декілька, то вибирається з найменшою y-координатою.
Наприклад, якщо виділено ярлык a (див. рисунок), то при натисненні стрілок можуть відбутись такі переходи:
Стрілка "←". Виділення переходить на ярлик b, так як він є найближчим у секторі цієї стрілки. При наступному натисненні "←" буде виділено ярлик c.
Стрілка "↑". У секторі стрілки знаходяться ярлики d та e. Виділення перейде на d, який ближче.
Стрілка "→". У секторі "→" знаходиться лише ярлик g, на який і перейде виділення.
Стрілка "↓". У цьому секторі знаходяться ярлики f та h, які рівновіддалені від ярлика a. Виділення переходить на ярлик h, так як x-координата цього ярлика менша. Якщо після цього натиснути "↓", то виділення залишиться на h, так як у секторі знизу немає жодного ярлика.
Напишіть програму DESKTOP, яка за інформацією про назви ярликі та про їх розміщення визначить найменшу можливу кількість натиснень клавіатури, за допомогою яких можна з вибраного ярлика досягти потрібного.
Вхіні дані
Перший рядок вхідного файлу містить три цілих числа: N (1 ≤ N ≤ 1000) – кількість ярликів на робочому столі, S (1 ≤ S ≤ N) – номер вибраного ярлика, F (1 ≤ F ≤ N) – номер ярлика на який потрібно перейти. Кожен з наступних N рядків задає ярлик у форматі "x y text", x, y – цілі числа (0 ≤ x, y ≤ 10^6), а текст містить не більше ніж 50, і не менше ніж один маленький символ латинського алфавіту a-z.
Ніякі два ярлики не мають однакових координат в однакових назв. Координатна сітка – стандартна, тобто "↑" збільшується y-координата, а "→" x-координата.
Вихіні дані
Єдиний рядок вихідного файлу повинен містити одне ціле число – мінімальну кількість натиснень на клавіатуру, які дозволять перейти від ярлика S до ярлика F.