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.


-----Input-----

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'.


-----Output-----

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.


-----Examples-----
Input
3 4 2 2
UURDRDRL

Output
1 1 0 1 1 1 1 0 6

Input
2 2 2 2
ULD

Output
1 1 1 1



-----Note-----

In the first sample, if we exclude the probable impact of the mines, the robot's route will look like that: $(2,2) \rightarrow(1,2) \rightarrow(1,2) \rightarrow(1,3) \rightarrow(2,3) \rightarrow(2,4) \rightarrow(3,4) \rightarrow(3,4) \rightarrow(3,3)$.

Difficulty: MEDIUM_HARD
Tags: Implementation

Starter code:

Solutions:
(x, y, x0, y0) = map(int, input().split())
S = input()
s = []
for i in range(len(S)):
	s.append(S[i])
X = [[0 for i in range(y + 2)] for j in range(x + 2)]
for i in range(y + 2):
	X[0][i] = -1
	X[x + 1][i] = -1
for i in range(x + 2):
	X[i][0] = -1
	X[i][y + 1] = -1
X[x0][y0] = 1
result = [1]
nr_explore = 1
for move in s:
	dx = 0
	dy = 0
	if move == 'U':
		dx = -1
		dy = 0
	elif move == 'D':
		dx = 1
		dy = 0
	elif move == 'R':
		dx = 0
		dy = 1
	elif move == 'L':
		dx = 0
		dy = -1
	if X[x0 + dx][y0 + dy] != -1:
		x0 += dx
		y0 += dy
		if X[x0][y0] == 0:
			nr_explore += 1
			X[x0][y0] = 1
			result.append(1)
		else:
			result.append(0)
	else:
		result.append(0)
result[-1] += x * y - nr_explore
for r in result:
	print(r, end=' ')


__author__ = 'Utena'
(x, y, x0, y0) = list(map(int, input().split()))
x1 = x0
y1 = y0
s = list(input())
k = 0
l = []
l1 = [[x0, y0]]
l2 = [[0] * (y + 1) for i in range(x + 1)]
for i in s:
	if i == 'R' and y0 < y:
		y0 += 1
		l1.append([x0, y0])
	elif i == 'L' and y0 > 1:
		y0 -= 1
		l1.append([x0, y0])
	elif i == 'U' and x0 > 1:
		x0 -= 1
		l1.append([x0, y0])
	elif i == 'D' and x0 < x:
		x0 += 1
		l1.append([x0, y0])
	else:
		l1.append([x0, y0])
for j in range(len(s)):
	x1 = l1[j][0]
	y1 = l1[j][1]
	l2[x1][y1] += 1
	if l2[x1][y1] > 1:
		l.append('0')
	else:
		l.append('1')
		k += 1
print(' '.join(l) + ' %d' % (x * y - k))


import itertools as it
import functools
import operator
import collections
import math
import sys

def solve(x, y, x0, y0, s):
	dir = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}
	seen = set()
	pos = (x0, y0)
	result = []
	for c in s:
		if pos in seen:
			result.append(0)
		else:
			result.append(1)
			seen.add(tuple(pos))
		(dx, dy) = dir[c]
		(nx, ny) = (pos[0] + dx, pos[1] + dy)
		pos0 = nx if 1 <= nx <= x else pos[0]
		pos1 = ny if 1 <= ny <= y else pos[1]
		pos = (pos0, pos1)
	result.append(x * y - len(seen))
	return result

def pp(*args, **kwargs):
	return print(*args, file=sys.stderr, **kwargs)

def main():
	(x, y, x0, y0) = map(int, input().split())
	s = input().strip()
	result = solve(x, y, x0, y0, s)
	print(*result)

def __starting_point():
	main()
__starting_point()


from functools import reduce
from operator import *
from math import *
from sys import *
from string import *
setrecursionlimit(10 ** 7)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
RI = lambda : list(map(int, input().split()))
RS = lambda : input().rstrip().split()
(x, y, x0, y0) = RI()
s = input()
total = 0
dirs = {'U': 0, 'D': 1, 'L': 2, 'R': 3}
visited = [[0 for i in range(y)] for j in range(x)]
for i in range(len(s)):
	if not visited[x0 - 1][y0 - 1]:
		print(1, end=' ')
		visited[x0 - 1][y0 - 1] = 1
		total += 1
	else:
		print(0, end=' ')
	x0 += dX[dirs[s[i]]]
	y0 += dY[dirs[s[i]]]
	if x0 < 1:
		x0 = 1
	elif x0 > x:
		x0 = x
	if y0 < 1:
		y0 = 1
	elif y0 > y:
		y0 = y
print(x * y - total)


