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 aij of matrix equals j. (1 ≤ i ≤ n, 1 ≤ j ≤ m). 
Then p times some element aij 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 aij Chef can only move to aij - 1 only if aij - 1 ≤ aij. 
- The cost of such a movement is aij - aij - 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 aij  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

-----Example-----
Input:
4 4 6
2 2
3 2 
3 2 
4 3
4 4
4 3

Output:
3
3
-1
4


-----Explanation-----

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.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
import os
import random
import math
(n, m, p) = list(map(int, input().split()))
arr = [dict() for _ in range(n)]
for _ in range(p):
	(i, j) = list(map(int, input().split()))
	i -= 1
	j -= 1
	if j not in arr[i]:
		arr[i][j] = j + 1
	else:
		arr[i][j] += 1

def chefbm(arr, i):
	for (e, f) in arr[i].items():
		if e == m - 1:
			continue
		if e + 1 in arr[i]:
			c = arr[i][e + 1]
		else:
			c = e + 1
		if arr[i][e] > c:
			return -1
	y = arr[i][m - 1] if m - 1 in arr[i] else m - 1
	x = arr[i][0] if 0 in arr[i] else 0
	return y - x
for i in range(n):
	print(chefbm(arr, i))


(N, M, P) = list(map(int, input().split()))
A = [dict() for _ in range(N)]
for _ in range(P):
	(i, j) = list(map(int, input().split()))
	i -= 1
	j -= 1
	if j not in A[i]:
		A[i][j] = j + 1
	else:
		A[i][j] += 1

def solve(A, i):
	for (k, v) in A[i].items():
		if k == M - 1:
			continue
		if k + 1 in A[i]:
			c = A[i][k + 1]
		else:
			c = k + 1
		if A[i][k] > c:
			return -1
	y = A[i][M - 1] if M - 1 in A[i] else M - 1
	x = A[i][0] if 0 in A[i] else 0
	return y - x
for i in range(N):
	print(solve(A, i))


(n, m, p) = (int(e) for e in input().split())

def add(d, k):
	if k in d:
		d[k] += 1
	else:
		d[k] = 1

def get(d, k):
	if k in d:
		return d[k]
	else:
		return 0
dic2 = {}
dic = {}
sumd = {}
for i in range(n):
	dic[i] = []
	sumd[i] = m - 1
for i in range(p):
	(a, b) = (int(e) for e in input().split())
	if b == 1:
		sumd[a - 1] -= 1
	if b == m:
		sumd[a - 1] += 1
	add(dic2, (a - 1, b - 1))
	dic[a - 1].append(b - 1)
for i in range(n):
	if len(dic[i]) <= 1:
		print(sumd[i])
	else:
		arr = set(dic[i])
		flag = 0
		for e in arr:
			if e == m - 1 or get(dic2, (i, e)) - 1 <= get(dic2, (i, e + 1)):
				pass
			else:
				flag = 1
				break
		if flag == 1:
			print(-1)
		else:
			print(sumd[i])


from collections import defaultdict
(n, m, p) = list(map(int, input().split()))
c = [defaultdict(int) for _ in range(n + 1)]
for _ in range(p):
	(i, j) = list(map(int, input().split()))
	c[i][j] += 1
for i in range(1, n + 1):
	if not c[i]:
		print(m - 1)
	else:
		x = m + c[i].get(m, 0)
		v = list(c[i].items())
		v.sort(reverse=True)
		cost = 0
		last_col = m
		ok = True
		for (j, h) in v:
			cost += max(0, last_col - j - 1)
			if j < m:
				x = j + 1 + c[i].get(j + 1, 0)
				if x < j + h:
					ok = False
					break
			if j > 1:
				x = h + 1 - c[i].get(j - 1, 0)
				if x < 0:
					ok = False
					break
				cost += x
			last_col = j - 1
		if ok:
			print(cost + max(0, last_col - 1))
		else:
			print(-1)


try:
	import psyco
	psyco.full()
except ImportError:
	pass

