Colorful Operations
You have an array $$$a_1,a_2, \dots, a_n$$$. Each element initially has value $$$0$$$ and color $$$1$$$. You are also given $$$q$$$ queries to perform:   Color $$$l$$$ $$$r$$$ $$$c$$$: Change the color of elements $$$a_l,a_{l+1},\cdots,a_r$$$ to $$$c$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le c \le n$$$).  Add $$$c$$$ $$$x$$$: Add $$$x$$$ to values of all elements $$$a_i$$$ ($$$1 \le i \le n$$$) of color $$$c$$$ ($$$1 \le c \le n$$$, $$$-10^9 \le x \le 10^9$$$).  Query $$$i$$$: Print $$$a_i$$$ ($$$1 \le i \le n$$$). 
The first sample test is explained below. Blue, red and green represent colors $$$1$$$, $$$2$$$ and $$$3$$$ respectively.  
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^6$$$) — the length of array $$$a$$$ and the number of queries you have to perform.Each of the next $$$q$$$ lines contains the query given in the form described in the problem statement.
Print the answers to the queries of the third type on separate lines.
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def add(s, t, x):
    (s, t) = (s + l1, t + l1)
    while s <= t:
        if s & 1:
            tree1[s] += x
            s += 1
        s >>= 1
        if not t & 1:
            tree1[t] += x
            t -= 1
        t >>= 1
    return

def get(i):
    i += l1
    ans = 0
    while i:
        ans += tree1[i]
        i >>= 1
    return ans

def update(i, x):
    i += l1
    tree2[i] = x
    i >>= 1
    while i:
        tree2[i] = max(tree2[2 * i], tree2[2 * i + 1])
        i >>= 1
    return

def get_max(s, t):
    (s, t) = (s + l1, t + l1)
    ans = 0
    while s <= t:
        if s & 1:
            ans = max(ans, tree2[s])
            s += 1
        s >>= 1
        if not t & 1:
            ans = max(ans, tree2[t])
            t -= 1
        t >>= 1
    return ans
(n, q) = map(int, input().split())
(u, v) = ([0] * (n + 5), [0] * (n + 5))
v[1] = 1
l1 = pow(2, (n + 5).bit_length())
l2 = 2 * l1
tree1 = [0] * l2
tree2 = [0] * l2
update(1, 1)
update(n + 1, n + 1)
nx = [0] * (n + 5)
(nx[1], nx[n + 1]) = (n, n + 1)
ans = []
for _ in range(q):
    q0 = list(input().rstrip().decode().split())
    if q0[0] == 'Color':
        (l, r, c) = (int(q0[1]), int(q0[2]), int(q0[3]))
        if not nx[l]:
            i = get_max(1, l - 1)
            v[l] = v[i]
            nx[l] = nx[i]
            nx[i] = l - 1
            update(l, l)
        if not nx[r + 1]:
            i = get_max(l, r)
            v[r + 1] = v[i]
            nx[r + 1] = nx[i]
            nx[i] = r
            update(r + 1, r + 1)
        i = l
        while i <= r:
            j = nx[i]
            add(i, j, u[v[i]])
            if i ^ l:
                update(i, 0)
            (nx[i], v[i]) = (0, 0)
            i = j + 1
        (nx[l], v[l]) = (r, c)
        add(l, r, -u[c])
    elif q0[0] == 'Add':
        (c, x) = (int(q0[1]), int(q0[2]))
        u[c] += x
    else:
        i = int(q0[1])
        c = v[get_max(1, i)]
        ans0 = get(i) + u[c]
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def add(s, t, x):
    (s, t) = (s + l1, t + l1)
    while s <= t:
        if s & 1:
            tree1[s] += x
            s += 1
        s >>= 1
        if not t & 1:
            tree1[t] += x
            t -= 1
        t >>= 1
    return

def get(i):
    i += l1
    ans = 0
    while i:
        ans += tree1[i]
        i >>= 1
    return ans

def update(i, x):
    i += l1
    tree2[i] = x
    i >>= 1
    while i:
        tree2[i] = max(tree2[2 * i], tree2[2 * i + 1])
        i >>= 1
    return

def get_max(s, t):
    (s, t) = (s + l1, t + l1)
    ans = 0
    while s <= t:
        if s & 1:
            ans = max(ans, tree2[s])
            s += 1
        s >>= 1
        if not t & 1:
            ans = max(ans, tree2[t])
            t -= 1
        t >>= 1
    return ans