(x, y, x0, y0) = [int(x) for x in input().split()]
x0 -= 1
y0 -= 1
commands = input()
xy = x * y
l = len(commands)
a = [0] * (l + 1)
n = 0
field = [[-1] * y for i in range(x)]
field[x0][y0] = 0
for i in range(l):
	command = commands[i]
	if command == 'U':
		if x0 > 0:
			x0 -= 1
	elif command == 'D':
		if x0 + 1 < x:
			x0 += 1
	elif command == 'L':
		if y0 > 0:
			y0 -= 1
	elif command == 'R':
		if y0 + 1 < y:
			y0 += 1
	if field[x0][y0] < 0:
		field[x0][y0] = i + 1
for i in range(x):
	for j in range(y):
		a[field[i][j]] += 1
print(' '.join((str(x) for x in a)))


(x, y, x0, y0) = map(int, input().split())
s1 = input()
r = x * y
res = '1 '
k = 1
a = [[0] * y for i in range(x)]
a[x0 - 1][y0 - 1] = 1
for i in range(len(s1) - 1):
	if s1[i] == 'U':
		if x0 - 1 >= 1 and k < r:
			x0 = x0 - 1
			if a[x0 - 1][y0 - 1] == 0:
				res = res + '1 '
				k = k + 1
				a[x0 - 1][y0 - 1] = 1
			else:
				res = res + '0 '
		else:
			res = res + '0 '
	if s1[i] == 'D':
		if x0 + 1 <= x and k < r:
			x0 = x0 + 1
			if a[x0 - 1][y0 - 1] == 0:
				res = res + '1 '
				k = k + 1
				a[x0 - 1][y0 - 1] = 1
			else:
				res = res + '0 '
		else:
			res = res + '0 '
	if s1[i] == 'L':
		if y0 - 1 >= 1 and k < r:
			y0 = y0 - 1
			if a[x0 - 1][y0 - 1] == 0:
				res = res + '1 '
				k = k + 1
				a[x0 - 1][y0 - 1] = 1
			else:
				res = res + '0 '
		else:
			res = res + '0 '
	if s1[i] == 'R':
		if y0 + 1 <= y and k < r:
			y0 = y0 + 1
			if a[x0 - 1][y0 - 1] == 0:
				res = res + '1 '
				k = k + 1
				a[x0 - 1][y0 - 1] = 1
			else:
				res = res + '0 '
		else:
			res = res + '0 '
print(res + str(r - k))


(x, y, x0, y0) = list(map(int, input().split()))
P = {(x0, y0)}
s = input()
c = 1
print(1, end=' ')
for i in range(len(s) - 1):
	if s[i] == 'L':
		if y0 >= 2:
			y0 -= 1
		if (x0, y0) in P:
			print(0, end=' ')
		else:
			print(1, end=' ')
			c += 1
			P.add((x0, y0))
	if s[i] == 'U':
		if x0 >= 2:
			x0 -= 1
		if (x0, y0) in P:
			print(0, end=' ')
		else:
			print(1, end=' ')
			c += 1
			P.add((x0, y0))
	if s[i] == 'R':
		if y0 < y:
			y0 += 1
		if (x0, y0) in P:
			print(0, end=' ')
		else:
			print(1, end=' ')
			c += 1
			P.add((x0, y0))
	if s[i] == 'D':
		if x0 < x:
			x0 += 1
		if (x0, y0) in P:
			print(0, end=' ')
		else:
			print(1, end=' ')
			c += 1
			P.add((x0, y0))
print(x * y - c)


import unittest
import sys

