Read problems statements in Mandarin Chinese  and Russian. 
Spring is interesting season of year. Chef is thinking about different things, but last time he thinks about interesting game - "Strange Matrix". 
Chef has a matrix that consists of n rows, each contains m elements. Initially, the element a_{i}_{j} of matrix equals j. (1 ≤ i ≤ n, 1 ≤ j ≤ m). 
Then p times some element a_{i}_{j} is increased by 1. 
Then Chef needs to calculate the following: 
For each row he tries to move from the last element (with number m) to the first one (with the number 1). 
While staying in a_{i}_{j} Chef can only move to a_{i}_{j - 1} only if a_{i}_{j - 1} ≤ a_{i}_{j}. 
The cost of such a movement is a_{i}_{j} - a_{i}_{j - 1}.
Otherwise Chef can't move and lose (in this row).
If Chef can move from the last element of the row to the first one, then the answer is the total cost of all the movements. 
If Chef can't move from the last element of the row to the first one, then the answer is -1. 
Help Chef to find answers for all the rows after P commands of increasing. 

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

The first line contains three integers n, m and p denoting the number of rows, the number of elements a single row and the number of increasing commands. 
Each of next p lines contains two integers i and j denoting that the element a_{i}_{j } is increased by one. 

------ Output ------ 

For each row in a single line print the answer after the P increasing commands.
 
------ Constraints ------ 

$1 ≤ n, m, p ≤ 10 ^ 5$
$1 ≤ i ≤ n$
$1 ≤ j ≤ m$

----- Sample Input 1 ------ 
4 4 6
2 2
3 2 
3 2 
4 3
4 4
4 3
----- Sample Output 1 ------ 
3
3
-1
4
----- explanation 1 ------ 

Here is the whole matrix after P commands:
1 2 3 4
1 3 3 4
1 4 3 4
1 2 5 5
Explanations to the answer: 
The first line is without changes: 4-3=1, 3-2=1, 2-1=1. answer = 3. 
The second line: 4-3=1, 3-3=0, 3-1=2. The answer is 3. 
The third line: 4-3=1, 3-4=-1, Chef can't move to the first number here. Therefore, the answer is -1. 
The fourth line: 5-5=0, 5-2=3, 2-1=1. The answer is 4.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc


Solutions:
def solve():
	(n, m, p) = (int(x) for x in input().split())
	scores = [m - 1 for x in range(n)]
	coord = dict()
	if m == 1:
		return scores
	for __ in range(p):
		(i, j) = (int(x) for x in input().split())
		if j == m:
			scores[i - 1] += 1
		elif j == 1:
			scores[i - 1] -= 1
		pair = (i, j)
		if pair not in coord:
			coord[pair] = 1
		else:
			coord[pair] += 1
	for (i, j) in coord:
		if j != m:
			condition = coord.get((i, j)) - coord.get((i, j + 1), 0) > 1
			if condition:
				scores[i - 1] = -1
	return scores
ans = solve()
print(*ans, sep='\n')


(n, m, p) = map(int, input().split())
s = [(n + 1, 0)]
for i in range(p):
	z = input().split()
	s.append((int(z[0]), int(z[1])))
s.sort()
x = 0
for j in range(1, n + 1):
	f = False
	t = 1
	e = m
	l = 0
	c1 = 0
	c2 = 0
	while s[x][0] == j:
		c3 = s[x][1]
		if m > 1 and (not f):
			if c3 > c2:
				f = l > c1 + 1 or (c1 > 1 and c3 > c2 + 1)
				c2 = c3
				l = c1
				c1 = 0
			c1 += 1
			if c2 == 1:
				t += 1
			elif c2 == m:
				e += 1
		x += 1
	if l > c1 + 1 or (c1 > 1 and c2 < m):
		f = True
	print(-1 if f else e - t)


line1 = input().split(' ')
n = int(line1[0])
m = int(line1[1])
p = int(line1[2])
mat = {}
while p > 0:
	p -= 1
	line1 = input().split(' ')
	x = int(line1[0])
	y = int(line1[1])
	if x in mat:
		if y in mat[x]:
			mat[x][y] = mat[x][y] + 1
		else:
			mat[x][y] = 1
	else:
		mat[x] = {}
		mat[x][y] = 1
for i in range(n):
	x = i + 1
	if x in mat:
		tempAns = 0
		lastItem = -1
		lastI = m
		if m not in mat[x]:
			lastItem = m
		for item in sorted(mat[x].keys(), reverse=True):
			if lastItem != -1 and (lastItem < mat[x][item] + item or (lastI != item + 1 and mat[x][item] > 1)):
				tempAns = -1
				break
			else:
				if lastItem != -1:
					tempAns += lastItem - (mat[x][item] + item)
				lastItem = mat[x][item] + item
				lastI = item
		if 1 not in mat[x] and tempAns != -1:
			tempAns += lastItem - 1
		print(tempAns)
	else:
		print(m - 1)


(n, m, p) = map(int, input().split())
incs = [(n + 1, 0)]
for _ in range(p):
	z = input().split()
	incs.append((int(z[0]), int(z[1])))
incs.sort()
inx = 0
for nx in range(1, n + 1):
	fail = False
	st = 1
	en = m
	last = 0
	curr = 0
	ccol = 0
	while incs[inx][0] == nx:
		ncol = incs[inx][1]
		if m > 1 and (not fail):
			if ncol > ccol:
				fail = last > curr + 1 or (curr > 1 and ncol > ccol + 1)
				ccol = ncol
				last = curr
				curr = 0
			curr += 1
			if ccol == 1:
				st += 1
			elif ccol == m:
				en += 1
		inx += 1
	if last > curr + 1 or (curr > 1 and ccol < m):
		fail = True
	print(-1 if fail else en - st)


import collections as c, sys
(N, M, P) = list(map(int, sys.stdin.readline().split()))
A = c.defaultdict(lambda : c.defaultdict(int))
for _ in range(P):
	(i, j) = list(map(int, sys.stdin.readline().split()))
	if j - 1 in A[i - 1]:
		A[i - 1][j - 1] += 1
	else:
		A[i - 1][j - 1] = j
for i in range(N):
	for (j, v) in A[i].items():
		if j == M - 1:
			continue
		x = A[i][j + 1] if j + 1 in A[i] else j + 1
		if A[i][j] > x:
			print(-1)
			break
	else:
		x = A[i][M - 1] if M - 1 in A[i] else M - 1
		print(x - A[i][0])