Read problems statements in Mandarin Chinese  and Russian. 

Yesterday Chef had a great party and doesn't remember the way he celebreated it. But he found a strange paper in his kitchen containing n digits (lets give them indices from 1 to n and name them a_{1}, a_{2} ... a_{N}). 
Chef remembers that he played such game:
On each step he choose an index x from 1 to n.
For all indices y (y < x) he calculated the difference b_{y} = a_{x} - a_{y}. 
Then he calculated B1 - sum of all b_{y} which are greater than 0 and B2 - sum of all b_{y} which are less than 0. 
The answer for this step is B1 - B2. 

Chef remembers the game, but forgot the answer. Please, help him!

------ Input ------ 

The first line contains two integers n, m denoting the number of digits and number of steps. The second line contains n digits (without spaces) a_{1}, a_{2}, ..., a_{n}. 
Each of next m lines contains single integer x denoting the index for current step. 
 
------ Output ------ 

For each of m steps print single number in a line - answer of the step.
 
------ Constraints ------ 

$1 ≤ n, m ≤ 10^{5}$
$0 ≤ a_{i} ≤ 9$
$1 ≤ x ≤ n$
 
----- Sample Input 1 ------ 
10 3
0324152397
1
4
7
----- Sample Output 1 ------ 
0
7
9
----- explanation 1 ------ 
For index 1 there are no indexes which are less, so B1 = B2 = 0 and the answer is 0.
For index 4 we have 

b1 = 4-0=4, 
b2 = 4-3=1, 
b3 = 4-2=2, 

so B1 = 4+1+2 = 7, B2 = 0 
and the answer is 7.
For index 7 we have

b1 = 2-0=2, 
b2 = 2-3=-1, 
b3 = 2-2=0, 
b4 = 2-4=-2, 
b5 = 2-1=1, 
b6 = 2-5=-3, 

so B1 = 2 + 1 = 3,
B2 = -1 -2 -3 = -6 
and the answer is 9.

Difficulty: MEDIUM_HARD
Tags: Preprocessing

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
(n, m) = map(int, input().split())
cnt = [0] * 10
ans = [0] * n
s = map(int, input().strip())
for (index, i) in enumerate(s):
	b1 = 0
	b2 = 0
	for j in range(10):
		if j > i:
			b2 += cnt[j] * (i - j)
		elif i > j:
			b1 += cnt[j] * (i - j)
	cnt[i] += 1
	ans[index] += b1 - b2
for _ in range(m):
	print(ans[int(input()) - 1])


(N, M) = [int(x) for x in input().split()]
S = input()
answer = [None] * N
count = [0] * 10
for i in range(N):
	c = S[i]
	c = ord(c) - ord('0')
	value = 0
	for j in range(c):
		value += (c - j) * count[j]
	for j in range(c + 1, 10):
		value += (j - c) * count[j]
	count[c] += 1
	answer[i] = value
for _ in range(M):
	x = int(input())
	print(answer[x - 1])


import sys
from collections import defaultdict

def main():
	print(*solve(sys.stdin), sep='\n')

def solve(lines):
	(_, digits, *indices) = lines
	return calculate_answer(as_ints(digits.rstrip()), as_ints(indices))

def calculate_answer(digits, indices):
	result = dict.fromkeys(indices)
	counts = defaultdict(int)
	for (index, digit) in enumerate(digits, start=1):
		if result.get(index, False) is None:
			result[index] = sum((n * abs(digit - d) for (d, n) in counts.items()))
		counts[digit] += 1
	return (result[i] for i in indices)

def as_ints(iterable):
	return [int(x) for x in iterable]
main()


(n, m) = map(int, input().split())
la = list(map(int, list(input().strip())))
l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
hash_count = {}
hash_bool = {}
for i in l:
	hash_bool[i] = False
	hash_count[i] = 0
ans = {}
for (x, i) in enumerate(la):
	if x == 0:
		ans[x] = 0
	else:
		(count1, sum1) = (0, 0)
		(count2, sum2) = (0, 0)
		for j in l:
			if hash_bool[j] == True:
				if i >= j:
					count1 += hash_count[j]
					sum1 += j * hash_count[j]
				else:
					count2 += hash_count[j]
					sum2 += j * hash_count[j]
		count1 = count1 * i - sum1
		count2 = -1 * abs(count2 * i - sum2)
		ans[x] = count1 - count2
	hash_count[i] += 1
	hash_bool[i] = True