class Robots:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		[self.x, self.y, self.x0, self.y0] = map(int, uinput().split())
		self.nums = list(uinput())

	def calculate(self):
		xy = self.x * self.y
		loc = (self.x0, self.y0)
		locs = set([loc])
		result = [1]
		for (i, d) in enumerate(self.nums):
			(nx, ny) = loc
			if d == 'U':
				nx = max(1, loc[0] - 1)
			if d == 'D':
				nx = min(self.x, loc[0] + 1)
			if d == 'L':
				ny = max(1, loc[1] - 1)
			if d == 'R':
				ny = min(self.y, loc[1] + 1)
			loc = (nx, ny)
			if len(locs) == xy:
				result.append(0)
			elif i == len(self.nums) - 1:
				result.append(xy - len(locs))
			elif loc in locs:
				result.append(0)
			else:
				result.append(1)
			locs.add(loc)
		return ' '.join(map(str, result))

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '3 4 2 2\nUURDRDRL'
		d = Robots(test)
		self.assertEqual(d.x, 3)
		self.assertEqual(d.y, 4)
		self.assertEqual(d.x0, 2)
		self.assertEqual(d.y0, 2)
		self.assertEqual(d.nums[:2], ['U', 'U'])
		self.assertEqual(Robots(test).calculate(), '1 1 0 1 1 1 1 0 6')
		test = '2 2 2 2\nULD'
		self.assertEqual(Robots(test).calculate(), '1 1 1 1')
		test = ''
		test = ''

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Robots(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))
sys.setrecursionlimit(100000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
sys.stdout.write(Robots().calculate())


(x, y, x0, y0) = tuple(map(int, input().split()))
s = input()
l = len(s)
res = [0] * (l + 1)
location = [x0, y0]
movement = {tuple(location)}
for i in range(1, l + 1):
	let = s[i - 1]
	if let == 'L':
		if location[1] - 1 > 0:
			location[1] -= 1
	if let == 'R':
		if location[1] + 1 <= y:
			location[1] += 1
	if let == 'U':
		if location[0] - 1 > 0:
			location[0] -= 1
	if let == 'D':
		if location[0] + 1 <= x:
			location[0] += 1
	if tuple(location) in movement:
		res[i] = 0
	else:
		res[i] = 1
	movement.add(tuple(location))
res[0] = 1
res[l] += x * y - sum(res)
print(' '.join(list(map(str, res))))


COLOR_RED = '\x1b[1;31m'
COLOR_RESET = '\x1b[1;m'
(m, n, x, y) = map(int, input().split())
S = input()
visited = set()
visited.add((x, y))
cnt = 1
print('1 ', end='')
for e in S[0:len(S) - 1]:
	if e == 'U' and x > 1:
		x -= 1
	elif e == 'D' and x < m:
		x += 1
	elif e == 'R' and y < n:
		y += 1
	elif e == 'L' and y > 1:
		y -= 1
	if (x, y) not in visited:
		print('1 ', end='')
		cnt += 1
	else:
		print('0 ', end='')
	visited.add((x, y))
print(n * m - cnt)


def main():
	(h, w, y, x) = map(int, input().split())
	yx = (h - y) * w + x - 1
	neigh = []
	for i in range(h):
		for j in range(w):
			neigh.extend((i * w + j + w if i < h - 1 else i * w + j, i * w + j - w if i else j, i * w + j - 1 if j else i * w, i * w + j + 1 if j < w - 1 else i * w + j))
	field = [True] * (w * h)
	field[yx] = False
	res = ['1']
	for c in input()[:-1]:
		yx = neigh[yx * 4 + ('U', 'D', 'L', 'R').index(c)]
		if field[yx]:
			res.append('1')
			field[yx] = False
		else:
			res.append('0')
	res.append(str(sum(field)))
	print(' '.join(res))
main()


(x, y, x0, y0) = list(map(int, input().split(' ')))
g = [[0] * (y + 1) for i in range(x + 1)]
s = input()
result = [0] * len(s)
count = x * y
for i in range(len(s)):
	if g[x0][y0] == 0:
		g[x0][y0] = 1
		result[i] = 1
		count -= 1
	if s[i] == 'U' and x0 > 1:
		x0 -= 1
	if s[i] == 'D' and x0 < x:
		x0 += 1
	if s[i] == 'L' and y0 > 1:
		y0 -= 1
	if s[i] == 'R' and y0 < y:
		y0 += 1
print(' '.join(map(str, result)), count)


(x, y, x0, y0) = list(map(int, input().split()))
s = input()
x0 -= 1
y0 -= 1
k = [1]
summa = 1
a = [[0] * y for i in range(x)]
a[x0][y0] = 1
for i in s:
	if i == 'U':
		x0 = max(x0 - 1, 0)
	elif i == 'D':
		x0 = min(x0 + 1, x - 1)
	elif i == 'R':
		y0 = min(y0 + 1, y - 1)
	else:
		y0 = max(y0 - 1, 0)
	if a[x0][y0]:
		k.append(0)
	else:
		a[x0][y0] = 1
		k.append(1)
		summa += 1
k[-1] += x * y - summa
print(' '.join((str(i) for i in k)))


(n, m, x, y) = [int(x) for x in input().split(' ')]
commands = input()
(x, y) = (x - 1, y - 1)
move = dict([('U', (-1, 0)), ('D', (1, 0)), ('L', (0, -1)), ('R', (0, 1))])
place = set()
place.add((x, y))
print('1', end=' ')
for command in commands[:-1]:
	(oldX, oldY) = (x, y)
	(x, y) = (x + move[command][0], y + move[command][1])
	if (x < 0 or y < 0) or (x >= n or y >= m):
		print('0', end=' ')
		(x, y) = (oldX, oldY)
		continue
	elif (x, y) in place:
		print(0, end=' ')
	else:
		print('1', end=' ')
	place.add((x, y))
(x, y) = (x + move[commands[-1]][0], y + move[commands[-1]][1])
if (x < 0 or y < 0) or (x >= n or y >= m):
	print('0')
else:
	print(n * m - len(place))


__author__ = 'MoonBall'
import sys
T = 1

def process():
	(x, y, x0, y0) = list(map(int, input().split()))
	s = input()
	d = {}
	L = len(s)
	cnt = [0] * (L + 1)
	d[x0] = {}
	d[x0][y0] = 0
	for (idx, _s) in enumerate(s):
		if _s == 'L':
			y0 = max(1, y0 - 1)
		elif _s == 'R':
			y0 = min(y, y0 + 1)
		elif _s == 'U':
			x0 = max(1, x0 - 1)
		elif _s == 'D':
			x0 = min(x, x0 + 1)
		if not d.get(x0):
			d[x0] = {}
		t = d[x0]
		if t.get(y0) == None:
			t[y0] = idx + 1
	for (i, _) in d.items():
		for (j, v) in _.items():
			cnt[v] = cnt[v] + 1
	cnt[L] = cnt[L] + x * y - sum(cnt)
	print(' '.join(map(str, cnt[0:L + 1])))
for _ in range(T):
	process()


DIR = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}
(X, Y, x, y) = map(int, input().split())
S = input()
path = list()
path.append((x, y))
for (dx, dy) in map(lambda x: DIR[x], S):
	(xp, yp) = (x + dx, y + dy)
	if xp < 1 or xp > X or yp < 1 or (yp > Y):
		pass
	else:
		(x, y) = (xp, yp)
	path.append((x, y))
