| Codeforces Round 178 (Div. 2) |
|---|
| Закончено |
Шаассу кажется, что на кухне скучно, когда там вся плитка на полу белая. Пол на его кухне вымощен n·m квадратными плитками в форме прямоугольника размера n × m. И вот юноша решил покрасить некоторые плитки черным, так чтобы получилась «шахматная раскраска». То есть, никакие две соседние плитки не должны быть одного цвета.
Для покраски Шаасс хочет задействовать робота-маляра. Вначале робот стоит на плитке (xs, ys) на границе кухни и направлен диагонально (то есть, смотрит влево-вверх, влево-вниз, вправо-вверх или вправо-вниз). Гуляя по кухне, робот закрашивает любую плитку, на которую он ступает, даже если эта плитка уже была закрашена. На покраску плитки требуется одна единица черной краски. Если в любой момент робот натолкнется на кухонную стену, он оттолкнется от нее по законам отражения. Обратите внимание, плитка закрашивается в тот момент, когда робот наступает на нее, шагая из другой плитки, то есть при изменении направления на одной и той же плитке закрашивания этой плитки не происходит. Плитка, на которой стоит робот в самом начале тоже закрашивается.
Робот прекращает покраску, как только пол становится стилизован под шахматную доску. Вам даны размеры кухни и позиция робота. Посчитайте, сколько краски потребит робот, пока не закрасит пол.
Рассмотрим изображенный ниже пример.
Если робот начинает движение с плитки номер 1 (плитки с координатами (1, 1)) таблицы слева, направляясь вниз-вправо, то он пройдет по плиткам 1354236 и потратит на этом пути 7 единиц черной краски, пока не остановится на плитке номер 6. Но если он начнет с плитки номер 1, как в таблице справа, направляясь вниз-вправо, то он застрянет в цикле плиток 1, 2, и 3.
В первой строке содержатся два целых числа n и m, (2 ≤ n, m ≤ 105). Во второй строке содержатся два целых числа xs и ys (1 ≤ xs ≤ n, 1 ≤ ys ≤ m) и исходное направление робота. Направление представлено одной из следующих строк: «UL» (направление вверх-влево), «UR» (вверх-вправо), «DL» (вниз-влево) or «DR» (вниз-вправо).
Заметьте, что запись (xs, ys) означает, что плитка находится в xs-ом ряду сверху и в ys-ом столбце слева на кухне.
Гарантируется, что изначально робот стоит на границе кухни (то есть в клетке, у которой менее четырех соседей по стороне).
Выведите количество краски, которое затратит робот на окраску кухонного пола на манер шахматной доски. Или, если эта цель не будет достигнута, выведите -1.
Пожалуйста, не используйте спецификатор %lld для чтения и записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
3 4
1 1 DR
7
3 4
3 3 DR
11
3 3
1 1 DR
-1
3 3
1 2 DL
4