for i in range(m):
	a = int(input()) - 1
	print(ans[a])


import sys
from math import gcd, sqrt, log10, log2, floor, ceil
from collections import deque, defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
(n, m) = il()
s = ip()
arr = []
darr = []
d = {}
for l in s:
	if l in d:
		d[l] += 1
	else:
		d[l] = 1
	darr.append(d.copy())
for _ in rg(m):
	x = ii()
	if x == 1:
		ot(0)
	else:
		sum = 0
		for k in darr[x - 2]:
			sum = sum + abs(int(k) - int(s[x - 1])) * darr[x - 2][k]
		ot(sum)


def solve(a):
	ans = 0
	ele = int(lst[a])
	for i in range(10):
		ans += dp[a][i] * abs(ele - i)
	print(ans)
for _ in range(1):
	(n, m) = list(map(int, input().split()))
	lst = input()
	dp = [[0 for i in range(10)] for j in range(n)]
	for i in range(1, n):
		ele = int(lst[i - 1])
		for j in range(10):
			if ele == j:
				dp[i][j] = dp[i - 1][j] + 1
			else:
				dp[i][j] = dp[i - 1][j]
	for i in range(m):
		a = int(input())
		solve(a - 1)


from collections import Counter
temp = input().split()
n = int(temp[0])
m = int(temp[1])
a = input()
ans = [0] * n
f = [0] * 10
step = 0
for i in range(n):
	cur = int(a[i])
	f[cur] += 1
	(b1, b2) = (0, 0)
	sum = 0
	for y in range(10):
		sum += abs(cur - y) * f[y]
	ans[i] = sum
for j in range(m):
	print(ans[int(input()) - 1])


(n, m) = map(int, input().split())
s = input()
freq = [0] * 10
B = [0] * n
for i in range(0, n):
	t = int(s[i])
	freq[t] += 1
	for j in range(0, 10):
		B[i] += freq[j] * abs(t - j)
for i in range(0, m):
	x = int(input())
	print(B[x - 1])


def solve(a):
	ans = 0
	e = int(s[a])
	for u in range(10):
		ans += d[a][u] * abs(e - u)
	print(ans)
(n, m) = list(map(int, input().split()))
s = input()
d = [[0 for x in range(10)] for y in range(n)]
for j in range(1, n):
	e = int(s[j - 1])
	for k in range(10):
		if e == k:
			d[j][k] = d[j - 1][k] + 1
		else:
			d[j][k] = d[j - 1][k]
for z in range(m):
	a = int(input())
	solve(a - 1)


temp = list(map(int, input().split()))
n = temp[0]
m = temp[1]
a = input()
a = a.strip()
b = []
for i in a:
	b.append(int(i))
b1 = []
b2 = []
for i in range(10):
	b1.append([])
	b2.append([])
for i in range(10):
	for j in range(n):
		b1[i].append(0)
		b2[i].append(0)
for i in range(10):
	val = i - b[0]
	if val < 0:
		b2[i][0] = val
	else:
		b1[i][0] = val
	for j in range(1, n):
		val = i - b[j]
		if val < 0:
			b2[i][j] += val + b2[i][j - 1]
			b1[i][j] = b1[i][j - 1]
		else:
			b1[i][j] += val + b1[i][j - 1]
			b2[i][j] = b2[i][j - 1]
for i in range(m):
	index = int(input())
	index -= 1
	x = b[index]
	print(b1[x][index] - b2[x][index])


(n, q) = map(int, input().split())
s = input()
dp = [0] * 10
ans = [0] * n
for i in range(n):
	cur_ele = int(s[i])
	dp[cur_ele] += 1
	(b1, b2) = (int(), int())
	for j in range(10):
		if j > cur_ele:
			val = cur_ele - j
			val *= dp[j]
			b2 += val
		else:
			val = cur_ele - j
			val *= dp[j]
			b1 += val
	ans[i] = b1 - b2
for _ in range(q):
	print(ans[int(input()) - 1])


def compute(val, dp, arr):
	ans = 0
	for i in range(10):
		ans += abs(arr[val - 1] - i) * dp[val - 1][i]
	print(ans)
(n, m) = list(map(int, input().split()))
s = input()
arr = []
for i in range(n):
	arr.append(int(s[i]))
dp = [[0 for i in range(10)] for i in range(n)]
for i in range(1, n):
	val = int(arr[i - 1])
	for k in range(10):
		if k == val:
			dp[i][k] = dp[i - 1][k] + 1
		else:
			dp[i][k] = dp[i - 1][k]