def main(N, M, P, tab):
	dtab = dict()
	for (ii, jj) in tab:
		(i, j) = (ii - 1, jj - 1)
		if i in dtab:
			dtab[i].append(j)
		else:
			dtab[i] = [j]
	for i in range(N):
		sol = M - 1
		if i in dtab:
			line = sorted(dtab[i])
			sol += line.count(M - 1) - line.count(0)
			prev = -1
			for k in line:
				if k > prev and k < M - 1:
					inc_k = line.count(k)
					inc_kp = line.count(k + 1)
					if inc_k > inc_kp + 1:
						sol = -1
						break
					prev = k
		print(sol)

def __starting_point():
	(N, M, P) = list(map(int, input().split()))
	tab = [list(map(int, input().split())) for _ in range(P)]
	main(N, M, P, tab)
__starting_point()


def __starting_point():
	(n, m, p) = list(map(int, input().split()))
	hit = {}
	sums = {}
	for i in range(1, n + 1):
		hit[i] = {}
		sums[i] = m - 1
	for _ in range(p):
		(i, j) = list(map(int, input().split()))
		if j not in hit[i]:
			hit[i][j] = 1
		else:
			hit[i][j] += 1
	for i in range(1, n + 1):
		done = True
		for j in hit[i]:
			if j != m and hit[i][j] - hit[i].get(j + 1, 0) > 1:
				done = False
				break
			if j == 1 and m > 1:
				sums[i] -= hit[i][j]
			elif j == m and m > 1:
				sums[i] += hit[i][j]
		if done:
			print(sums[i])
		else:
			print(-1)
__starting_point()


(n, m, p) = list(map(int, input().split()))
mn = {}
for i in range(0, p):
	(x, y) = list(map(int, input().split()))
	key = (x, y)
	if key in mn:
		mn[key] += 1
	else:
		mn[key] = 1
ans = {}
for key in mn:
	cur = key
	next = (key[0], key[1] + 1)
	if next[1] <= m:
		if next in mn:
			if mn[cur] > mn[next] + 1:
				ans[cur[0]] = -1
		elif mn[cur] > 1:
			ans[cur[0]] = -1
for i in range(1, n + 1):
	if i in ans:
		print(-1)
	else:
		start = (i, 1)
		end = (i, m)
		if end in mn and start in mn:
			print(mn[end] - mn[start] + (m - 1))
		if end in mn and start not in mn:
			print(mn[end] + (m - 1))
		if end not in mn and start in mn:
			print(m - 1 - mn[start])
		if end not in mn and start not in mn:
			print(m - 1)


inp = input().split()
(row_n, col_m, operation_p) = (int(inp[0]), int(inp[1]), int(inp[2]))
operations = []
for i in range(operation_p):
	inp = input().split()
	(row, col) = (int(inp[0]), int(inp[1]))
	operations.append([row, col])
operations.sort()
i = 0
sol_index = 1
while i < operation_p:
	if operations[i][0] == sol_index:
		sol = col_m - 1
		o = {}
		while i < operation_p and operations[i][0] == sol_index:
			e = operations[i][1]
			if e in o:
				o[e] += 1
			else:
				o[e] = 1
			i += 1
		for e in o:
			if o[e] > 1:
				if e + 1 <= col_m:
					if e + 1 in o:
						if o[e] - o[e + 1] > 1:
							sol = -1
							break
					else:
						sol = -1
						break
		if sol != -1:
			if 1 in o:
				sol -= o[1]
			if col_m in o:
				sol += o[col_m]
		print(sol)
		sol_index += 1
	else:
		print(col_m - 1)
		sol_index += 1
while sol_index <= row_n:
	print(col_m - 1)
	sol_index += 1


import sys
__author__ = 'm.melnik'
(n, m, p) = [int(i) for i in sys.stdin.readline().split()]
incs = {i: [] for i in range(1, n + 1)}
for i in range(p):
	(x, y) = [int(i) for i in sys.stdin.readline().split()]
	incs[x].append(y)
for i in range(1, n + 1):
	cur = 1
	cost = 0
	height = cur
	prev_height = 0
	for j in sorted(incs[i]):
		if j == cur:
			height += 1
		elif j == cur + 1:
			if cur != 1:
				if height >= prev_height:
					cost += height - prev_height
				else:
					cost = -1
					break
			prev_height = height
			height = j + 1
			cur = j
		else:
			if cur != 1:
				if height >= prev_height:
					cost += height - prev_height
				else:
					cost = -1
					break
			if height > cur + 1:
				cost = -1
				break
			else:
				cost += j - height - 1
				cur = j
				height = j + 1
				prev_height = j - 1
	if cost != -1:
		if cur != m:
			if cur != 1:
				if height >= prev_height:
					cost += height - prev_height
				else:
					cost = -1
			if cost != -1:
				if height > cur + 1:
					cost = -1
				else:
					cost += m - height
		elif cur != 1:
			if height >= prev_height:
				cost += height - prev_height
			else:
				cost = -1
	print(cost)


