E. Красочные запросы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a_1,a_2, \dots, a_n$$$. Каждый элемент изначально имеет значение $$$0$$$ и цвет $$$1$$$. Также вам дано $$$q$$$ запросов, которые нужно обработать:

  • Color $$$l$$$ $$$r$$$ $$$c$$$: Поменять цвет элементов $$$a_l,a_{l+1},\cdots,a_r$$$ на $$$c$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le c \le n$$$).
  • Add $$$c$$$ $$$x$$$: Прибавить $$$x$$$ к значениям всех элементов $$$a_i$$$ ($$$1 \le i \le n$$$), имеющих цвет $$$c$$$ ($$$1 \le c \le n$$$, $$$-10^9 \le x \le 10^9$$$).
  • Query $$$i$$$: Вывести $$$a_i$$$ ($$$1 \le i \le n$$$).
Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n,q \le 10^6$$$) — длину массива $$$a$$$ и количество запросов, которые нужно обработать.

Каждая из следующих $$$q$$$ строк содержит запрос, который задан в формате, описанном в условии задачи.

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

Выведите ответы на запросы третьего типа в отдельных строках.

Примеры
Входные данные
5 8
Color 2 4 2
Add 2 2
Query 3
Color 4 5 3
Color 2 2 3
Add 3 3
Query 2
Query 5
Выходные данные
2
5
3
Входные данные
2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2
Выходные данные
7
7
8
Примечание

Первый тестовый пример описан ниже. Синий, красный и зеленый обозначают цвета $$$1$$$, $$$2$$$ и $$$3$$$ соответственно.