Ана и Йон имат общ интерес към шаха и винаги, когато имат време, играят на шах. Понеже са оригинални хора, те са си поръчали шахматни дъски с различни размери, както и със специални набори от фигури. Ако нямат време да завършат играта, те запазват положението на фигурите върху дъската и продължават на следващия ден. Веднъж те имали проблем - Лонел, техният син разбъркал фигурите - и сега те се опитват да възстановят конфигурацията. Йон си спомня точно как е изглеждала конфигурацията вчера в началото на играта и си спомня точно ходовете, които той е направил. Ана си спомня, че тя е играла малко странно - през цялата игра е премествала само една фигура - топа. Тя не си спомня точно позициите в които го е поставяла, но си спомня посоките, по които го е придвижвала.
Задача
Напишете програма, която определя позициите в които може да бъде топът, който Ана е премествала.
Вход
Входният файл
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 |
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
(превод на български: Емил
Келеведжиев)