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: interview

Starter code:

Solutions:
import sys
import os
import random
import math
#nonlocal defs
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))

import sys
import os
import random
import math
#nonlocal defs
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 chefbm(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(chefbm(a,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 list(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 = 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])




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))

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)


#!/usr/bin/env python2
# -*- coding: utf-8 -*-

## Codechef May Challenge 2014
## Chef and Strange Matrix

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


def main(N, M, P, tab):
 """Evolved solution"""
 # make a dictionnary with rows and cols increased
 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]

 # move along each row
 for i in range(N):
  sol = M-1
  if i in dtab:
   line = sorted(dtab[i])
   # only the first and the last col give points
   sol += line.count(M-1) - line.count(0)
   # check for unsolvable cases
   prev = -1 # don't repeat k
   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())) # rows, cols, increasing cmds
 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


#print mn
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:   # Strictly correct.
    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 start != end:
  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)
  #else:
   #print mn[start]+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:
  #Logic
  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
  #print o
  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

inp = input().split()

row_n,col_m,operation_p = int(inp[0]),int(inp[1]),int(inp[2])

operations = []

#---------------Getting 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:
  #Logic
  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
  #print o
  for e in o:
   if o[e]>1:
    # print "O[e] > 1"
    if e+1<=col_m:
     # print("e+1 <= col_m")
     if e+1 in o:
      #print "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

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 list(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))


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
 # print(sorted(incs[i]))
 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
  else:
   if 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
 else:
  if 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
   else:
    if 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
 else:
  if 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())))
 #print "l = ",l
 #print "d = ",d
 for i in range(len(l)):
  #print "ans = ",ans
  number = l[i]
  if number > 1:
   below = number - 1
  else:
   if 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
  else:
   if 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]))



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
 else:
  if 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())))
 #print "l = ",l
 #print "d = ",d
 for i in range(len(l)):
  #print "ans = ",ans
  number = l[i]
  if number > 1:
   below = number - 1
  else:
   if 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
  else:
   if 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]))
'''for i in xrange(1,n+1):
    flag = True
    if i not in d:
     print m-1
    else:
     s = 0
     temp = m
     first = temp + d[i].count(temp)
     while temp > 1:
      second = (temp-1) + d[i].count(temp-1)
      #print d[i]
      if first >= second:
       s += first-second
       first = second
       #print "s = ",s
      else:
       flag = False
       break
      temp -= 1
     if flag:
      print s
     else:
      print -1
   
      '''