Chef and Strange Matrix

All submissions for this problem are available.
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
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 5Explanations to the answer:
 The first line is without changes: 43=1, 32=1, 21=1. answer = 3.
 The second line: 43=1, 33=0, 31=2. The answer is 3.
 The third line: 43=1, 34=1, Chef can't move to the first number here. Therefore, the answer is 1.
 The fourth line: 55=0, 52=3, 21=1. The answer is 4.
Author:  berezin 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CHEFBM 
Tags  berezin, easy, implementation, may14 
Date Added:  18032014 
Time Limit:  1  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions