Как и большинство пятиклассников, Петя очень любит компьютерные игры, больше всего ему нравится игра “Питон”. Суть этой игры состоит в следующем. На клетчатом поле размером \(N \times N\), находятся \(M\) кроликов. Каждый кролик имеет свою калорийность. Играющий управляет питоном, который изначально имеет длину \(2\). Каждую секунду голова питона перемещается на одну позицию вверх, влево, вправо или вниз, в соответствии с клавишей, которую в данный момент нажимает играющий, а хвост питона перемещается на клетку, где находилась часть питона, предшествующая хвосту. Когда питон съедает кролика с калорийностью \(K\), голова у него продолжает двигаться, а хвост в течении \(K\) секунд остается на месте. При этом происходит увеличение длины питона на \(K\). Как только питон пересекает сам себя, игра заканчивается. Если питон съедает кролика, когда процесс переваривания предыдущего кролика еще не закончен, то очередной кролик остается в пищеводе и ждет своей очереди на переваривание. Длина питона, в конечном итоге, должна увеличится на величину равную сумме калорийностей всех съеденных кроликов (если, разумеется, до этого игра не завершится).

После некоторой практики Петя решил, что его техника игры совершенна, и что надо оставить записи потомкам о своих играх. Для этого он записывал, на какие клавиши он нажимал и сколько времени (в секундах) он держал клавишу нажатой (а Петя, как истинный игроман, каждую секунду держал нажатой какую-либо клавишу). К сожалению, в той версии “Питона”, в которую играл Петя, содержалась ошибка, а именно в некоторых случаях питон мог пересекать сам себя без всяких последствий. Ваша задача состоит в том, чтобы написать программу, которая по известному начальному положению питона, расположению кроликов на площадке и последовательности нажатий на клавиши определит первый момент времени, когда питон пересечет сам себя. Известно, что других ошибок “Питон” не содержит. В частности, питон не может последовательно двигаться в противоположных направлениях.