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.util.*;
import java.io.*;
public class Edu90G{
   public static void main(String[] main) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      PrintWriter out = new PrintWriter(System.out);
      int size = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken())-1;
      int m = Integer.parseInt(st.nextToken());
      HashSet<Long> pawn = new HashSet<Long>();
      int[] arr = new int[2*size];
      for(int i = 0; i < 2*size; i++) {
    	  arr[i] = i-1;
      }
      PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
      constructST(arr,2*size);
      for(int i = 0; i < m; i++) {
    	  st = new StringTokenizer(br.readLine());
    	  int x = Integer.parseInt(st.nextToken())-1;
    	  int y = Integer.parseInt(st.nextToken())-1;
    	  long coord = (long)x*size + y;
    	  if(pawn.contains(coord)) {
    		  pawn.remove(coord);
    		  arr[y + Math.abs(x-k)]--;
        	  updateRange(2*size, 0, y + Math.abs(x-k), -1);
        	  pq.remove(-y-Math.abs(x-k));
    	  }
    	  else {
    		  pawn.add(coord);
    		  arr[y + Math.abs(x-k)]++;
        	  updateRange(2*size, 0, y + Math.abs(x-k), 1);
        	  pq.add(-y - Math.abs(x-k));
    	  }
    	  if(pq.size() > 0) {
	    	  int res = query(2*size, 0, -pq.peek());
	    	  if(res > size-1)
	    		  out.println(res - size + 1);
	    	  else
	    		  out.println(0);
    	  }
    	  else
    		  out.println(0);
      }
      out.close();
   }
      
  
// Ideally, we should not use global variables and large 
// constant-sized arrays, we have done it here for simplicity 
  
// To store segment tree 
static int tree[]; 
  
// To store pending updates 
static int lazy[]; 
  
// si -> index of current node in segment tree 
// ss and se -> Starting and ending indexes of 
// elements for which current nodes stores sum 
// us and ue -> starting and ending indexes of update query 
// diff -> which we need to add in the range us to ue 
static void updateRangeUtil(int si, int ss, int se, int us, 
                    int ue, int diff) 
{ 
    // If lazy value is non-zero for current node of segment 
    // tree, then there are some pending updates. So we need 
    // to make sure that the pending updates are done before 
    // making new updates. Because this value may be used by 
    // parent after recursive calls (See last line of this 
    // function) 
    if (lazy[si] != 0) 
    { 
        // Make pending updates using value stored in lazy 
        // nodes 
        tree[si] += lazy[si]; 
  
        // Checking if it is not leaf node because if 
        // it is leaf node then we cannot go further 
        if (ss != se) 
        { 
            // We can postpone updating children we don't 
            // need their new values now. 
            // Since we are not yet updating children of si, 
            // we need to set lazy flags for the children 
            lazy[si * 2 + 1] += lazy[si]; 
            lazy[si * 2 + 2] += lazy[si]; 
        } 
  
        // Set the lazy value for current node as 0 as it 
        // has been updated 
        lazy[si] = 0; 
    } 
  
    // Out of range 
    if (ss > se || ss > ue || se < us) 
        return; 
  
    // Current segment is fully in range 
    if (ss >= us && se <= ue) 
    { 
        // Add the difference to current node 
        tree[si] += diff; 
  
        // Same logic for checking leaf node or not 
        if (ss != se) 
        { 
            // This is where we store values in lazy nodes, 
            // rather than updating the segment tree itelf 
            // Since we don't need these updated values now 
            // we postpone updates by storing values in lazy[] 
            lazy[si * 2 + 1] += diff; 
            lazy[si * 2 + 2] += diff; 
        } 
        return; 
    } 
  
    // If not completely in range, but overlaps 
    // recur for children 
    int mid = (ss + se) / 2; 
    updateRangeUtil(si * 2 + 1, ss, mid, us, ue, diff); 
    updateRangeUtil(si * 2 + 2, mid + 1, se, us, ue, diff); 
  
    // And use the result of children calls 
    // to update this node 
    tree[si] = Math.max(tree[si * 2 + 1], tree[si * 2 + 2]); 
} 
  
