#P17843. [ONTAK 2021]ROB
[ONTAK 2021]ROB
小机器人
机器人在无限整数网格上运动,有 个不同的障碍格。程序由 条命令组成:U、D、R、L 分别尝试将 移动到 、、、。若目标格是障碍,机器人本次停在原地;否则完成移动。
给出 个起点,分别求从这些起点执行完整程序后的终点。各询问互不影响。
输入格式
第一行 ,第二行长度为 的命令串。接下来 行为障碍坐标,再接下来 行为起点坐标。
输出格式
输出 行,每行是相应终点的两个整数坐标。终点坐标可能为负数。
数据范围
,。输入的每个坐标均在 内。障碍互不相同,起点不会落在障碍上。
样例
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 分。