Профессор Префиксов создал нового экспериментального робота-пылесоса AI#622 с ИИ. Чтобы протестировать разработку, Префиксов поместил робота в комнату из бесконечного количества клеток. Теперь он хочет узнать, как робот выбирает маршрут уборки.

Профессор запустил робота на $n$ секунд. Каждую секунду робот перемещается вверх, вниз, вправо или влево по комнате на $x$ плиток. У профессора есть $m$ запросов, состоящих из двух чисел $a$ и $b$ ($a < b$). Для каждого запроса нужно узнать, на сколько клеток в высоту и в ширину отличается положение робота между секундами $a$ и $b$.

Входные данные

В первой строке заданы два числа - $n$ и $m$ ($n, m \leq 10^5$).

Затем идут $n$ строк. В $i$-ой строке - символ, означающий направление движения между $i-1$-ой и $i$-ой секундой: L - влево, R - вправо, U - вверх, D - вниз, и через пробел число $x_i$ ($x_i \leq 10^9$) - пройденное в этом направлении расстояние в клетках.

Затем идут $m$ строк с запросами профессора, содержащие числа $a_i$ и $b_i$.

Выходные данные

В ответ на каждый запрос в отдельной строке нужно вывести два числа через пробел. Первое число - разница в положении робота в секунды $a_i$ и $b_i$ по горизонтали. Второе число - по вертикали. Расстояние измеряется в клетках.

Подзадачи