Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Корабль Одиссея движется по координатной плоскости. Он начинает плавание в точке `(0;0)` и направлен в положительном
направлении оси `Ox`. Составленный Одиссеем план плавания до Итаки состоит из `N` шагов, на каждом из которых корабль либо
движется на `1` единицу расстояния вперед (``F``), либо поворачивает под прямым углом налево (``L``) или направо (``R``).
План был хорош, пока не вмешался обиженный на героя Посейдон. Бог выбрал часть плана, состоящую из шагов с
номерами от `L` до `R` включительно, и заменил в нём все правые повороты на левые, а левые -- на правые. Одиссей -- очень
внимательный герой, он сразу же заметил подмену и понял, куда именно приведет его изменившийся план. Поэтому Посейдон
изменил план ещё раз, а потом ещё раз, и ещё... Каждый раз изменение применялось к текущему плану (уже учитывающему все изменения,
сделанные ранее), а не к изначальному плану Одиссея.
Помогите Одиссею отслеживать конечную точку путешествия по текущему плану после каждого из изменений. ||.llm|Выполнение вычислений реализовать как функцию с именем raschet, которой передаются входные данные как аргументы.||
В первой строке входных данных содержится пара положительных целых чисел `N` (`1 <= N <= 10^5 `) и `Q` (`1 <= Q <= 10^5`) -- количество
шагов в плане и количество сделанных Посейдоном изменений соответственно.
Во второй строке входных данных содержится описание плана Одиссея: строка из `N` букв ``F``, ``L`` или ``R`` без пробелов, каждая
буква обозначает один шаг (движение вперед либо поворот).
Затем следует `Q` строк -- описание сделанных Посейдоном изменений. Каждая строка содержит пару положительных целых
чисел `L` и `R` (`1 <= L <= R <= N`) -- минимальный и максимальный номер шага, затронутый изменением.
Выведите `Q` строк, каждая из которых содержит по `2` целых числа `x` и `y` -- координаты точки, в которой закончится
путешествие Одиссея с учетом всех внесенных к этому моменту изменений Посейдона.
```sample Пример ввода 1
15 3
FFLFLFLFFRFRRFF
6 9
8 12
2 15
```
```sample Пример вывода 1
0 3
-2 3
-2 -3
```
```sample Пример ввода 2
4 2
LRRL
1 1
1 4
```
```sample Пример вывода 2
0 0
0 0
```
```sample Пример ввода 3
3 2
FFF
3 3
1 3
```
```sample Пример вывода 3
3 0
3 0
```
В примере 1 первоначальный план имеет вид ``FFLFLFLFFRFRRFF`` и заканчивается в точке `(2; -1)`. После первого
изменения план имеет вид ``FFLFLFRFFRFRRFF`` и заканчивается в точке `(0; 3)`. После второго изменения план
имеет вид ``FFLFLFRFFLFLRFF`` и заканчивается в точке `(-2; 3)`. После третьего изменения план имеет
вид ``FFRFRFLFFRFRLFF`` и заканчивается в точке `(-2; -3)`. Пути изображены на рисунке, красным выделены
изменённые (по сравнению с предыдущей версией плана) повороты.
В примере 2 корабль только вращается на месте и никуда не перемещается, поэтому никогда не покинет точку `(0;0)`.
В примере 3 план не содержит поворотов, поэтому конечная точка останется на месте при любых изменениях.
Начало
Рабочее место участника
Дерево отрезков, декартово дерево, √-декомпозиция