eolymp
bolt
Try our new interface for solving problems
Problems

Рабочий стол

Рабочий стол

Time limit 1 second
Memory limit 64 MiB

На рабочем столе операционной системы расположено N ярлыков, каждый из которых задан целыми координатами x и y, а также названием. Название ярлыка состоит из маленьких символов латинского алфавита (a-z). Необходимо перейти (т.е. переместить выделение) с выделенного ярлыка S к ярлыку F, с помощью клавиатуры, использовав наименьшее возможное количество нажатий. Переход осуществляется с помощью нажатий на клавиши с буквами a-z, либо на стрелки "↑","↓","←" и "→".

При нажатии на клавиши с буквами переход происходит по следующим правилам:

  1. Если на рабочем столе находятся ярлыки, название которых начинается на нажатую букву, и выделен один из них, то переход происходит на ярлык, с названием, следующим в лексикографическом порядке среди тех, которые начинаются на эту букву (после последнего выделение переходит на первый). Т.е. если есть ярлыки a, ab, b, то при нажатии a выделение будет переходить только между a и ab.

  2. Если название текущего ярлыка не начинается на выбранную букву, то выделение переходит на лексикографически наименьший ярлык, который начинается на нажатую букву.

  3. Если на рабочем столе нет ярлыков, название которых начинается на нажатую букву, переход не осуществляется.

При нажатии на стрелку переход происходит на ближайший в обычном геометрическом смысле ярлык, который лежит в секторе стрелки. Определим сектор стрелки как прямой угол с вершиной в выделенном ярлыке, биссектрисой которого есть луч, соответствующий стрелке. Если ярлык лежит на границе сектора, то он относится к верхнему или нижнему сектору (а не к правому или левому). Если в определенном секторе нет ни одного ярлыка, то переход не осуществляется. Если ближайших ярлыков несколько, то выбирается ярлык с наименьшей x координатой, а если и таких несколько, то выбирается с наименьшей y-координатой.

Например, если выделен ярлык a (см. рисунок), то при нажатии стрелок могут произойти такие переходы:

  1. Стрелка "←". Выделение переходит на ярлык b, т.к. он есть ближайшим в секторе этой стрелки. При последующем нажатии "←" будет выделен ярлык c.

  2. Стрелка "↑". В секторе стрелки находятся ярлыки d и e. Выделение перейдет на d, который ближе.

  3. Стрелка "→". В секторе "→" находится только ярлык g, на который и перейдет выделение.

  4. Стрелка "↓". В этом секторе находятся ярлыки f и h, которые равноудалены от ярлыка a. Выделение переходит на ярлык h, т.к. x-координата этого ярлыка меньше. Если после этого нажать "↓", то выделение остается на h, т.к. в секторе снизу нет ни одного ярлыка.

Напишите программу DESKTOP, которая по информации о названиях ярлыков и об их расположении определит наименьшее возможное количество нажатий клавиатуры, с помощью которых можно из выбранного ярлыка достичь целевого.

Input data

Первая строка входного файла содержит три целых числа: N (1N1000) – количество ярлыков на рабочем столе, S (1SN) – номер выбранного ярлыка, F (1FN) – номер ярлыка на который требуется перейти. Каждая из последующих N строк задает ярлык в формате "x y text", x, y – целые числа (0x, y10^6), а текст содержит не более чем 50, и не менее чем один маленький символ латинского алфавита a-z.

Никакие два ярлыка не имеют одинаковых координат и одинаковых названий. Координатная сетка – стандартная, т.е. "↑" увеличивается y-координата, а "→" x-координата.

Output data

Единственная строка выходного файла должна содержать одно целое число – минимальное количество нажатий на клавиатуру, которые позволят перейти от ярлыка S к ярлыку F.

Examples

Input example #1
8 1 4
5 4 a
2 3 b
3 2 h
0 3 c
4 6 d
7 6 e
7 2 f
9 6 g
Output example #1
1