Представьте таблицу размера n × m, где некоторые ячейки заблокированы. У ячейки в верхнем левом углу координаты — (1, 1), а у ячейки в правом нижнем углу — (n, m). Всего в таблице существуют k заблокированных ячеек, остальные ячейки — пустые. Вы пускаете луч лазера из центра пустой ячейки (xs, ys) в одном из диагональных направлений (то есть северо-восток, северо-запад, юго-запад или юго-восток). Если луч попадает в заблокированную ячейку или на границу таблицы, то он отражается. Поведение отражения луча в разных ситуациях показано на рисунке ниже.
Заметим, что через некоторое время луч попадает в бесконечный цикл. Посчитайте количество пустых ячеек, через которые луч проходит хотя бы однажды. Считается, что луч проходит через ячейку, если он проходит через ее центр.
Выходные данные
В единственной строке выходных данных выведите количество пустых ячеек, через которые луч проходит хотя бы раз.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 0
1 2 SW
|
6
|
|
2
|
7 5 3
3 3
4 3
5 3
2 1 SE
|
14
|