Робот-пылесос находится на полу прямоугольной комнаты, ограниченной стенами. Пол можно представить как таблицу из \(n\) строк и \(m\) столбцов. Строки пола пронумерованы от \(1\) до \(n\) сверху вниз, а столбцы пронумерованы от \(1\) до \(m\) слева направо. Клетка на пересечении \(r\)-й строки и \(c\)-го столбца обозначается \((r,c)\). Изначально робот находится в клетке \((r_b, c_b)\).
Каждую секунду робот двигается на \(dr\) строк и \(dc\) столбцов, то за секунду робот передвигается из клетки \((r, c)\) в \((r + dr, c + dc)\). Изначально \(dr = 1\), \(dc = 1\). Если в направлении движения робота находится вертикальная стена (левая или правая), \(dc\) отражается перед движением, новое значение \(dc\) становится \(-dc\). Также, если в направлении движения робота находится горизонтальная стена (верхняя или нижняя), \(dr\) отражается перед движением, новое значение \(dr\) становится \(-dr\).
В начале каждой секунды (в том числе перед первым движением робота) робот очищает все клетки, лежащие в той же строке или в том же столбце, что и робот. В комнате лишь одна грязная клетка \((r_d, c_d)\). Задача робота — очистить эту грязную клетку.
Иллюстрация к первому примеру. Робот обозначен голубой дугой. Красной звездой обозначена грязная клетка. Каждую секунду робот очищает строку и столбец, что показано желтыми линиями. По данному размеру пола \(n\) и \(m\), начальной позиции робота \((r_b, c_b)\) и позиции грязной клетки \((r_d, c_d)\) найдите, через какое время робот выполнит задачу.
Выходные данные
Для каждого набора входных данных выведите одно целое число — время, необходимое роботу для очистки грязной клетки. Можно показать, что робот всегда очистит грязную клетку за конечное время.
Примечание
В первом примере размер пола равен \(10\times 10\). Начальная позиция робота \((6, 1)\), грязная клетка — \((2, 8)\). Иллюстрация к этому примеру находится в условии задачи.
Во втором примере пол такой же, но начальная позиция робота \((9, 9)\), а грязная клетка — \((1, 1)\). В этом примере робот дойдет точно до грязной клетки и очистит ее.
В третьем примере пол имеет размеры \(9 \times 8\). Начальная позиция робота \((5, 6)\), грязная клетка \((2, 1)\).
В четвертом примере пол имеет размеры \(6 \times 9\). Начальная позиция робота \((2, 2)\), грязная клетка \((5, 8)\).
В последнем примере робот изначально в том же столбце, что и грязная клетка, поэтому он ее сразу очистит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
10 10 6 1 2 8
10 10 9 9 1 1
9 8 5 6 2 1
6 9 2 2 5 8
2 2 1 1 2 1
|
7
10
9
3
0
|