Today, puppy Tuzik is going to a new dog cinema. He has already left his home and just realised that he forgot his dog-collar! This is a real problem because the city is filled with catchers looking for stray dogs.
A city where Tuzik lives in can be considered as an infinite grid, where each cell has exactly four neighbouring cells: those sharing a common side with the cell. Such a property of the city leads to the fact, that the distance between cells (xA, yA) and (xB, yB) equals |xA - xB| + |yA - yB|.
Initially, the puppy started at the cell with coordinates (0, 0). There are N dog-catchers located at the cells with the coordinates (xi, yi), where 1 ≤ i ≤ N. Tuzik's path can be described as a string S of M characters, each of which belongs to the set {'D', 'U', 'L', 'R'} (corresponding to it moving down, up, left, and right, respectively). To estimate his level of safety, Tuzik wants to know the sum of the distances from each cell on his path to all the dog-catchers. You don't need to output this sum for the staring cell of the path (i.e. the cell with the coordinates (0, 0)).

-----Input-----
The first line of the input contains two integers N and M.
The following N lines contain two integers xi and yi each, describing coordinates of the dog-catchers.
The last line of the input contains string S of M characters on the set {'D', 'U', 'L', 'R'}.
- 'D' - decrease y by 1
- 'U' - increase y by 1
- 'L' - decrease x by 1
- 'R' - increase x by 1

-----Output-----
Output M lines: for each cell of the path (except the starting cell), output the required sum of the distances.

-----Constraints-----
- 1 ≤ N ≤ 3 ✕ 105
- 1 ≤ M ≤ 3 ✕ 105
- -106 ≤ xi, yi ≤ 106

-----Example-----
Input:
2 3
1 2
0 1
RDL

Output:
4
6
6

-----Explanation-----

Initially Tuzik stays at cell (0, 0). Let's consider his path:

- Move 'R' to the cell (1, 0). Distance to the catcher (1, 2) equals 2, distance to the catcher (0, 1) equals 2, so the total distance equals 4
- Move 'D' to the cell (1, -1). Distance to the catcher (1, 2) equals 3, distance to the catcher (0, 1) equals 3, so the total distance equals 6
- Move 'L' to the cell (0, -1). Distance to the catcher (1, 2) equals 4, distance to the catcher (0, 1) equals 2, so the total distance equals 6

```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 = '# cook your dish here\nfrom sys import stdin,stdout\na,b=list(map(int,stdin.readline().split()))\nleft=[]\ntop=[]\nfor i in range(a):\n c,d=list(map(int,stdin.readline().split()))\n left.append(c)\n top.append(d)\nleft.sort()\ntop.sort()\nfrom bisect import bisect_right as br\nfrom bisect import bisect_left as bl\nrow=0\ncol=0\ntotal=0\ncons_x=0\ncons_y=0\nfor i in range(len(left)):\n cons_x+=(abs(left[i]))\n cons_y+=(abs(top[i]))\ntotal=cons_x+cons_y\ncc=stdin.readline().rstrip()\nfor i in cc:\n if i=="R":\n  kk=br(left,col)\n  cons_x=(cons_x+kk-(a-kk))\n  col+=1\n if i=="L":\n  kk=bl(left,col)\n  cons_x=(cons_x+(a-kk)-kk)\n  col-=1\n if i=="U":\n  kk=br(top,row)\n  cons_y=(cons_y+kk-(a-kk))\n  row+=1\n if i=="D":\n  kk=bl(top,row)\n  cons_y=(cons_y+(a-kk)-kk)\n  row-=1\n stdout.write(str(cons_x+cons_y))\n stdout.write("\\n")\n  \n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13863