sah

Ана и Йон имат общ интерес към шаха и винаги, когато имат време, играят на шах. Понеже са оригинални хора, те са си поръчали шахматни дъски с различни размери, както и със специални набори от фигури. Ако нямат време да завършат играта, те запазват положението на фигурите върху дъската и продължават на следващия ден. Веднъж те имали проблем - Лонел, техният син разбъркал фигурите - и сега те се опитват да възстановят конфигурацията. Йон си спомня точно как е изглеждала конфигурацията вчера в началото на играта и си спомня точно ходовете, които той е направил. Ана си спомня, че тя е играла малко странно - през цялата игра е премествала само една фигура - топа. Тя не си спомня точно позициите в които го е поставяла, но си спомня посоките, по които го е придвижвала.  

Задача

Напишете програма, която определя позициите в които може да бъде топът, който Ана е премествала.

Вход

Входният файл sah.in съдържа на първия си ред две положителни цели числа, разделени с интервал, X N, които задават размера на шахматната дъска и броя на фигурите върху нея.
Следващите N реда съдържат информация за положението на фигурите, а именно редът i+1 съдържа положението на фигура i във вид на две положителни цели числа, отделени с интервал L C
. Те задават реда и стълба на дъската, в които се намира фигурата.
Последната позиция е на топа, който движи Ана.
Следващият ред съдържа положително цяло число Nr, което задава броя на ходовете, направени от Йон и Ана.
Всеки от следващите Nr реда съдържа информация за ходовете, които е направил Йон, а именно ред N+2+j съдържа 3 положителни цели числа, отделени с по един интервал -  i L1 C1, които показват, че фигура i е преместена на ред L1
и стълб C1.
Последният ред на файла съдържа последователност от Nr знака измежду  {'N', 'S', 'E', 'V'}, които задават посоките по които Ана е премествала топа (i
-тият  знак от редицата съответства на i-тия ход).

Изход

Изходният файл sah.out трябва да съдържа на първия си ред едно положително цяло число p, показващо броя на възможните финални позиции.
Следващите p реда трябва да съдържат възможните крайни позиции, по една на ред. Всяка позиция се описва с две положителни цели цисла, отделени с интервал, L C, означаващи, че финалната позиция е върху ред L и стълб C. Финалните позиции трябва да са подредени по реда на номерата на редовете си. Ако има повече от една финална позиция с един един същ номер на ред, тогава те трябва да са подредени по реда на номерата на стълбовете си.

Ограничения и пояснения

1 < X <= 50
1 < N <= 1000
0 < Nr <= 1000
Фигурите са номерирани от 1 до N.
Редовете на дъската са номерирани отгоре надолу от 1 до X, а стълбовете - отляво надясно - от 1 до X.
Ана и Йон правят ходове, редувайки се, като Йон започва първи.
Топът може да бъде местен само в една от следните четири посоки:
север (N) - към ред с по-малък номер, оставайки на същия стълб;
юг (S) - към ред с по-голям номер, оставайки на същия стълб;
изток (E) - към стълб с по-голям номер, оставайки на същия ред;
запад (V) - към стълб с по-малък номер, оставайки на същия ред;
 

Пример
sah.in sah.out

5 8
2 2
3 2
4 3
5 4
4 5
3 5
2 5
2 4
4
3 4 2
4 5 3
1 1 2
2 5 1
SVNV

4
2 1
2 2
3 1
3 2

Time limit: 0.1 секунди за тест

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com

(превод на български: Емил Келеведжиев)