Задача F. Трава у дома Месгрейвов ≡

Условие

 — В результате, дорогой Ватсон, у нас с Реджинальдом Месгрейвом осталась половина инструкции, в которой указано, сколько шагов нужно сделать до очередного поворота налево или направо. Вторую половину, где как раз указывалось направление поворота после очередных шагов, утащил пройдоха-дворецкий. Еще нам были известны размер участка в форме прямоугольника, за пределы которого нельзя было выходить — с одной стороны располагалась стена замка, с другой — пруд, с третьей — глубокий обрыв, с четвертой — отвесная скала, и от какого угла следует начинать наши поиски. Клад был зарыт где-то на этой зеленой лужайке, но хозяин наотрез отказывался планомерно перекопать её.

 — Что же его останавливало, дорогой Холмс? Неужели древняя корона английских королей не стоит какого-то газона?

 — Это был не просто газон, а настоящее произведение искусства! Месгрейвы несколько столетий возделывали его и в результате получился просто идеальный ландшафт. "Укажите мне место, где может быть зарыт клад, — сказал Реджинальд, — и я разрешу раскопки именно в этом месте. Но копать там, где клада точно быть не может, я не позволю!"

 — Инструкция очень длинная, значит и шагов, и поворотов нужно было сделать много. Тут могут быть сотни подходящих мест, как же Вы отсекли все лишние?

 — Нет ничего зазорного в том, чтобы обратиться к помощи профессионала. Я нанес визит сэру Чарльзу Бэббиджу, описал стоящую перед нами задачу и попросил определить координаты тех участков газона, где может быть спрятано сокровище. Ученый заинтересовался, настроил свою аналитическую машину и загрузил в неё стопку картонок. Я уже приготовился к томительному ожиданию, сопровождаемому обычными стенаниями Бэббиджа о том, как ему докучают уличные музыканты, как вдруг он с улыбкой поворачивается и протягивает мне готовые перфокарты. На верхней было выбито точное количество возможных мест, а на остальных — их координаты. Нам с Месгрейвом повезло, уже пятая по счету раскопка привела к успеху.

Заметка на полях дневника Джона Ватсона: "Боюсь, что рассказ Холмса выглядит несколько ... фантастически. Требуется проверка со стороны какого-нибудь молодого исследователя, возможно ли с помощью вычислительного устройства и половины инструкции быстро определить все места, где спрятано сокровище?"

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: m и n — размер участка, на котором зарыт клад. Вторая строка содержит натуральное число k — количество чисел в инструкции. В третьей строке через пробел расположены k натуральных чисел p_i — количество шагов до очередного поворота.

Формат выходных данных

В первой строке выведете одно неотрицательное целое число p — количество возможных мест участка, где может быть зарыт клад. В следующих p строках выведете через пробел два натуральных числа x_i и y_i — координаты очередного места. Координаты должны быть выведены в порядке не убывания x_i, если существует несколько мест с равными x_i, — в порядке не убывания y_i.

Ограничения

1 ≤ m, n ≤ 60

1 ≤ k, p_i ≤ 30

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере дан участок размером 10 на 6, место старта всегда в участке с координатами (1, 1). В инструкции три команды: пройти 5 шагов, повернуть налево или направо (часть инструкции с точными направлениями поворотов утрачена) пройти ещё 2 шага, повернуть налево или направо, пройти 4 шага и копать. С учетом того, что ни на каком шаге нельзя выходить за пределы участка, есть всего три подходящих места, где может быть зарыто сокровище.

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

10 6
3
5 2 4

3
2 3
3 2
10 3