Максим і принцеса

Обмеження: 2 сек., 256 МіБ

Сьогодні Максим вирішив урятувати принцесу, яка живе в далекому краї в чарівній вежі.

Зараз Максим стоїть у точці \((x_1, y_1)\), а його принцеса сидить у точці \((x_2, y_2)\). За один день наш герой може переміститися з \((x, y)\) в \((x + 1, y)\), \((x - 1, y)\), \((x, y + 1)\), \((x, y - 1)\) або залишитися на місці.

З таємничих джерел він дізнався, що вежу, у якій живе принцеса, охороняє злий дракон. Кожного дня дракон зсуває Максима з \((x, y)\) в \((x + 1, y)\), \((x - 1, y)\), \((x, y + 1)\), \((x, y - 1)\) залежно від літери (R, L, U, D).

Допоможіть Максимові дізнатись, за скільки днів він зможе добратись до принцеси, або скажіть, що це неможливо.

Вхідні дані

Перший рядок містить два цілих числа \(x_1\), \(y_1\) — координати Максима.

Другий рядок містить два цілих числа \(x_2\), \(y_2\) — координати принцеси.

Третій рядок містить ціле число \(n\) — довжину рядка \(s\).

У четвертому рядку записано \(s\), який складається лише з букв U, D, L і R. \(s_i\) — напрямок, куди здуває дракон Максима в \(i\)-ий день. Дракон виконує свої дії циклічно, тобто після \(s_n\) буде виконувати \(s_1\).

Вихідні дані

Виведіть мінімальну кількість днів, щоб дійти до принцеси, або -1, якщо це зробити неможливо.

Обмеження

\(0 \le x_1, y_1, x_2, y_2 \le 10^9\),

\(1 \le n \le 10^5\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
0 3 0 0 3 UDD	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
0 0 0 1 1 L	-1

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
0 0 1 0 2 LR	2

Примітки

Зауважте, що спочатку дракон зсуває Максима, а вже після того Максим може рухатися.