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

Difficulty: HARD
Tags: Constructive algorithms

Geometry

Sorting

Range queries

Complete search

Mathematics

Data structures

Ad-hoc
Skill types: Sorting

Data structures

Range queries

Complete search

Starter code:

Solutions:
from time import time
from bisect import bisect_left as bl, bisect_right as br
(n, m) = map(int, input().split())
c = []
(x, y) = ([], [])
for i in range(n):
	loc = list(map(int, input().split()))
	x.append(loc[0])
	y.append(loc[1])
x.sort()
y.sort()
(sx, sy) = ([], [])
(sx1, sy1) = (0, 0)
for i in range(n):
	sx1 += x[i]
	sy1 += y[i]
	sx.append(sx1)
	sy.append(sy1)
(lx, ly) = (0, 0)
s = list(input())
d = {}
for s1 in s:
	dist = 0
	move = {'R': (lx + 1, ly), 'L': (lx - 1, ly), 'U': (lx, ly + 1), 'D': (lx, ly - 1)}
	(lx, ly) = move[s1]
	try:
		dist = d[str([lx, ly])]
	except:
		(ix, iy) = (bl(x, lx), bl(y, ly))
		xs1 = sx[ix - 1] if ix - 1 >= 0 else 0
		ys1 = sy[iy - 1] if iy - 1 >= 0 else 0
		(xs2, ys2) = (sx[-1] - xs1, sy[-1] - ys1)
		dist = ix * lx - xs1 + (xs2 - (n - ix) * lx) + (iy * ly - ys1) + (ys2 - (n - iy) * ly)
		d[str([lx, ly])] = dist
	print(dist)


from sys import stdin, stdout
(a, b) = list(map(int, stdin.readline().split()))
left = []
top = []
for i in range(a):
	(c, d) = list(map(int, stdin.readline().split()))
	left.append(c)
	top.append(d)
left.sort()
top.sort()
from bisect import bisect_right as br
from bisect import bisect_left as bl
row = 0
col = 0
total = 0
cons_x = 0
cons_y = 0
for i in range(len(left)):
	cons_x += abs(left[i])
	cons_y += abs(top[i])
total = cons_x + cons_y
cc = stdin.readline().rstrip()
for i in cc:
	if i == 'R':
		kk = br(left, col)
		cons_x = cons_x + kk - (a - kk)
		col += 1
	if i == 'L':
		kk = bl(left, col)
		cons_x = cons_x + (a - kk) - kk
		col -= 1
	if i == 'U':
		kk = br(top, row)
		cons_y = cons_y + kk - (a - kk)
		row += 1
	if i == 'D':
		kk = bl(top, row)
		cons_y = cons_y + (a - kk) - kk
		row -= 1
	stdout.write(str(cons_x + cons_y))
	stdout.write('\n')