Задача 3. Змейка первокурсника ≡

Условие

Первокурсник Варфоломей решил написать всем известную игру змейку в качестве домашней работы, усовершенствовав её на свой вкус.

По правилам Варфоломея змейка, поедая яблоки, не растет и за границы поля не выходит. Для передвижения змеи по клеткам он также придумал свои правила, по которым каждый ход задается символами: W  — наверх, A  — влево, S  — вниз, D  — вправо. Каждый раз, когда змейка съедает яблоко, выводятся координаты съеденного яблока. Также все яблоки сразу находятся на поле в заранее известных координатах.

Трудился студент день и ночь, написал генерацию красивой карты размером 40 на 40 клеток, аппетитных яблок и идеальной змеи, размером в 1 клетку. Но не успел Варфоломей закончить свою домашнюю работу  — коллоквиум по матанализу подошел слишком близко.

Помогите ему доделать игру, написав программу, которая по N шагам змеи определит координаты всех съеденных яблок на её пути.

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Решение будет полностью проверяться сразу после отправки, и участникам будут видны набранные за данную задачу баллы.

Формат входного файла

Первая строка входного файла содержит целые числа N, M  — количество яблок и шагов змеи соответственно. На второй строке N пар чисел  — координат яблок. На третьей строке M символов  — направления шагов змейки.

Формат выходного файла

Первая строка выходного файла должна содержать количество съеденных яблок  — K. Последующие K строк должны содержать в себе координаты яблок в порядке их поедания. Каждая пара координат, разделенная пробелами, должна быть на новой строке.

Примеры тестов

1 2
1 1
D S

1
1 1