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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\n\nn,m,p = list(map(int,sys.stdin.readline().split()))\n\nd1 = {}\n\nfor i in range(p):\n i,j = list(map(int,sys.stdin.readline().split()))\n if i not in d1:\n  d1[i] = {}\n  d1[i][j] = 1\n else:\n  if j not in d1[i]:\n   d1[i][j] = 1\n  else:\n   d1[i][j] += 1\n\ndef matrix(n,m,d):\n ans = m-1\n l = list(reversed(sorted(d.keys())))\n #print "l = ",l\n #print "d = ",d\n for i in range(len(l)):\n  #print "ans = ",ans\n  number = l[i]\n  if number > 1:\n   below = number - 1\n  else:\n   if len(l) == 1:\n    if d[1] > 1:\n     return -1\n    else:\n     return m-2\n   else:\n    value = 1 + d[1]\n    if 2 not in d:\n     if 2-value >= 0:\n      ans += 2 - value - 1\n     else:\n      return -1\n    return ans\n  if number < m:\n   above = number + 1\n  else:\n   if len(l) == 1:\n    return ((m+d[m])-(m-1)-1)+ans\n   else:\n    if m-1 not in d:\n     ans += (m+d[m])-(m-1)-1\n    else:\n     below = (m-1)+d[below]\n     value = m+d[m]\n     if value - below < 0:\n      return -1\n     else:\n      ans += value-(below) - 1\n    continue\n  value = number + d[number]\n  if below in d:\n   initial = below + d[below]\n  else:\n   initial = below\n  if above in d:\n   final = above + d[above]\n  else:\n   final = above\n  if value - initial >= 0:\n   ans += value - initial - 1\n  else:\n   return -1\n  if len(l)==1:\n   if final - value >= 0:\n    ans += final - value - 1\n   else:\n    return -1\n  elif number+1 != l[i-1]:\n   if final - value >= 0:\n    ans += final - value - 1\n   else:\n    return -1\n \n return ans \n\n\nfor i in range(1,n+1):\n if m == 1:\n  print(0)\n elif i not in d1:\n  print(m-1)\n else:\n  print(matrix(n,m,d1[i]))\n\'\'\'for i in xrange(1,n+1):\n    flag = True\n    if i not in d:\n     print m-1\n    else:\n     s = 0\n     temp = m\n     first = temp + d[i].count(temp)\n     while temp > 1:\n      second = (temp-1) + d[i].count(temp-1)\n      #print d[i]\n      if first >= second:\n       s += first-second\n       first = second\n       #print "s = ",s\n      else:\n       flag = False\n       break\n      temp -= 1\n     if flag:\n      print s\n     else:\n      print -1\n   \n      \'\'\'\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13423