result = []
total = 0
vis = set()
for i in range(len(S)):
	if path[i] in vis:
		result.append(0)
	else:
		result.append(1)
		total += 1
	vis.add(path[i])
result.append(X * Y - total)
print(' '.join(map(str, result)))


(x, y, x0, y0) = list(map(int, input().split()))
s = input()
board = [[0] * y for _ in range(x)]
ans = [0] * (len(s) + 1)
ans[0] = 1
board[x0 - 1][y0 - 1] = 1
for i in range(len(s)):
	ch = s[i]
	if ch == 'U' and x0 > 1:
		x0 -= 1
		if board[x0 - 1][y0 - 1] == 0:
			ans[i + 1] = 1
			board[x0 - 1][y0 - 1] = 1
	if ch == 'D' and x0 < x:
		x0 += 1
		if board[x0 - 1][y0 - 1] == 0:
			ans[i + 1] = 1
			board[x0 - 1][y0 - 1] = 1
	if ch == 'R' and y0 < y:
		y0 += 1
		if board[x0 - 1][y0 - 1] == 0:
			ans[i + 1] = 1
			board[x0 - 1][y0 - 1] = 1
	if ch == 'L' and y0 > 1:
		y0 -= 1
		if board[x0 - 1][y0 - 1] == 0:
			ans[i + 1] = 1
			board[x0 - 1][y0 - 1] = 1
cnt0 = sum([row.count(0) for row in board])
ans[-1] += cnt0
print(*ans)


(x, y, xc, yc) = map(int, input().strip().split())
yc -= 1
xc -= 1
program = input().strip()
commands = {'U': (-1, 0), 'D': (1, 0), 'R': (0, 1), 'L': (0, -1)}
used = [[False] * y for i in range(x)]
used[xc][yc] = True
result = []
print(1, end=' ')
cnt = 1
for i in range(len(program)):
	cmd = program[i]
	xc += commands[cmd][0] if -1 < xc + commands[cmd][0] < x else 0
	yc += commands[cmd][1] if -1 < yc + commands[cmd][1] < y else 0
	if not used[xc][yc] and i != len(program) - 1:
		print(1, end=' ')
		result.append(1)
		cnt += 1
	elif i != len(program) - 1:
		print(0, end=' ')
		result.append(0)
	else:
		print(x * y - cnt, end=' ')
	used[xc][yc] = True


(x, y, sx, sy) = map(int, input().split())
(sx, sy) = (sx - 1, sy - 1)
direction = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
visited = [[False] * y for i in range(x)]
prev = (sx, sy)
s = input()
sm = x * y - 1
print(1, end=' ')
visited[prev[0]][prev[1]] = True
for c in s[:-1]:
	d = direction[c]
	cur = tuple(map(sum, zip(prev, d)))
	if not 0 <= cur[0] < x or not 0 <= cur[1] < y:
		cur = prev
	p = 1 - visited[cur[0]][cur[1]]
	print(p, end=' ')
	sm -= p
	visited[cur[0]][cur[1]] = True
	prev = cur
print(sm)


(x, y, x0, y0) = map(int, input().split())
s = input()
isVisited = []
for i in range(x):
	isVisited.append([])
	for j in range(y):
		isVisited[i].append(False)
cnt = 1
ans = ['1']
isVisited[x0 - 1][y0 - 1] = True
locx = x0 - 1
locy = y0 - 1
for elem in s:
	if elem == 'U':
		locx -= 1
		if locx < 0:
			locx = 0
	if elem == 'R':
		locy += 1
		if locy >= y:
			locy = y - 1
	if elem == 'D':
		locx += 1
		if locx >= x:
			locx = x - 1
	if elem == 'L':
		locy -= 1
		if locy < 0:
			locy = 0
	if not isVisited[locx][locy]:
		isVisited[locx][locy] = True
		ans.append('1')
		cnt += 1
	else:
		ans.append('0')
ans[-1] = int(ans[-1])
ans[-1] += x * y - cnt
ans[-1] = str(ans[-1])
print(' '.join(ans))


