spoj
Състезание
Задача
H
Наименование
ЖАБАТА-ПРИНЦЕСА

Условие

H. ЖАБАТА-ПРИНЦЕСА 
---
Всеки ден Крис тича около езерото с N водни лилии. В езерото живее жабата Квак, която подскача по листата на лилиите. По спомени от приказките, Крис вярва, че ако целуне Квак, тя ще се превърне в красива принцеса. Но как да я хване? 

След продължителни наблюдения Крис установява, че Квак може да подскача само в четири посоки, които той отбелязва с буквите A – североизток, B – югоизток , C – северозапад и D –  югозапад. Всяка разходка е предварително планирана и се извършва по списък от K последователни посоки за подскок. Квак скача винаги до най-близкото листо в избраната посока. Ако няма листо в избраната посока, Квак остава на листото на което се намира, след което пробва подскок в следващата посока в списъка. След като Квак скочи, листото, от което е скочила потъва и изчезва. По време на разходката всички листа са неподвижни. Крис използва това обстоятелство и изготвя списък с целочислените координати на листата. Положителната посока на абсцисата на координатната система, която използва, сочи изток. Крис иска да определи координатите на листото, на което Квак ще се окаже накрая. Той ще я изчака там и ще я целуне. Напишете програма, която решава проблема на Крис и му помага да превърне Квак в красива принцеса. 

Вход: От първия ред на стандартния вход се въвежда броя на тестовите случаи. Всеки тест започва с ред, на който са зададени N и K. На третия ред ще е зададен низ с K букви, всяка от които е A, B, C или D – редицата от посоките, в които Квак се опитва да скочи. Всеки от следващите N реда съдържа две цели числа X и Y – координатите на едно от растенията. Квак първоначално се намира на растението, чиито координати са посочени на първия от тези редове. 

Изход: За всеки тестов случай програмата трябва да изведе на отделен ред на стандартния изход координатите на растението, до което ще стигне Квак за съответния тестов случай, разделени с един интервал. 

Ограничения: 1 ≤ N, K ≤ 10^5, 0 ≤ X ≤ 10^9, 0 ≤ Y ≤ 10^9. 

Примерен вход:
2      
7 5       
ACDBB 
5 6 
8 9 
4 13 
1 10 
7 4 
10 9 
3 7 
6 12 
AAAAAABCCCDD 
1 1 
2 2 
3 3 
4 4 
5 3 
6 2 

Примерен изход:
7 4 
5 3

« Предходна страница Решение Въпрос