for i in range(m):
	val = int(input())
	compute(val, dp, arr)


(n, m) = map(int, input().split())
a = input()
A = [[0 for j in range(n)] for i in range(10)]
A[int(a[0])][0] = 1
for i in range(10):
	for j in range(1, n):
		A[i][j] = A[i][j - 1]
		if int(a[j]) == i:
			A[i][j] += 1
for _ in range(m):
	x = int(input())
	d = int(a[x - 1])
	if x == 1:
		print(0)
		continue
	B1 = 0
	B2 = 0
	for i in range(0, d):
		B1 += A[i][x - 2] * (d - i)
	for i in range(d + 1, 10):
		B2 += A[i][x - 2] * (d - i)
	print(B1 - B2)


[n, m] = [int(i) for i in input().split()]
s = input()
arr = []
for p in range(10):
	temp = []
	total = 0
	for q in range(n):
		total += abs(p - int(s[q]))
		temp.append(total)
	arr.append(temp)
for t in range(m):
	x = int(input())
	if x == 1:
		print(0)
	else:
		print(arr[int(s[x - 1])][x - 2])


(nums, cases) = map(int, input().split())
inpL = list(map(int, list(input().strip())))
popn = [[] for i in range(10)]
for n in range(10):
	myBin = 0
	for j in inpL:
		myBin += abs(int(j) - n)
		popn[n] += [myBin]
for c in range(cases):
	q = int(input())
	queried = inpL[q - 1]
	print(popn[int(queried)][q - 1])


(n, m) = map(int, input().split())
s = input().strip()
arr = [int(i) for i in s]
part = [[0] * 10]
part[0][arr[0]] += 1
for i in range(1, n):
	part.append(part[-1][:])
	part[-1][arr[i]] += 1
for _ in range(m):
	tot = 0
	i = int(input()) - 1
	for j in range(10):
		tot += abs(arr[i] - j) * part[i][j]
	print(tot)


import sys
from collections import defaultdict

def main():
	print(*solve(sys.stdin), sep='\n')

def solve(lines):
	next(lines)
	digits = as_ints(next(lines).rstrip())
	indices = as_ints(lines)
	return calculate_answer(digits, indices)

def calculate_answer(digits, indices):
	result = dict.fromkeys(indices)
	counts = defaultdict(int)
	todo = len(result)
	for (index, digit) in enumerate(digits, start=1):
		if index in result:
			if not result[index]:
				result[index] = sum((count * abs(digit - d) for (d, count) in counts.items()))
			todo -= 1
			if not todo:
				return (result[i] for i in indices)
		counts[digit] += 1

def as_ints(seq):
	return [int(x) for x in seq]
main()


(n, m) = list(map(int, input().split()))
a = input()
l = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
l[int(a[0])] += 1
sums = [0] * n
for i in range(1, n):
	s = 0
	num = int(a[i])
	for j in range(10):
		s += l[j] * abs(num - j)
	sums[i] = s
	l[num] += 1
for _ in range(m):
	x = int(input())
	print(sums[x - 1])


(n, m) = map(int, input().split())
a = list(map(int, list(input().strip())))
s = [[] for i in range(10)]
for i in range(10):
	temp = 0
	for j in a:
		temp += abs(int(j) - i)
		s[i] += [temp]
for i in range(m):
	ind = int(input())
	ind1 = a[ind - 1]
	print(s[int(ind1)][ind - 1])


from itertools import repeat
import numpy as np
(n, m) = map(int, input().split())
a = input()
digit_count = np.zeros((n, 10))
for i in range(n):
	if i > 0:
		digit_count[i] = digit_count[i - 1]
	digit_count[i, int(a[i])] += 1
for _ in repeat(None, m):
	x = int(input())
	B = 0
	for i in range(10):
		B += digit_count[x - 1, i] * abs(int(a[x - 1]) - i)
	print(int(B))


(n, m) = map(int, input().split())
d = list(map(int, list(input().strip())))
a = [0 for _ in range(10)]
abig = []
for i in range(n):
	a[d[i]] += 1
	abig.append(a[:])
for _ in range(m):
	x = int(input()) - 1
	ans = 0
	for i in range(10):
		ans += abs(d[x] - i) * abig[x][i]
	print(ans)


