Задача C. Открытый подсчёт 2

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Юный робототехник Вася построил робота, который способен перемещаться по неограниченному клетчатому полю согласно заложенной в него программе. Робот занимает ровно одну клетку поля. Программа для робота состоит из последовательности команд, разделённых пробелом. Каждая команда состоит из латинской буквы и натурального числа. Буква задаёт направление движения (U — на север, D — на юг, L — на запад, R — на восток), а число — количество клеток, на которое робот должен сдвинуться.

Робот выполняет команды в бесконечном цикле — т. е. после выполнения последней команды он снова переходит к первой.

На поле задана система координат. Ось ординат направлена не север, ось абсцисс направлена на восток. Робот начинает движение с клетки с координатами (0, 0).

Требуется по данной программе определить количество клеток внутри прямоугольника с координатами (x1, y1) − (x2, y2), которые будут когда-либо посещены роботом.

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Если правильный ответ на какой-то из тестов получить не удалось, выведите вместо него число 0.

Формат входного файла

Первая строка входного файла содержит целое число N — количество программ. Далее следует N пар строк. В каждой паре первая строка содержит программу, а вторая — целые числа x1 y1 x2 y2.

Формат выходного файла

Выходной файл должен содержать N целых чисел — количество клеток, посещённых роботом при выполнении каждой программы внутри соответствующего прямоугольника.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
U1 R2
1 1 3 2
L1 R2
100 -10 200 10
4
101

0.074s 0.012s 15