Puppy and Catchers

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Today, puppy Tuzik is going to a new dog cinema. He has already left his home and just realised that he forgot his dogcollar! 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 (x_{A}, y_{A}) and (x_{B}, y_{B}) equals x_{A}  x_{B} + y_{A}  y_{B}.
Initially, the puppy started at the cell with coordinates (0, 0). There are N dogcatchers located at the cells with the coordinates (x_{i}, y_{i}), 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 dogcatchers. 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 x_{i} and y_{i} each, describing coordinates of the dogcatchers.
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 ✕ 10^{5}
 1 ≤ M ≤ 3 ✕ 10^{5}
 10^{6} ≤ x_{i}, y_{i} ≤ 10^{6}
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
Author:  pavel1996 
Tester:  kostya_by 
Editorial  http://discuss.codechef.com/problems/PPCTS 
Tags  cook67, geometry, implementation, maths, pavel1996, sorting 
Date Added:  24012016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions