CF606B.Testing Robots

The Cybernetics Failures (CF) organisation made a prototype of a bomb technician robot. To find the possible problems it was decided to carry out a series of tests. At the beginning of each test the robot prototype will be placed in cell (_x_0, _y_0) of a rectangular squared field of size x × y, after that a mine will be installed into one of the squares of the field. It is supposed to conduct exactly x·y tests, each time a mine is installed into a square that has never been used before. The starting cell of the robot always remains the same.

After placing the objects on the field the robot will have to run a sequence of commands given by string s, consisting only of characters 'L', 'R', 'U', 'D'. These commands tell the robot to move one square to the left, to the right, up or down, or stay idle if moving in the given direction is impossible. As soon as the robot fulfills all the sequence of commands, it will blow up due to a bug in the code. But if at some moment of time the robot is at the same square with the mine, it will also blow up, but not due to a bug in the code.

Moving to the left decreases coordinate y, and moving to the right increases it. Similarly, moving up decreases the x coordinate, and moving down increases it.

The tests can go on for very long, so your task is to predict their results. For each k from 0 to length(s) your task is to find in how many tests the robot will run exactly k commands before it blows up.

网络控制故障（CF）组织制造了一台拆弹机器人原型机。为了找出可能存在的问题，决定进行一系列测试。每次测试开始时，机器人原型机将被放置在尺寸为 $x \times y$ 的矩形方格场地中的某个单元格 $(x_0, y_0)$ 上，随后在场地的某一个方格中安放一枚地雷。计划总共进行恰好 $x \cdot y$ 次测试，且每次测试中地雷被安放在一个此前从未使用过的方格中。机器人的起始位置始终不变。

在场地中布置好机器人和地雷后，机器人将执行由字符串 $s$ 给出的一系列指令；该字符串仅包含字符 'L'、'R'、'U'、'D'。这些指令分别表示：向左、向右、向上、向下移动一格；若朝指定方向移动会越出场地边界，则机器人保持不动。机器人执行完全部指令序列后，将因代码缺陷而爆炸。但若在执行过程中某一时刻机器人恰好位于地雷所在的方格，则它也会立即爆炸，但此时并非由于代码缺陷所致。

向左移动会使 $y$ 坐标减 1，向右移动则使其加 1；类似地，向上移动会使 $x$ 坐标减 1，向下移动则使其加 1。

由于测试过程可能非常漫长，你的任务是预测其结果。对每个 $k$（从 $0$ 到 $\mathrm{length}(s)$），你需要计算：在多少次测试中，机器人恰好执行了 $k$ 条指令后就爆炸了。

The first line of the input contains four integers x, y, _x_0, _y_0 (1 ≤ x, y ≤ 500, 1 ≤ _x_0 ≤ x, 1 ≤ _y_0 ≤ y) — the sizes of the field and the starting coordinates of the robot. The coordinate axis X is directed downwards and axis Y is directed to the right.

The second line contains a sequence of commands s, which should be fulfilled by the robot. It has length from 1 to 100 000 characters and only consists of characters 'L', 'R', 'U', 'D'.

输入的第一行包含四个整数 $x$、$y$、$x_0$、$y_0$（$1 ≤ x, y ≤ 500$，$1 ≤ x_0 ≤ x$，$1 ≤ y_0 ≤ y$），表示场地的尺寸以及机器人的起始坐标。坐标轴 $X$ 向下为正方向，坐标轴 $Y$ 向右为正方向。

第二行包含一个由机器人执行的指令序列 $s$。该序列长度为 $1$ 至 $100\,000$ 个字符，且仅由字符 'L'、'R'、'U'、'D' 组成。

Print the sequence consisting of (length(s) + 1) numbers. On the k-th position, starting with zero, print the number of tests where the robot will run exactly k commands before it blows up.

输出一个由（字符串 $s$ 的长度 $+1$）个数组成的序列。从第 $0$ 个位置开始，在第 $k$ 个位置上输出机器人恰好执行 $k$ 条指令后爆炸的测试用例数量。

In the first sample, if we exclude the probable impact of the mines, the robot's route will look like that: .

在第一个样例中，如果不考虑地雷的潜在影响，机器人的路径将如下所示：。