题目描述

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

上图是一个4×4 大小的网格，机器人在第1行、第1列，坐标位置是（1，1）。

智能清洁机器人可以接受4种移动指令：

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

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

1 、c i 的下一条指令将导致机器人移动到网格之外。

2 、c i没有后续指令可以执行。

机器人最开始位于坐标为（row， col）的单元格上。

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

输入格式

共3行，第一行两个正整数n，m 分别表示网格的行列数、指令序列的长度。

第二行包含两个正整数row 和 col，表示机器人最开始位于坐标为(row，col) 的单元格上。

第三行是一个长度为m 的字符串 c，表示小可可给机器人的指令序列。

输出格式

输出共m行，每行一个整数。

第i 行表示从 c 中第 i 条指令 ci开始执行，机器人可以连续执行的指令数目。

样例

3 6
0 1
RRDDLU

1
5
4
3
1
0

解释#1

0："RRDDLU" 在移动到网格外之前，只能执行一条 "R" 指令。

1："RDDLU" 可以执行全部五条指令，机器人仍在网格内，最终到达（1,1）。

2："DDLU" 可以执行全部四条指令，机器人仍在网格内，最终到达（0，0）。

3："DLU" 可以执行全部三条指今，机器人仍在网格内，最终到达（0，0）。

4："LU" 在移动到网格外之前，只能执行一条 "L" 指令。

5："U" 如果向上移动，将会移动到网格外。。

数据范围

-保证对于所有数据满足： $1≤n≤60，1≤m≤2000$。

• $0≤row，col≤n−1$。