import operator
(n, m, p) = list(map(int, input().split()))
a = []
for i in range(p):
	a.append(list(map(int, input().split())))
a.sort(key=operator.itemgetter(0, 1))
b = []
j = p - 1
for i in range(n, 0, -1):
	last = 200000
	now = 0
	k = m
	low = 1
	high = m
	while j >= 0 and a[j][0] == i:
		if a[j][1] == k:
			now += 1
			if now > last + 1:
				break
		elif a[j][1] == k - 1:
			k = a[j][1]
			last = now
			now = 1
		else:
			k = a[j][1]
			now = 1
			last = 0
		if a[j][1] == m:
			high = now + a[j][1]
		if a[j][1] == 1:
			low = now + a[j][1]
		j -= 1
	if now > last + 1:
		b.append(-1)
		while j >= 0 and a[j][0] == i:
			j -= 1
	else:
		b.append(high - low)
for i in range(n - 1, -1, -1):
	print(b[i])


from sys import stdout, stdin
from operator import itemgetter
(n, m, p) = list(map(int, stdin.readline().split()[0:3]))
increases = {}
for _ in range(p):
	(i, j) = list(map(int, stdin.readline().split()[0:2]))
	if not i in increases:
		increases[i] = {}
		increases[i][j] = 1
	elif j in increases[i]:
		increases[i][j] += 1
	else:
		increases[i][j] = 1
for row in range(1, n + 1, 1):
	base = m - 1
	if not row in increases or m == 1:
		print(base)
	else:
		keylist = list(increases[row].keys())
		keylist.sort()
		for key in keylist:
			if key == m:
				base += increases[row][key]
				continue
			if not key + 1 in increases[row]:
				if increases[row][key] >= 2:
					base = -1
					break
				if key == 1:
					base -= increases[row][key]
					continue
			elif increases[row][key] - increases[row][key + 1] >= 2:
				base = -1
				break
			else:
				if key == 1:
					base -= increases[row][key]
				continue
		print(base)


import sys
(n, m, p) = list(map(int, sys.stdin.readline().split()))
d1 = {}
for i in range(p):
	(i, j) = list(map(int, sys.stdin.readline().split()))
	if i not in d1:
		d1[i] = {}
		d1[i][j] = 1
	elif j not in d1[i]:
		d1[i][j] = 1
	else:
		d1[i][j] += 1

def matrix(n, m, d):
	ans = m - 1
	l = list(reversed(sorted(d.keys())))
	for i in range(len(l)):
		number = l[i]
		if number > 1:
			below = number - 1
		elif len(l) == 1:
			if d[1] > 1:
				return -1
			else:
				return m - 2
		else:
			value = 1 + d[1]
			if 2 not in d:
				if 2 - value >= 0:
					ans += 2 - value - 1
				else:
					return -1
			return ans
		if number < m:
			above = number + 1
		elif len(l) == 1:
			return m + d[m] - (m - 1) - 1 + ans
		else:
			if m - 1 not in d:
				ans += m + d[m] - (m - 1) - 1
			else:
				below = m - 1 + d[below]
				value = m + d[m]
				if value - below < 0:
					return -1
				else:
					ans += value - below - 1
			continue
		value = number + d[number]
		if below in d:
			initial = below + d[below]
		else:
			initial = below
		if above in d:
			final = above + d[above]
		else:
			final = above
		if value - initial >= 0:
			ans += value - initial - 1
		else:
			return -1
		if len(l) == 1:
			if final - value >= 0:
				ans += final - value - 1
			else:
				return -1
		elif number + 1 != l[i - 1]:
			if final - value >= 0:
				ans += final - value - 1
			else:
				return -1
	return ans
for i in range(1, n + 1):
	if m == 1:
		print(0)
	elif i not in d1:
		print(m - 1)
	else:
		print(matrix(n, m, d1[i]))