// Function to update a range of values in segment 
// tree 
// us and eu -> starting and ending indexes of update query 
// ue -> ending index of update query 
// diff -> which we need to add in the range us to ue 
static void updateRange(int n, int us, int ue, int diff) 
{ 
    updateRangeUtil(0, 0, n - 1, us, ue, diff); 
} 
  
// A recursive function to get the sum of values in given 
// a range of the array. The following are the parameters 
// for this function 
// si --> Index of the current node in the segment tree 
// Initially, 0 is passed as root is always at index 0 
// ss & se --> Starting and ending indexes of the 
// segment represented by current node 
// i.e., tree[si] 
// qs & qe --> Starting and ending indexes of query 
// range 
static int getSumUtil(int ss, int se, int qs, int qe, int si) 
{ 
  
    // If lazy flag is set for current node of segment tree 
    // then there are some pending updates. So we need to 
    // make sure that the pending updates are done before 
    // processing the sub sum query 
    if (lazy[si] != 0) 
    { 
  
        // Make pending updates to this node. Note that this 
        // node represents sum of elements in arr[ss..se] and 
        // all these elements must be increased by lazy[si] 
        tree[si] += lazy[si]; 
  
        // Checking if it is not leaf node because if 
        // it is leaf node then we cannot go further 
        if (ss != se) 
        { 
            // Since we are not yet updating children os si, 
            // we need to set lazy values for the children 
            lazy[si * 2 + 1] += lazy[si]; 
            lazy[si * 2 + 2] += lazy[si]; 
        } 
  
        // Unset the lazy value for current node as it has 
        // been updated 
        lazy[si] = 0; 
    } 
  
    // Out of range 
    if (ss > se || ss > qe || se < qs) 
        return 0; 
  
    // At this point, we are sure that pending lazy updates 
    // are done for current node. So we can return value 
    // (same as it was for a query in our previous post) 
  
    // If this segment lies in range 
    if (ss >= qs && se <= qe) 
        return tree[si]; 
  
    // If a part of this segment overlaps with the given 
    // range 
    int mid = (ss + se) / 2; 
    return Math.max(getSumUtil(ss, mid, qs, qe, 2 * si + 1), 
            getSumUtil(mid + 1, se, qs, qe, 2 * si + 2)); 
} 
  
// Return sum of elements in range from index qs (query 
// start) to qe (query end). It mainly uses getSumUtil() 
static int query(int n, int qs, int qe) 
{ 
    // Check for erroneous input values 
    if (qs < 0 || qe > n - 1 || qs > qe) 
    { 
        System.out.print("Invalid Input"); 
        return -1; 
    } 
  
    return getSumUtil(0, n - 1, qs, qe, 0); 
} 
  
// A recursive function that constructs Segment Tree for 
// array[ss..se]. si is index of current node in segment 
// tree st. 
static void constructSTUtil(int arr[], int ss, int se, int si) 
{ 
    // out of range as ss can never be greater than se 
    if (ss > se) 
        return; 
  
    // If there is one element in array, store it in 
    // current node of segment tree and return 
    if (ss == se)  
    { 
        tree[si] = arr[ss]; 
        return; 
    } 
  
    // If there are more than one elements, then recur 
    // for left and right subtrees and store the sum 
    // of values in this node 
    int mid = (ss + se) / 2; 
    constructSTUtil(arr, ss, mid, si * 2 + 1); 
    constructSTUtil(arr, mid + 1, se, si * 2 + 2); 
  
    tree[si] = Math.max(tree[si * 2 + 1], tree[si * 2 + 2]); 
} 
  
// Function to construct a segment tree from a given array 
// This function allocates memory for segment tree and 
// calls constructSTUtil() to fill the allocated memory 
static void constructST(int arr[], int n) 
{ 
	lazy = new int[4*n+10];
	tree = new int[4*n+10];
    // Fill the allocated memory st 
    constructSTUtil(arr, 0, n - 1, 0); 
} 
}