Galactic

import java.util.StringTokenizer;

import java.io.BufferedReader;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.util.Random;

class Kattio extends PrintWriter {
    public Kattio(InputStream i) {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(i));
    }
    public Kattio(InputStream i, OutputStream o) {
        super(new BufferedOutputStream(o));
        r = new BufferedReader(new InputStreamReader(i));
    }

    public int getInt() {
        return Integer.parseInt(nextToken());
    }

    public double getDouble() {
        return Double.parseDouble(nextToken());
    }

    public long getLong() {
        return Long.parseLong(nextToken());
    }

    public String getWord() {
        return nextToken();
    }



    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;

    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) { }
        return token;
    }

    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }
}

class Node {
	Node left, right, parent;
	int index, score, penalty, height, size;

	Node(int ind, int a, int b) {
		this.score = a;
		this.penalty = b;
		this.index = ind;
	}

	String info() {
		return Integer.toString(this.index) + ", " + Integer.toString(this.score) + ", " + Integer.toString(this.penalty);
	}

}

class BinaryTree {
	Node root;
	Node[] list;

	BinaryTree(int n) {
		this.list = new Node[n + 1];
		for (int i = 1; i < n + 1; i++) {
			list[i] = new Node(i, 0, 0);
		}
	}

	int max(int a, int b) {
		a = (a > b) ? a : b;
		return a;
	}

	int height(Node team) {
		//System.out.println("height");

		if (team == null) {return -1;}
		else {
			int a = (team.left == null) ? -1 : team.left.height;
			int b = (team.right == null) ? -1 : team.right.height;
			return max(a, b) + 1;
		}
	}

	int size(Node team) {
		//System.out.println("size");

		if (team == null) {return 0;}
		else {
			int a = (team.left == null) ? 0 : team.left.size;
			int b = (team.right == null) ? 0 : team.right.size;
			return 1 + a + b;
		}
	}

	Boolean comparer(Node teama, Node teamb) {
		System.out.println("compare " + teama.info() + " and " + teamb.info());

		if (teama.score == teamb.score && teama.penalty == teamb.penalty) {
			return teama.index < teamb.index;
		}
		return teama.score > teamb.score || (teama.score == teamb.score && teama.penalty < teamb.penalty);
	}

	//t.right must be != null
	void rotateleft(Node t) {
		System.out.println("rl " + t.info());

		Node w = t.right;
		System.out.println(w.info());
		w.parent = t.parent;
		t.parent = w;
		t.right = w.left;
		if (w.left != null) w.left.parent = t;
		w.left = t;
		if (w.parent != null) {
			if (w.parent.right != null) {
				if (w.parent.right == t) {w.parent.right = w;}
			}
			if (w.parent.left != null) {
				if (w.parent.left == t) {w.parent.left = w;}
			}
		}
		if (t == this.root) {this.root = w;}
		t.height = height(t);
		w.height = height(w);
		if (w.parent != null) w.parent.height = height(w.parent);
	}

	//t.left must be != null
	void rotateright(Node t) {
		System.out.println("rr " + t.info());

		Node w = t.left;
		w.parent = t.parent;
		t.parent = w;
		t.left = w.right;
		if (w.right != null) w.right.parent = t;
		w.right = t;
		if (w.parent != null) {
			if (w.parent.right != null) {
				if (w.parent.right == t) {w.parent.right = w;}
			}
			if (w.parent.left != null) {
				if (w.parent.left == t) {w.parent.left = w;}
			}
		}
		if (t == this.root) {this.root = w;}
		t.height = height(t);
		w.height = height(w);
		if (w.parent != null) w.parent.height = height(w.parent);
	}

	int bf(Node t) {
		int a = (t.left == null) ? -1 : t.left.height;
		int b = (t.right == null) ? -1 : t.right.height;
		return a - b;
	}

	void insert(Node team) {
		System.out.println("insert " + team.info());
		team.parent = null;
		team.left = null;
		team.right = null;
		team.height = 0;
		team.size = 1;
		if (this.root == null) {
			this.root = team;
		}
		else {
			//traverses down where the node should go
			Node curr = this.root, prev = curr;
			while (curr != null) {
				prev = curr;
				curr = (comparer(curr, team)) ? curr.left : curr.right;
			}
			team.parent = prev;
			if (comparer(prev, team)) {prev.left = team;}
			else {prev.right = team;}

			//updates the lineage for height
			fixavl(prev);
		}
	}

