У вас есть массив \(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\)).
Выходные данные
Выведите ответы на запросы третьего типа в отдельных строках.
Примечание
Первый тестовый пример описан ниже. Синий, красный и зеленый обозначают цвета \(1\), \(2\) и \(3\) соответственно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2
|
7
7
8
|