题目描述

小可可的学校引进了一台智能清洁机器人，学校将机器人的工作区域划分为一个 $n\times n$ 的方格（左上角单元格坐标为 $(0,0)$，右下角单元格坐标为 $(n-1,n-1)$）。机器人初始位于单元格 $(\text{row},\text{col})$。

机器人可以接收长度为 $m$ 的指令字符串 $c$，其中每个字符是四种移动指令之一：$L$（向左移动）、$R$（向右移动）、$U$（向上移动）和 $D$（向下移动）。当机器人从指令串 $c$ 的第 $i$ 条指令开始（$0\le i\le m-1$）执行时，它会依次执行后续指令直到指令串结束或因为下一条指令会导致其移出网格，此时它停止执行。

小可可想知道：对于每个起始位置 $i$（$0\le i\le m-1$），若机器人从 $c[i]$ 开始执行，它能够连续执行的指令条数是多少。

输入格式

输入共 $3$ 行：

• 第一行包含两个正整数 $n$ 和 $m$，分别表示网格的行/列数与指令序列的长度。
• 第二行包含两个整数 $\text{row}$ 和 $\text{col}$，表示机器人初始所在单元格的坐标（$0\le \text{row},\text{col}\le n-1$）。
• 第三行是长度为 $m$ 的字符串 $c$，由字符 $L$、$R$、$U$、$D$ 组成，表示指令序列（下标从 $0$ 到 $m-1$）。

输出格式

输出共 $m$ 行。第 $i$ 行（$0\le i\le m-1$）是一个整数，表示如果机器人从指令串 $c$ 的第 $i$ 条指令开始执行，能够连续执行的指令条数。

样例输入

3 6
0 1
RRDDLU

样例输出

1
5
4
3
1
0

说明

样例 1 解释

机器人位于大小为 $3\times3$ 的网格中，初始位置 $(0,1)$，指令串为 $c=\text{RRDDLU}$（索引 $0\ldots5$）：

数据范围

• $1\le n\le 60$，$1\le m\le 2000$。
• $0\le \text{row},\text{col}\le n-1$。
• 字符串 $c$ 仅包含字符 $L$、$R$、$U$、$D$。