(X, Y, x0, y0) = [int(x) for x in input().split()]
commands = input()
pos = [x0, y0]
count = X * Y
result = [0] * len(commands)
visited = {}
for i in range(len(commands)):
	key = pos[0] + X * (pos[1] - 1)
	if key not in visited:
		result[i] = 1
		count -= 1
		visited[key] = 0
	if commands[i] == 'U' and pos[0] - 1 > 0:
		pos[0] -= 1
	elif commands[i] == 'D' and pos[0] + 1 <= X:
		pos[0] += 1
	elif commands[i] == 'L' and pos[1] - 1 > 0:
		pos[1] -= 1
	elif commands[i] == 'R' and pos[1] + 1 <= Y:
		pos[1] += 1
print(' '.join([str(x) for x in result]), count)


def tests(mr, mc, r0, c0, path):
	seen = set()
	(r, c) = (r0, c0)
	for d in path:
		if (r, c) in seen:
			yield 0
		else:
			seen.add((r, c))
			yield 1
		if d == 'U':
			if r > 1:
				r -= 1
		elif d == 'D':
			if r < mr:
				r += 1
		elif d == 'L':
			if c > 1:
				c -= 1
		elif d == 'R':
			if c < mc:
				c += 1
	yield (mr * mc - len(seen))
(mr, mc, r0, c0) = map(int, input().split())
path = input()
print(' '.join(map(str, tests(mr, mc, r0, c0, path))))


import sys
input = sys.stdin.readline
(x, y, cx, cy) = map(int, input().split())
S = input()[:-1]
cx -= 1
cy -= 1
s = {1000 * cx + cy}
ans = [0] * (len(S) + 1)
ans[0] = 1
for i in range(len(S) - 1):
	if S[i] == 'L':
		cy = max(0, cy - 1)
	elif S[i] == 'R':
		cy = min(y - 1, cy + 1)
	elif S[i] == 'U':
		cx = max(0, cx - 1)
	else:
		cx = min(x - 1, cx + 1)
	if 1000 * cx + cy not in s:
		ans[i + 1] = 1
		s.add(1000 * cx + cy)
ans[len(S)] = x * y - len(s)
print(*ans)


(rs, cs, r, c) = map(int, input().split())
s = input()
r -= 1
c -= 1
f = [[0] * cs for i in range(rs)]
res = [0] * len(s)
cnt = 0
for i in range(len(s)):
	if f[r][c] == 0:
		res[i] = 1
		cnt += 1
		f[r][c] = 1
	if s[i] == 'U' and r > 0:
		r -= 1
	elif s[i] == 'R' and c < cs - 1:
		c += 1
	elif s[i] == 'D' and r < rs - 1:
		r += 1
	elif s[i] == 'L' and c > 0:
		c -= 1
print(' '.join(map(str, res)), rs * cs - cnt)


(x, y, x0, y0) = map(int, input().split())
moves = input()
seen = [[False] * y for i in range(x)]
(currX, currY) = (x0 - 1, y0 - 1)
total = 0
for i in range(len(moves)):
	if not seen[currX][currY]:
		print('1', end=' ')
		total += 1
	else:
		print('0', end=' ')
	seen[currX][currY] = True
	if moves[i] == 'L':
		currY = max(currY - 1, 0)
	elif moves[i] == 'R':
		currY = min(currY + 1, y - 1)
	elif moves[i] == 'U':
		currX = max(currX - 1, 0)
	else:
		currX = min(currX + 1, x - 1)
print(x * y - total)


DELTAS = {'U': (-1, 0), 'R': (0, 1), 'D': (1, 0), 'L': (0, -1)}
try:
	while True:
		(h, w, y, x) = map(int, input().split())
		y -= 1
		x -= 1
		s = input()
		total = h * w - 1
		used = [[False] * w for i in range(h)]
		used[y][x] = True
		print(end='1 ')
		last = len(s) - 1
		for (i, c) in enumerate(s):
			(dy, dx) = DELTAS[c]
			ny = y + dy
			nx = x + dx
			if 0 <= ny < h and 0 <= nx < w:
				if i != last:
					if used[ny][nx]:
						print(end='0 ')
					else:
						print(end='1 ')
						used[ny][nx] = True
						total -= 1
				y = ny
				x = nx
			elif i != last:
				print(end='0 ')
		print(total)
except EOFError:
	pass


import time
(a, b, x, y) = (int(i) for i in input().split())
s = input()
ans = [0 for i in range(len(s) + 1)]
start = time.time()
acc = 0
x -= 1
y -= 1
map = [[0 for i in range(b)] for j in range(a)]
for i in range(len(s)):
	if map[x][y] == 0:
		ans[i] += 1
		map[x][y] = 1
	if s[i] == 'L' and y > 0:
		y -= 1
	elif s[i] == 'R' and y < b - 1:
		y += 1
	elif s[i] == 'D' and x < a - 1:
		x += 1
	elif s[i] == 'U' and x > 0:
		x -= 1
ans[len(s)] = a * b - sum([sum(i) for i in map])
for i in ans:
	print(i, end=' ')
print()
finish = time.time()