(n, q) = map(int, input().split())
(u, v) = ([0] * (n + 5), [0] * (n + 5))
v[1] = 1
l1 = pow(2, (n + 5).bit_length())
l2 = 2 * l1
tree1 = [0] * l2
tree2 = [0] * l2
update(1, 1)
update(n + 1, n + 1)
nx = [0] * (n + 5)
(nx[1], nx[n + 1]) = (n, n + 1)
ans = []
for _ in range(q):
    q0 = list(input().rstrip().decode().split())
    if q0[0] == 'Color':
        (l, r, c) = (int(q0[1]), int(q0[2]), int(q0[3]))
        if not nx[l]:
            i = get_max(1, l - 1)
            v[l] = v[i]
            nx[l] = nx[i]
            nx[i] = l - 1
            update(l, l)
        if not nx[r + 1]:
            i = get_max(l, r)
            v[r + 1] = v[i]
            nx[r + 1] = nx[i]
            nx[i] = r
            update(r + 1, r + 1)
        i = l
        while i <= r:
            j = nx[i]
            add(i, j, u[v[i]])
            if i ^ l:
                update(i, 0)
            (nx[i], v[i]) = (0, 0)
            i = j + 1
        (nx[l], v[l]) = (r, c)
        add(l, r, -u[c])
    elif q0[0] == 'Add':
        (c, x) = (int(q0[1]), int(q0[2]))
        u[c] += x
    else:
        i = int(q0[1])
        c = v[get_max(1, i)]
        ans0 = get(i) + u[c]
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') not in [None, '0']
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

    def val(self, it):
        """"""
        (pos, idx) = it
        return self._lists[pos][idx]

    def erase(self, it):
        """"""
        (pos, idx) = it
        self._delete(pos, idx)

    def begin(self):
        """"""
        return (0, 0)

    def end(self):
        """"""
        return (len(self._lists) - 1, len(self._lists[-1])) if self._lists else (0, 0)

    def prev(self, it):
        """"""
        (pos, idx) = it
        return (pos, idx - 1) if idx else (pos - 1, len(self._lists[pos - 1]) - 1)

    def next(self, it):
        """"""
        (pos, idx) = it
        return (pos, idx + 1) if pos + 1 == len(self._lists) or idx + 1 != len(self._lists[pos]) else (pos + 1, 0)

class FenwickTreeSum:

    def __init__(self, N):
        """"""
        self.tree = [0] * N

    def query(self, end):
        """"""
        x = 0
        while end:
            x += self.tree[end - 1]
            end &= end - 1
        return x

    def update(self, idx, x):
        """"""
        while idx < len(self.tree):
            self.tree[idx] += x
            idx |= idx + 1

def solve():
    (N, Q) = list(map(int, input().split()))
    starts = SortedList([0])
    colors = [1] + [0] * N

    def split(x):
        it = starts.prev(starts._loc_right(x))
        s = starts.val(it)
        if s == x:
            return
        starts.add(x)
        colors[x] = colors[s]
    add = [0] * (N + 1)
    fen = FenwickTreeSum(N + 1)

    def add_range(s, e, v):
        fen.update(s, v)
        fen.update(e + 1, -v)
    res = []
    for _ in range(Q):
        ts = input().decode().strip().split()
        if ts[0] == 'Color':
            (l, r, c) = (int(ts[1]) - 1, int(ts[2]), int(ts[3]))
            split(l)
            split(r)
            it = starts.prev(starts._loc_right(l))
            remove = []
            while starts.val(it) != r:
                s = starts.val(it)
                nit = starts.next(it)
                add_range(s, starts.val(nit) - 1, add[colors[s]] - add[c])
                it = nit
                remove.append(s)
            for s in remove:
                starts.remove(s)
            colors[l] = c
            starts.add(l)
        elif ts[0] == 'Add':
            (c, x) = (int(ts[1]), int(ts[2]))
            add[c] += x
        elif ts[0] == 'Query':
            x = int(ts[1]) - 1
            i = starts.bisect_right(x) - 1
            v = fen.query(x + 1) + add[colors[starts[i]]]
            res.append(v)
    print('\n'.join(map(str, res)))
if __name__ == '__main__':
    solve()