	void fixavl(Node prev) {
		System.out.println("fixavl at " + prev.info());
		while (prev != null) {
			prev.height = height(prev);
			if (bf(prev) == 2) {
				System.out.println(bf(prev) + " is BF of " + prev.info());

				if (bf(prev.left) == -1) {rotateleft(prev.left);}
				rotateright(prev);
				prev = prev.parent;

			}
			else if (bf(prev) == -2) {
				if (bf(prev.right) == 1) {rotateright(prev.right);}
				rotateleft(prev);
				prev = prev.parent;
			}
			prev = prev.parent;
		}
	}

	Node lowest(Node from) {
		System.out.println("lowest");

		Node low = from;
		if (low == null) {return null;}
		else {
			while (low.left != null) {low = low.left; System.out.println("here?");}
			return low;
		}
	}

	void remove(Node team) {
		System.out.println("removing " + team.info());

		if (team.left == null && team.right == null) {
			if (this.root == team) {this.root = null;}
			else {
				if (team.parent.right == team) {team.parent.right = null;}
				else {team.parent.left = null;}
				fixavl(team.parent);
			}
		}

		else if (team.left != null && team.right != null) {
			System.out.println("THIS CURSED PART");
			Node child = team.right;
			while (child.left != null) {child = child.left;}
			this.list[team.index] = child;
			this.list[child.index] = team;
			int tindex = team.index, tscore = team.score, tpenalty = team.penalty;
			team.index = child.index;
			team.score = child.score;
			team.penalty = child.penalty;
			child.index = tindex;
			child.score = tscore;
			child.penalty = tpenalty;

			remove(child);
		}

		else {
			if (team == this.root) {
				if (team.left != null) {
					this.root = team.left;
					team.left.parent = null;
				}
				else {
					this.root = team.right;
					team.right.parent = null;
				}
				fixavl(this.root);
			}
			else {
				System.out.println("here");
				Node temp = (team.left != null) ? team.left : team.right;
				if (team.parent.right != null) {
					if (team.parent.right.index == team.index) {
						team.parent.right = temp;
						temp.parent = team.parent;
					}
				}
				if (team.parent.left != null) {
					if (team.parent.left.index == team.index) {
						team.parent.left = temp;
						temp.parent = team.parent;
					}
				}
				fixavl(team.parent);
			}
		}
	}

	Node successor(Node curr) {
		Node temp = curr;
		if (curr.right != null) {return lowest(curr.right);}
		while (temp.parent != null) {
			if (temp.parent.left != null) {
				if (temp.parent.left.index == temp.index) {return temp.parent;}
			}
			temp = temp.parent;
		}
		return null;
	}

}
public class Galactic {

	public static void main(String[] args) {
		Kattio br = new Kattio(System.in);
		Random rng = new Random();
		int nn = br.getInt(), n = br.getInt();
		BinaryTree tree = new BinaryTree(nn);
		boolean[] intree = new boolean[nn+1];
		int rank = 1;

		for (int i = 0; i < n; i++) {
			int newteam = rng.nextInt(nn) + 1, newpenal = rng.nextInt(3);
			System.out.println(newteam + " " + newpenal);
			System.out.println(tree.list[newteam].info());
			//int newteam = br.getInt(), newpenal = br.getInt();
			if (intree[newteam]) {tree.remove(tree.list[newteam]);}
			tree.list[newteam].score++;
			tree.list[newteam].penalty += newpenal;

			if (newteam == 1) {
				Node low = tree.lowest(tree.root);
				while(low != null && tree.comparer(tree.list[1], low)) {
					rank--;
					Node temp = tree.successor(low);
					tree.remove(low);
					intree[low.index] = false;
					low = temp;
				}
			}

			else if (newteam != 1 && tree.comparer(tree.list[newteam], tree.list[1])) {
				if (!intree[newteam]) {rank++;}
				intree[newteam] = true;
				tree.insert(tree.list[newteam]);
			}
			System.out.println("\n NODE LIST");

			for (Node node : tree.list) {
				if (node != null) {
				if (intree[node.index]) {
					if (node.left != null) System.out.print(node.left.info());
					else {System.out.print("null");}
					System.out.print(" " + node.info() + " ");
					if (node.right != null) System.out.print(node.right.info());
					else {System.out.print("null");}
					System.out.print("- height:" + node.height);
					System.out.print("\n");


				}
			}}

		br.println(rank);

		}

		br.close();

	}

}
/*
3 4
2 7
3 5
1 6
1 9

CREATES BUG
8 2
5 1
10 2
4 2
7 1

*/