(x, y, x0, y0) = map(int, input().split())
g = [[0 for i in range(y + 1)] for j in range(x + 1)]
s = input()
result = [0] * len(s)
sum = x * y
for i in range(len(s)):
	if g[x0][y0] == 0:
		g[x0][y0] = 1
		result[i] = 1
		sum -= 1
	if s[i] == 'U':
		if x0 > 1:
			(x0, y0) = (x0 - 1, y0)
	elif s[i] == 'D':
		if x0 <= x - 1:
			(x0, y0) = (x0 + 1, y0)
	elif s[i] == 'R':
		if y0 <= y - 1:
			(x0, y0) = (x0, y0 + 1)
	elif y0 > 1:
		(x0, y0) = (x0, y0 - 1)
result.append(sum)
print(' '.join([str(i) for i in result]))


[size_x, size_y, x, y] = [int(x) for x in input().split()]
s = input()
coord = [x, y]
direction = {'U': [-1, 0], 'D': [1, 0], 'L': [0, -1], 'R': [0, 1]}
visited = {}
blown = 0
output = []
for c in s:
	if (coord[0], coord[1]) not in visited:
		output.append(1)
		visited[coord[0], coord[1]] = True
		blown += 1
	else:
		output.append(0)
	coord[0] += direction[c][0]
	coord[0] = max(1, coord[0])
	coord[0] = min(size_x, coord[0])
	coord[1] += direction[c][1]
	coord[1] = max(1, coord[1])
	coord[1] = min(size_y, coord[1])
output.append(size_x * size_y - blown)
print(' '.join((str(x) for x in output)))


(X, Y, x, y) = map(int, input().split())
s = list(input())
dir = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
field = [[1] * Y for i in range(X)]
x -= 1
y -= 1
for c in s:
	print(field[x][y])
	field[x][y] = 0
	x += dir[c][0]
	y += dir[c][1]
	if x < 0:
		x = 0
	if x >= X:
		x = X - 1
	if y < 0:
		y = 0
	if y >= Y:
		y = Y - 1
print(sum((sum(field[i]) for i in range(X))))


(A, B, C, D) = input().split()
a = int(A)
b = int(B)
c = int(C)
d = int(D)
lista = [[0 for i in range(555)] for j in range(555)]
c -= 1
d -= 1
lista[c][d] = 1
s = input()
k = len(s)
l = 1
print('1 ', end='')
for i in range(k):
	if i + 1 == k:
		print(a * b - l)
		break
	if s[i] == 'U':
		if c:
			c -= 1
	elif s[i] == 'D':
		if c < a - 1:
			c += 1
	elif s[i] == 'R':
		if d < b - 1:
			d += 1
	elif d:
		d -= 1
	if lista[c][d] == 0:
		print('1 ', end='')
		l += 1
	else:
		print('0 ', end='')
	lista[c][d] = 1


(x, y, a, b) = list(map(int, input().split()))
s = input()
m = [[0] * y for i in range(x)]
ans = '1 '
k = 1
m[a - 1][b - 1] = 1
for i in range(len(s)):
	if s[i] == 'D':
		a = min(a + 1, x)
		m[a - 1][b - 1] += 1
		if m[a - 1][b - 1] == 1:
			k += 1
			ans += '1 '
		else:
			ans += '0 '
	elif s[i] == 'U':
		a = max(a - 1, 1)
		m[a - 1][b - 1] += 1
		if m[a - 1][b - 1] == 1:
			k += 1
			ans += '1 '
		else:
			ans += '0 '
	elif s[i] == 'R':
		b = min(b + 1, y)
		m[a - 1][b - 1] += 1
		if m[a - 1][b - 1] == 1:
			k += 1
			ans += '1 '
		else:
			ans += '0 '
	else:
		b = max(b - 1, 1)
		m[a - 1][b - 1] += 1
		if m[a - 1][b - 1] == 1:
			k += 1
			ans += '1 '
		else:
			ans += '0 '
ans = ans[:-1]
k -= int(ans[-1])
ans = ans[:-1]
ans += str(x * y - k)
print(ans)


(x, y, sx, sy) = map(int, input().split())
s = input()
st = set()
z = x * y
for i in range(len(s)):
	if not (sx, sy) in st:
		st.add((sx, sy))
		print(1, end=' ')
		z -= 1
	else:
		print(0, end=' ')
	c = s[i]
	if c == 'U' and sx > 1:
		sx -= 1
	elif c == 'D' and sx < x:
		sx += 1
	elif c == 'L' and sy > 1:
		sy -= 1
	elif c == 'R' and sy < y:
		sy += 1
print(z)


(rows, cols, r, c) = map(int, input().split())
s = input()
r -= 1
c -= 1
field = [[0] * cols for i in range(rows)]
res = [0] * len(s)
field[r][c] = 1
cnt = 1
for i in range(len(s)):
	if s[i] == 'U':
		if r > 0:
			r -= 1
	elif s[i] == 'R':
		if c < cols - 1:
			c += 1
	elif s[i] == 'D':
		if r < rows - 1:
			r += 1
	elif s[i] == 'L':
		if c > 0:
			c -= 1
	if field[r][c] == 0:
		res[i] = 1
		cnt += 1
		field[r][c] = 1
