题目描述

小可可的学校引进了一台智能清洁机器人，学校将机器人的工作区域划分为一个 $n \times n$ 大小的网格（如图 1 所示）。左上角单元格坐标为 $(0,0)$，右下角单元格坐标为 $(n-1,n-1)$。

上图是一个 $4 \times 4$ 大小的网格，机器人在第 1 行、第 1 列，坐标位置是 $(1,1)$。

智能清洁机器人可以接受 4 种移动指令：'L'（向左移动），'R'（向右移动），'U'（向上移动）和 'D'（向下移动）。收到一条指令后，机器人会按指令方向移动一个单元格。小可可给机器人的指令序列是一个长度为 $m$ 的字符串 $c$，其中仅包含 'L'、'R'、'U' 和 'D' 四种字符。机器人可以从 $c$ 中的第 $i$ 条指令 $c_i$（$0 \leq i \leq m-1$）开始执行，它将会逐条指令连续执行，直到指令序列结束。

在遇到下述情况之一时，机器人将会停止移动：

1. $c_i$ 的下一条指令将导致机器人移动到网格之外。
2. $c_i$ 没有后续指令可以执行。

机器人最开始位于坐标为 $(\text{row},\text{col})$ 的单元格上。

小可可想知道，若机器人从指令序列 $c$ 中第 $i$ 条指令 $c_i$ 开始执行，可以连续执行的指令数目。

输入格式

共 3 行，第一行两个正整数 $n$，$m$ 分别表示网格的行列数、指令序列的长度。 第二行包含两个正整数 $\text{row}$ 和 $\text{col}$，表示机器人最开始位于坐标为 $(\text{row},\text{col})$ 的单元格上。 第三行是一个长度为 $m$ 的字符串 $c$，表示小可可给机器人的指令序列。

输出格式

输出共 $m$ 行，每行一个整数。 第 $i$ 行表示从 $c$ 中第 $i$ 条指令 $c_i$ 开始执行，机器人可以连续执行的指令数目。

样例

输入数据#1

3 6
0 1
RRDDLU

输出数据#1

1
5
4
3
1
0

解释#1

机器人从 $(0,1)$ 出发，并从第 $i$ 条指令开始执行：

• 0："RRDDLU" 在移动到网格外之前，只能执行一条 "R" 指令。
• 1："RDDLU" 可以执行全部五条指令，机器人仍在网格内，最终到达（1，1）。
• 2："DDLU" 可以执行全部四条指令，机器人仍在网格内，最终到达（1，0）。
• 3："DLU" 可以执行全部三条指令，机器人仍在网格内，最终到达（0，0）。
• 4："LU" 在移动到网格外之前，只能执行一条 "L" 指令。
• 5："U" 如果向上移动，将会移动到网格外。

数据范围

• 保证对于所有数据满足：$1 \leq n \leq 60$，$1 \leq m \leq 2000$。
• $0 \leq \text{row}, \text{col} \leq n-1$。