Експерименти з Горлумом#7475

Експерименти з Горлумом

1 секунда

64 мегабайти

Середня

Зовсім недавно Єржан винайшов лазер, здатний вимірювати відстань до віддалених об'єктів. Але, як і будь-який винахід, лазер потрібно протестувати, і бажано на живому рухомому об'єкті (не питайте, яка кінцева мета цього лазера). Оскільки використовувати мишей старомодно, Єржан вирушив у заборонений ліс на пошуки підходящої істоти.

Як Єржан у лісі спіймав Горлума - це вже зовсім інша історія! Головне, що піддослідний для лазера знайшовся. Істота ця зветься Горлум і, незважаючи на те, що після довгих тренувань Горлум може строго виконувати команди, будучи істотою роздолбайською, кількість команд обмежена п'ятьма, для зручності позначеними символами латинського алфавіту:

"L" Горлум робить крок вліво - перехід з точки $(x, y)$ в точку $(x - 1, y)$ (x - 1, y).
"R" Горлум робить крок вправо - перехід з точки $(x, y)$ в точку $(x + 1, y)$ (x + 1, y).
"F" Горлум робить крок вперед - перехід з точки $(x, y)$ в точку $(x, y + 1)$ (x, y + 1).
"B" Горлум робить крок назад - перехід з точки $(x, y)$ в точку $(x, y - 1)$ (x, y - 1).
"I" Горлум дістає зі своєї кишені золоте кільце із сяючими написами і нікуди не рухається.

Для експерименту Єржан поставив свій лазер у точці $(L a se r_{x}, L a se r_{y})$ (Laser_x, Laser_y) на площині в Евклідовому просторі. Також, Єржан навчив Горлума виконувати список команд $T$ , де $T$ - це рядок, що містить символи команд у порядку їх виконання. Горлум стартує в точці $(G or l u m_{x}, G or l u m_{y})$ (Gorlum_x, Gorlum_y).

Ваше завдання знайти мінімальну і максимальну відстані до Горлума, зафіксовані лазером. Ваша відповідь буде зарахована правильною, якщо абсолютна або відносна похибки двох чисел не перевищують $1 0^{- 9}$ 10^{-9}.

Вхідні дані

У перших двох рядках дано число $k$ ( $k \leq 1 0^{5}$ k \leq 10^5) і рядок $S$ ( $∣ S ∣ \leq 1 0^{4}$ |S| \leq 10^4), що складається з символів "LRFBI". Для отримання рядка-списку-команд $T$ , $k$ разів сконкатенуйте рядок $S$ (іншими словами $T = S^{k}$ T = S^k).

У останніх двох рядках дано дві пари чисел: координати розташування лазера $(L a se r_{x}, L a se r_{y})$ (Laser_x, Laser_y) і старту Горлума $(G or l u m_{x}, G or l u m_{y})$ (Gorlum_x, Gorlum_y). Усі координати - цілі числа, за модулем не перевищують $1 0^{4}$ 10^4.

Вихідні дані

Два дійсних числа - мінімальна і максимальна зафіксовані відстані. Абсолютна або відносна похибки чисел не повинні перевищувати $1 0^{- 9}$ 10^{-9}.

Приклади

Приклад 1