res[len(s) - 1] += rows * cols - cnt
print(1, ' '.join(map(str, res)))


(n, m, x, y) = map(int, input().split())
(s, t) = ([1], [[1] * (m + 1) for i in range(n + 1)])
for d in input():
	t[x][y] = 0
	if d == 'U':
		x = max(x - 1, 1)
	elif d == 'D':
		x = min(x + 1, n)
	elif d == 'L':
		y = max(y - 1, 1)
	else:
		y = min(y + 1, m)
	s.append(t[x][y])
s[-1] += n * m - sum(s)
print(' '.join(map(str, s)))


(q, b, c, d) = map(int, input().split())
s = input()
(x, y) = (c, d)
l = 1
print(1, end=' ')
a = set()
a.add((c, d))
for i in range(len(s) - 1):
	item = s[i]
	if item == 'U':
		if x == 1 or (x - 1, y) in a:
			print(0, end=' ')
			if (x - 1, y) in a:
				x -= 1
		else:
			print(1, end=' ')
			x -= 1
			l += 1
	elif item == 'R':
		if y == b or (x, y + 1) in a:
			print(0, end=' ')
			if (x, y + 1) in a:
				y += 1
		else:
			print(1, end=' ')
			y += 1
			l += 1
	elif item == 'L':
		if y == 1 or (x, y - 1) in a:
			print(0, end=' ')
			if (x, y - 1) in a:
				y -= 1
		else:
			print(1, end=' ')
			y -= 1
			l += 1
	elif x == q or (x + 1, y) in a:
		print(0, end=' ')
		if (x + 1, y) in a:
			x += 1
	else:
		print(1, end=' ')
		x += 1
		l += 1
	a.add((x, y))
print(q * b - l)


s = str(input()).split()
x = int(s[0])
y = int(s[1])
x0 = int(s[2]) - 1
y0 = int(s[3]) - 1
s = str(input())
g = [[0] * y for i in range(x)]
count = x * y
res = [0] * (len(s) + 1)
for i in range(len(s)):
	if g[x0][y0] == 0:
		res[i] = 1
		g[x0][y0] = 1
		count -= 1
	if s[i] == 'U' and x0 > 0:
		x0 -= 1
	if s[i] == 'D' and x0 < x - 1:
		x0 += 1
	if s[i] == 'L' and y0 > 0:
		y0 -= 1
	if s[i] == 'R' and y0 < y - 1:
		y0 += 1
res[-1] = count
for i in range(len(res)):
	print(res[i], end=' ')


(x, y, x0, y0) = list(map(int, input().split()))
s = input()
s = s[:len(s) - 1]
visited = [[False for i in range(y + 1)] for j in range(x + 1)]
visited[x0][y0] = True
ans = '1 '
cnt = 1
for i in s:
	if i == 'U':
		if x0 != 1:
			x0 -= 1
			if not visited[x0][y0]:
				ans += '1 '
				cnt += 1
				visited[x0][y0] = True
			else:
				ans += '0 '
		else:
			ans += '0 '
	elif i == 'D':
		if x0 != x:
			x0 += 1
			if not visited[x0][y0]:
				ans += '1 '
				cnt += 1
				visited[x0][y0] = True
			else:
				ans += '0 '
		else:
			ans += '0 '
	elif i == 'L':
		if y0 != 1:
			y0 -= 1
			if not visited[x0][y0]:
				ans += '1 '
				cnt += 1
				visited[x0][y0] = True
			else:
				ans += '0 '
		else:
			ans += '0 '
	elif y0 != y:
		y0 += 1
		if not visited[x0][y0]:
			ans += '1 '
			cnt += 1
			visited[x0][y0] = True
		else:
			ans += '0 '
	else:
		ans += '0 '
z = str(x * y - cnt)
print(ans + z)


(x, y, x0, y0) = map(int, input().split())
s = input()
z = set()
k = (len(s) + 1) * [0]
k[0] = 1
u = 0
z.add((x0, y0))
for i in s:
	u += 1
	if i == 'U' and x0 > 1:
		x0 -= 1
	elif i == 'D' and x0 < x:
		x0 += 1
	elif i == 'L' and y0 > 1:
		y0 -= 1
	elif i == 'R' and y0 < y:
		y0 += 1
	if not (x0, y0) in z:
		k[u] += 1
		z.add((x0, y0))
k[len(s)] += x * y - sum(k)
for i in k:
	print(i, end=' ')


(a, b, x, y) = map(int, input().split())
s = input()
p = []
for i in range(a + 1):
	p.append([0] * (b + 1))
