D. Маленький Декарт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Декарт получил в подарок последовательность целых чисел от $$$1$$$ до $$$n$$$, расположенных так, что число $$$i$$$ стоит на $$$i$$$-м месте.

Не понятно от чего, Декарту сразу захотелось брать отрезки внутри последовательности и что-нибудь с ними делать. Быстро обнаружилось, что маленький Декарт умеет только два типа действий:

  • «reverse i j» — перевернуть порядок чисел, которые находятся в отрезке с $$$i$$$ по $$$j$$$.
  • «inverse i j» — умножить каждое число с отрезка от $$$i$$$ до $$$j$$$ на $$$-1$$$.

В обоих случаях $$$1 \leq i \leq j \leq n$$$.

Так Декарт провёл все выходные, о чём рассказал своему другу Поликарпу. Маленький Декарт записал все действия в порядке их применения к последовательности и показал Поликарпу. Если Поликарп правильно скажет, какое число стоит на месте $$$pos$$$ после всех операций, то Декарт даст ему последовательность на выходные.

Поликарп очень хочет поиграть с числами, но увидев большой список он побледнел. Поэтому он просит вас о помощи — по списку операций определите число на требуемой позиции.

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

В первой строке содержатся два целых числа $$$n$$$ и $$$m$$$ — количество чисел в последовательности и количество действий ($$$1 \leq n \leq 10^9$$$; $$$0 \leq m \leq 10^5$$$).

В каждой из следующих $$$m$$$ строках содержится описание очередного действия.

В последней строке содержится целое число $$$pos$$$ ($$$1 \leq pos \leq n$$$).

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

Выведите число, которое находится на месте $$$pos$$$ после всех действий.

Примеры
Входные данные
5 4
inverse 1 3
reverse 2 5
reverse 1 3
inverse 2 4
3
Выходные данные
1
Входные данные
3 2
reverse 1 2
inverse 2 3
2
Выходные данные
-1
Входные данные
3 2
inverse 1 2
reverse 2 3
2
Выходные данные
3
Примечание

В первом примере последовательность меняется следующим образом:

$$$(1, 2, 3, 4, 5) \rightarrow (-1, -2, -3, 4, 5) \rightarrow (-1, 5, 4, -3, -2) \rightarrow (4, 5, -1, -3, -2) \rightarrow (4, -5, 1, 3, -2)$$$