Problem: You are given a chessboard consisting of n rows and n columns. Rows are numbered from bottom to top from 1 to n. Columns are numbered from left to right from 1 to n. The cell at the intersection of the x-th column and the y-th row is denoted as (x, y). Furthermore, the k-th column is a special column. 

Initially, the board is empty. There are m changes to the board. During the i-th change one pawn is added or removed from the board. The current board is good if we can move all pawns to the special column by the followings rules:

  * Pawn in the cell (x, y) can be moved to the cell (x, y + 1), (x - 1, y + 1) or (x + 1, y + 1); 
  * You can make as many such moves as you like; 
  * Pawns can not be moved outside the chessboard; 
  * Each cell can not contain more than one pawn. 



The current board may not always be good. To fix it, you can add new rows to the board. New rows are added at the top, i. e. they will have numbers n+1, n+2, n+3, ....

After each of m changes, print one integer — the minimum number of rows which you have to add to make the board good.

Input

The first line contains three integers n, k and m (1 ≤ n, m ≤ 2 ⋅ 10^5; 1 ≤ k ≤ n) — the size of the board, the index of the special column and the number of changes respectively.

Then m lines follow. The i-th line contains two integers x and y (1 ≤ x, y ≤ n) — the index of the column and the index of the row respectively. If there is no pawn in the cell (x, y), then you add a pawn to this cell, otherwise — you remove the pawn from this cell.

Output

After each change print one integer — the minimum number of rows which you have to add to make the board good.

Example

Input


5 3 5
4 4
3 5
2 4
3 4
3 5


Output


0
1
2
2
1

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.*;
import java.util.*;
 
public class Main {
	static int N;
	static int K;
	static long NONE = -100000000000L;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		
		N = sc.ni();
		K = sc.ni()-1;
		int Q = sc.ni();
		int[][] queries = new int[Q][2];
		ArrayList<Pawn> pawns = new ArrayList<Pawn>();
		HashSet<Long> hs = new HashSet<Long>();
		for (int q = 0; q < Q; q++) {
			int c = sc.ni()-1;
			int r = sc.ni()-1;
			queries[q] = new int[] {r,c};
			Pawn p = new Pawn(r,c,q);
			if (!hs.contains(p.map)) {
				hs.add(p.map);
				pawns.add(p);
			}
		}
		int P = pawns.size();
		Collections.sort(pawns);
		HashMap<Long,Integer> access = new HashMap<Long,Integer>();
		for (int i = 0; i < P; i++)
			access.put(pawns.get(i).map,i);
		BinaryIndexedTree bit = new BinaryIndexedTree(P);
		LazyST st = new LazyST(P);
		st.add(0, P-1, NONE);
		for (int q = 0; q < Q; q++) {
			int[] query = queries[q];
			int idx = access.get(query[0]*((long)N)+query[1]);
			if (!bit.exists[idx]) {
				//add a pawn
				bit.add(1, idx);
				long val = (long)(pawns.get(idx).minR+bit.sum(idx+1,P));
				long add = val-st.query(idx, idx);
				st.add(idx, idx, add);
				st.add(0, idx-1, 1L);
			} else {
				//remove a pawn
				bit.add(-1, idx);
				long add = NONE-st.query(idx, idx);
				st.add(idx, idx, add);
				st.add(0, idx-1, -1L);
			}
			long minR = st.query(0, P-1);
			long ans = Math.max(0L, minR-N+1);
			pw.println(ans);
		}
		pw.close();
	}
	
	static class BinaryIndexedTree {
		public int[] arr;
		public boolean[] exists;

		public BinaryIndexedTree (int N) {
			arr = new int[N+1];
			exists = new boolean[N];
		}

		//add k to the i-th element.
		public void add(int k, int i) {
			int node = i+1;
			if (k!=0)
				exists[i] = !exists[i];
			while (node < arr.length) {
				arr[node] += k;
				node += node & (-node);
			}
		}

		//sum up the elements from input[s_i] to input[e_i], from [s_i,e_i).
		public int sum(int s_i, int e_i) {
			return sum(e_i) - sum(s_i);
		}

		public int sum(int i) {
			int total = 0;
			int node = i;
			while (node > 0) {
				total += arr[node];
				node -= node & (-node);
			}
			return total;
		}
	}
	
	static class LazyST {
		public long[] tree;
		public long[] lazy;
		public int N;

		public LazyST(int n) {
			N = n;
			tree = new long[4*N+1];
			lazy = new long[4*N+1];
		}

		//range update nums[updateL..updateR] += val;
		public void add(int updateL, int updateR, long val) {
			add(0,0,N-1,updateL,updateR,val);
		}

		private void add(int n, int L, int R, int updateL, int updateR, long val) {
			push(n,L,R);
			if (updateL <= L && R <= updateR) {
				//fully contained
				lazy[n] += val;
				push(n,L,R);
				return;
			} else if (L>updateR || R<updateL || L==R) {
				//not contained at all or leaf
				return;
			}
			add(2*n+1,L,(L+R)/2,updateL,updateR,val); 
			add(2*n+2,(L+R)/2+1,R,updateL,updateR,val);
			tree[n] = merge(tree[2*n+1],tree[2*n+2]);
		}

		public long query(int Lq, int Rq) {
			return query(0,0,N-1,Lq,Rq);
		}

		private long query(int n, int L, int R, int Lq, int Rq) {
			push(n,L,R);
			if (Lq <= L && R <= Rq) {
				return tree[n];
			} else if (R < Lq || Rq < L) {
				return 300000*NONE;
			} else {
				return merge(query(2*n+1,L,(L+R)/2,Lq,Rq),query(2*n+2,(L+R)/2+1,R,Lq,Rq));
			}
		}

		private void push(int n, int L, int R) {
			tree[n] += operation(lazy[n],L,R);

			if (L < R) {
				lazy[2*n+1] += lazy[n];
				lazy[2*n+2] += lazy[n];
			}
			lazy[n] = 0L;
		}

		public long merge(long a, long b) {
			//return Math.min(a,b); //min,NONE=INF
			return Math.max(a,b); //max,NONE=NEG INF
			//return (a+b); //sum,NONE=0
		}

		//used to process lazy updates
		public long operation(long a, long L, long R) {
			return a; //min or max
			//return (R-L+1)*a; //sum
		}
	}
	
	static class Pawn implements Comparable<Pawn> {
		int minR;
		int idx;
		long map;
		
		public Pawn(int r, int c, int i) {
			minR = r+Math.abs(K-c);
			idx = i;
			map = r*((long)N)+c;
		}
		
		public int compareTo(Pawn p) {
			return (minR-p.minR);
		}
		
		public String toString() {
			return ("[" + (map/N) + ", " + (map%N) + ", MINR: " + minR + "]");
		}
	}
	
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        }
        
        int ni() { 
            return Integer.parseInt(next()); 
        }
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() {
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str;
        }
    }
}