sum = 0
for i in range(len(s)):
	if p[x][y] == 0:
		p[x][y] = 1
		print(1, end=' ')
		sum += 1
	else:
		print(0, end=' ')
	if s[i] == 'U' and x != 1:
		x -= 1
	if s[i] == 'D' and x != a:
		x += 1
	if s[i] == 'L' and y != 1:
		y -= 1
	if s[i] == 'R' and y != b:
		y += 1
print(a * b - sum)


(M, N, x, y) = input().split()
s = input()
M = int(M)
N = int(N)
x = int(x) - 1
y = int(y) - 1
ans = [0 for i in range(len(s) + 10)]
has = [[0 for j in range(N)] for i in range(M)]
has[x][y] = 1
c = 1
ans[0] = 1
for i in range(len(s) - 1):
	if s[i] == 'U' and x - 1 >= 0:
		x -= 1
	if s[i] == 'D' and x + 1 < M:
		x += 1
	if s[i] == 'L' and y - 1 >= 0:
		y -= 1
	if s[i] == 'R' and y + 1 < N:
		y += 1
	if has[x][y] == 0:
		c += 1
		ans[i + 1] = has[x][y] = 1
for i in range(len(s)):
	print(ans[i], end=' ')
print(M * N - c)


(x, y, m, n) = map(int, input().split())
cmd = input()
m -= 1
n -= 1
visited = [[False] * y for _ in range(x)]
i = m
j = n
ans = [1]
visited[i][j] = True
left = x * y - 1
while len(cmd):
	c = cmd[0]
	cmd = cmd[1:]
	if c == 'L':
		j -= 1
	elif c == 'R':
		j += 1
	elif c == 'U':
		i -= 1
	elif c == 'D':
		i += 1
	i = min(max(i, 0), x - 1)
	j = min(max(j, 0), y - 1)
	if not visited[i][j]:
		visited[i][j] = True
		ans.append(1)
		left -= 1
	else:
		ans.append(0)
ans[-1] += left
print(*ans)


(mr, mc, R, C) = map(int, input().split())
s = input()
vis = set()
(r, c, res) = (R, C, '')
for d in s:
	if (r, c) in vis:
		res += '0 '
	else:
		vis.add((r, c))
		res += '1 '
	if d == 'U':
		if r > 1:
			r -= 1
	elif d == 'D':
		if r < mr:
			r += 1
	elif d == 'L':
		if c > 1:
			c -= 1
	elif d == 'R':
		if c < mc:
			c += 1
res += str(mr * mc - len(vis))
print(res)


(x, y, x1, y1) = map(int, input().split())
mat = [[0] * (y + 2) for ll in range(x + 2)]
for i in range(y + 2):
	mat[0][i] = 't'
	mat[-1][i] = 't'
for i in range(x + 2):
	mat[i][0] = 't'
	mat[i][-1] = 't'
s = input()
ans = [1]
for i in range(len(s)):
	k = s[i]
	if k == 'U':
		if mat[x1 - 1][y1] == 't':
			ans.append(0)
		elif mat[x1 - 1][y1] == 'm':
			ans.append(0)
			mat[x1][y1] = 'm'
			x1 -= 1
		else:
			mat[x1][y1] = 'm'
			x1 -= 1
			ans.append(1)
	elif k == 'D':
		if mat[x1 + 1][y1] == 't':
			ans.append(0)
		elif mat[x1 + 1][y1] == 'm':
			ans.append(0)
			mat[x1][y1] = 'm'
			x1 += 1
		else:
			mat[x1][y1] = 'm'
			x1 += 1
			ans.append(1)
	elif k == 'R':
		if mat[x1][y1 + 1] == 't':
			ans.append(0)
		elif mat[x1][y1 + 1] == 'm':
			ans.append(0)
			mat[x1][y1] = 'm'
			y1 += 1
		else:
			mat[x1][y1] = 'm'
			y1 += 1
			ans.append(1)
	elif k == 'L':
		if mat[x1][y1 - 1] == 't':
			ans.append(0)
		elif mat[x1][y1 - 1] == 'm':
			ans.append(0)
			mat[x1][y1] = 'm'
			y1 -= 1
		else:
			mat[x1][y1] = 'm'
			y1 -= 1
			ans.append(1)
print(*ans[:-1], x * y - sum(ans[:-1]))


(x, y, x0, y0) = [int(x) for x in input().split()]
s = input()
was_in = [[False for y1 in range(y + 1)] for x1 in range(x + 1)]
length = 1
moves = {'D': (1, 0), 'U': (-1, 0), 'R': (0, 1), 'L': (0, -1)}
state = (x0, y0)
count = [1]
was_in[x0][y0] = True
for c in s:
	new_state = (state[0] + moves[c][0], state[1] + moves[c][1])
	new_state = new_state if 0 < new_state[0] <= x and 0 < new_state[1] <= y else state
	state = new_state
	if was_in[state[0]][state[1]]:
		count.append(0)
	else:
		count.append(1)
		was_in[state[0]][state[1]] = True
		length += 1
count[-1] += x * y - length
for i in count:
	print(i, end=' ')