В организации Cybernetics Failures (CF) создали прототип робота-сапёра. Для обнаружения возможных проблем в его функционировании было принято решение провести серию испытаний. В начале каждого испытания прототип робота будет помещён в клетку (x₀, y₀) прямоугольного клетчатого поля размера x × y, после чего в одну из клеток поля будет установлена мина. Предполагается провести ровно x·y испытаний, каждый раз устанавливая мину в ранее не использованную клетку. Стартовая же клетка робота никогда не меняется.

После размещения объектов на поле робот должен будет выполнить последовательность команд, заданную строкой s, состоящей только из символов 'L', 'R', 'U', 'D'. Эти команды предписывают роботу переместиться влево, вправо, вверх или вниз на одну клетку или остаться на месте, если перемещение в данном направлении невозможно. Как только робот выполнит всю последовательность команд, он взорвется из-за бага в коде. Если же в какой-то момент времени робот находится в одной клетке с миной, он также взорвётся, но уже не из-за бага в коде.

Движение влево уменьшает координату y, а движение вправо её увеличивает. Аналогично, движение вверх уменьшает координату x, а движение вниз её увеличивает.

Испытания могут затянуться очень надолго, поэтому вам предстоит предсказать их результаты. Для каждого k от 0 до length(s) вам требуется найти, в скольких испытаниях робот выполнит ровно k команд, прежде чем взорвётся.