(n, m) = map(int, input().split())
a = input()
ans = [0] * n
f = [0] * 10
for i in range(n):
	cur = int(a[i])
	f[cur] += 1
	sum = 0
	for y in range(10):
		sum += abs(cur - y) * f[y]
	ans[i] = sum
for j in range(m):
	print(ans[int(input()) - 1])


(n, m) = map(int, input().split())
s = input()
t = []
p = []
temp = [0] * 10
for i in range(n):
	temp[int(s[i])] += 1
	p = temp.copy()
	t.append(p)
for i in range(m):
	a = int(input()) - 1
	b = int(s[a])
	ans = 0
	for k in range(10):
		if t[a][k] > 0:
			ans += abs(b - k) * t[a][k]
	print(ans)


import sys
from collections import defaultdict

def main():
	print(*solve(sys.stdin), sep='\n')

def solve(lines):
	(_, digits, *indices) = lines
	return calculate_answer(as_ints(digits.rstrip()), as_ints(indices))

def calculate_answer(digits, indices):
	unique = set(indices)
	result = {}
	counts = defaultdict(int)
	for (index, digit) in enumerate(digits, start=1):
		if index in unique and index not in result:
			result[index] = sum((n * abs(digit - d) for (d, n) in counts.items()))
			if len(result) == len(unique):
				return (result[i] for i in indices)
		counts[digit] += 1

def as_ints(iterable):
	return [int(x) for x in iterable]
main()


import sys
from itertools import islice
from collections import defaultdict

def main():
	print(*solve(sys.stdin), sep='\n')

def solve(lines):
	(length, steps) = as_ints(next(lines).split())
	digits = as_ints(next(lines)[:length])
	indices = as_ints(islice(lines, steps))
	return calculate_answer(digits, indices)

def calculate_answer(digits, indices):
	result = dict.fromkeys(indices)
	sums = defaultdict(int)
	for (index, digit) in enumerate(digits, start=1):
		if result.get(index, False) is None:
			result[index] = sum((n * abs(digit - d) for (d, n) in sums.items()))
		sums[digit] += 1
	return (result[i] for i in indices)

def as_ints(seq):
	return [int(x) for x in seq]
main()


(n, m) = map(int, input().split())
s = input().strip()
l = [int(i) for i in s]
d = [0] * 10
ans = [0] * (n + 193)
for i in range(n):
	curr = l[i]
	less = 0
	big = 0
	c1 = 0
	c2 = 0
	for j in range(10):
		if j < curr:
			c1 += d[j]
			less += d[j] * j
		if j > curr:
			c2 += d[j]
			big += d[j] * j
	ans[i] = big - less + curr * (c1 - c2)
	d[l[i]] += 1
for _ in range(m):
	x = int(input())
	print(ans[x - 1])


import sys

def main():
	print(*solve(sys.stdin), sep='\n')

def solve(lines):
	(_, digits, *indices) = lines
	return calculate_answer(as_ints(digits.rstrip()), as_ints(indices))

def calculate_answer(digits, indices):
	result = dict.fromkeys(indices)
	counts = [0] * 10
	for (index, digit) in enumerate(digits, start=1):
		if index in result and result[index] is None:
			result[index] = sum((n * abs(digit - d) for (d, n) in enumerate(counts)))
		counts[digit] += 1
	return (result[i] for i in indices)

def as_ints(iterable):
	return [int(x) for x in iterable]
main()


def soln(n, m, arr):
	mem = [0] * n
	freq = [0] * 10
	for i in range(n):
		freq[arr[i]] += 1
		for j in range(10):
			mem[i] += abs(arr[i] - j) * freq[j]
	return mem
(n, m) = map(int, input().split())
arr = input()
mem = [0] * n
freq = [0] * 10
for i in range(n):
	cur = int(arr[i])
	freq[cur] += 1
	for j in range(10):
		mem[i] += abs(cur - j) * freq[j]
for i in range(m):
	print(mem[int(input()) - 1])


from collections import Counter
temp = input().split()
n = int(temp[0])
m = int(temp[1])
a = input()
ans = [0] * n
f = [0] * 10
step = 0
for i in range(n):
	cur = int(a[i])
	f[cur] += 1
	(b1, b2) = (0, 0)
	for y in range(10):
		val = cur - y
		val *= f[y]
		if y > cur:
			b2 += val
		else:
			b1 += val
	ans[i] = b1 - b2
for j in range(m):
	print(ans[int(input()) - 1])