有 SPJ 的题不会是构造题。
题目描述
平面上有一个机器人，初始位于 $(0,0)$。有一个长为 $n$ 的包含 LRS 三种字母的字符串 $S$。 机器人会进行 $n$ 次移动，假设当前坐标为 $(x,y)$，对于第 $i$ 次移动：
若 $S_i$ 为 L，则移动至 $(x-1,y)$。
若 $S_i$ 为 R，则移动至 $(x+1,y)$。
若 $S_i$ 为 S，则移动至 $(x,y+1)$。
你可以在平面上放置若干个障碍，如果机器人将要移动到的位置上有障碍，则不会进行这次移动。
你的目标是让机器人在 $n$ 次移动后位于 $(X,Y)$。为了解题方便，保证 $X,Y\ge0$。
输入格式
从文件 $\texttt{robot.in}$ 中读入数据。
第一行三个非负整数 $n,X,Y$。
第二行一个长为 $n$ 的字符串序列 $S$。
输出格式
输出到文件 $\texttt{robot.out}$ 中。
无解输出 $-1$。
否则第一行一个非负整数 $m$，表示你放置的障碍数，需要保证 $m\le2\times10^6$，且 $(0,0)$ 处没有障碍。
接下来 $m$ 行每行两个整数 $x,y$，表示在 $(x,y)$ 处放置了障碍，需要保证 $x,y$ 在 int 范围内。
样例 1 输入
5 1 2
SRRSL样例 1 输出
0样例 2 输入
9 2 1
SRSLLSRSR样例 2 输出
3
-1 1
0 2
1 2样例 3
见选手目录下的 $\text{robot3.in}$ 与 $\text{robot3.ans}$。
数据范围与提示
$1\le n\le3\times10^5,0\le X,Y\le n$
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $1$ | $X+Y>n$ | $3$ |
| $2$ | $n\le 20$ | $12$ |
| $3$ | $n\le229$ | $25$ |
| $4$ | $n\le2024$ | $20$ |
| $5$ | $n\le22922$ | $20$ |
| $6$ | 无 | $20$ |
我们下发了 $\texttt{checker.cpp}$ 文件，可以编译生成可执行文件 $\texttt{checker}$ 来检查你输出的正确性。
$\texttt{checker}$ 的使用方法为：$\texttt{checker }$，参数依次代表输入文件、你的输出文件、答案文件。