It's Christmas time and Santa is in town. There are N children each having a bag with a mission to fill in as many toffees as possible. They are accompanied by a teacher whose ulterior motive is to test their counting skills. The toffees are of different brands (denoted by lowercase letters a-z). Santa picks up a child numbered m and gives n toffees of brand p to the child.

The teacher wishes to ask the children to calculate the number of toffees there are of a particular brand amongst a given range of children. Formally, there are 2 queries:

Input:

First line consists of Q queries.

Each line follows and consists of four space separated values:

Type 1: It is of the form 1 m x p

1 is the type no,"m" is the child to which "x" toffees of a brand "p" are given

Type 2: It is of the form 2 m n p
where m - n is the range of children (inclusive) being queried for brand p

Output:

Report the sum of toffees of brand p within the given range m - n for each query of type 2

Constraints:

1 <= Q <= 10^5

1 <= N <= 10^6

1 <= m <= n <= 10^6

1 <= x <= 10^6

all brand of toffees are lowercase letters

Subtask 1: (30 points)

1 <= Q <= 10^3

1 <= m <= n <= 10^3

1 <= x <= 10^3

Subtask 2: (70 points)

Original Constraints

Sample Input:

5

1 3 4 a

1 5 8 a

1 1 7 x

2 1 6 a

2 3 6 y

Sample Output:

12

0

In first case, there are two children between 3 and 5 between 0 - 6  having sum (4 + 8)

There's no toffee for y in given range

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'N=10**3+1\nt=eval(input())\ninp = ()\nbag=[[0 for j in range(ord(\'z\'))] for i in range(N+1)]\n#print bag\nwhile t:\n t-=1\n inp=input().split()\n if inp[0]=="1":\n  #print "enter"\n  bag[int(inp[1])][ord(inp[3])-ord(\'a\')]+=int(inp[2])\n\n\n if inp[0]=="2":\n  sum=0\n  for i in range(int(inp[1]),int(inp[2])+1):\n   sum+=bag[i][ord(inp[3])-ord(\'a\')]\n  print(sum)\n\n#\n# for j in range(ord(\'z\')-ord(\'a\')):\n#     for i in range(N+1):\n#         if bag[i][j]!=0:\n#             print bag[i][j] ,i,j\n\n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 1097799