#P17843. [ONTAK 2021]ROB

[ONTAK 2021]ROB

小机器人

机器人在无限整数网格上运动,有 kk 个不同的障碍格。程序由 nn 条命令组成:U、D、R、L 分别尝试将 (x,y)(x,y) 移动到 (x,y+1)(x,y+1)、(x,y−1)(x,y-1)、(x+1,y)(x+1,y)、(x−1,y)(x-1,y)。若目标格是障碍,机器人本次停在原地;否则完成移动。

给出 qq 个起点,分别求从这些起点执行完整程序后的终点。各询问互不影响。

输入格式

第一行 n,k,qn,k,q,第二行长度为 nn 的命令串。接下来 kk 行为障碍坐标,再接下来 qq 行为起点坐标。

输出格式

输出 qq 行,每行是相应终点的两个整数坐标。终点坐标可能为负数。

数据范围

1≤n,q≤500001\le n,q\le50000,1≤k≤1001\le k\le100。输入的每个坐标均在 [0,106][0,10^6] 内。障碍互不相同,起点不会落在障碍上。

样例

4 2 5
LURD
0 0
1 2
1 0
1 1
2 0
2 1
2 2
2 0
0 1
2 0
2 0
3 2

来源

(https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2021/p/rob/)。中文整理与独立加强数据;本包每题 20 个测试点,每点 5 分。