Recently a tournament in k kinds of sports has begun in Berland. Vasya wants to make money on the bets.

The scheme of the tournament is very mysterious and not fully disclosed. Competitions are held back to back, each of them involves two sportsmen who have not left the tournament yet. Each match can be held in any of the k kinds of sport. Loser leaves the tournament. The last remaining sportsman becomes the winner. Apart of this, the scheme can be arbitrary, it is not disclosed in advance.

Vasya knows powers of sportsmen in each kind of sport. He believes that the sportsmen with higher power always wins.

The tournament is held every year, and each year one new participant joins it. In the first tournament, only one sportsman has participated, in the second there were two sportsmen, and so on. Vasya has been watching the tournament for the last n years. Help him to find the number of possible winners for each of the n tournaments.

Input

The first line contains two integers n and k (1 ≤ n ≤ 5·104, 1 ≤ k ≤ 10) — the number of tournaments and the number of kinds of sport, respectively.

Each of the next n lines contains k integers si1, si2, ..., sik (1 ≤ sij ≤ 109), where sij is the power of the i-th sportsman in the j-th kind of sport. The sportsman with higher powers always wins. It's guaranteed that for any kind of sport all of these powers are distinct.

Output

For each of the n tournaments output the number of contenders who can win.

Examples

Input

3 2
1 5
5 1
10 10


Output

1
2
1


Input

3 2
2 2
3 3
1 10


Output

1
1
3


Input

3 2
2 3
1 1
3 2


Output

1
1
2

Note

In the first sample:

In the first tournament there is only one sportsman, and he is the winner.

In the second tournament, there are two sportsmen, and everyone can defeat another, depending on kind of sports.

In the third tournament, the third sportsman in the strongest in both kinds of sports, so he is the winner regardless of the scheme.
import java.io.*;
import java.util.*;

public class TaskC {

    public static void main(String[] args) {

        ClassLoader classLoader = TaskC.class.getClassLoader();
        InputStream inputStream = null;
        OutputStream outputStream = null;

        /*
        File fileIn = new File(classLoader.getResource("inC.txt").getFile());;
        File fileOut = new File(classLoader.getResource("outC.txt").getFile());
        try {inputStream = new FileInputStream(fileIn);} catch (FileNotFoundException ex){return;};
        try {outputStream = new FileOutputStream(fileOut);} catch (FileNotFoundException ex){return;};
        /*/
        inputStream = System.in;
        outputStream = System.out;
        //*/

        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        Task solver = new Task();
        solver.solve(in, out);

        out.close();
    }
}

class InputReader {

    private BufferedReader reader;
    private StringTokenizer tokenizer;

    InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    String nextLine(){
        try {
            return reader.readLine();
        } catch (IOException e){
            throw new RuntimeException(e);
        }
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

}

class Task {

    void solve(InputReader in, PrintWriter out) {

        int n = in.nextInt();
        int k = in.nextInt();

        LinkedSet set = new LinkedSet();

        for (int i = 0; i < n; i++) {

            int abilities[] = new int[k];
            for (int j = 0; j < k; j++) {
                abilities[j] = in.nextInt();
            }

            Item item = new Item(abilities, k);

            Node lowest = set.findLowestLeaf(item);
            Node highest = set.findHighestLeaf(item);

            if (lowest == null || highest == null) {
                // первая итерация цикла, в СД ещё нет элементов
                set.addItemAsNode(null, item);

            } else if (lowest.next == highest) {
                // вставляем между множествами
                set.addItemAsNode(lowest, item);

            } else if (item.moreOrEqualThen(set.root.upperBound)) {
                // самый первый
                set.addItemAsHeadNode(item);

            } else if (item.lessThen(set.root.lowerBound)) {
                // самый последний
                set.addItemAsLastNode(item);

            } else if (lowest == highest) {
                // попал в какое-то множество
                set.addItemToNode(lowest, item);

            } else {
                // попал в разные множества
                Node union = set.unionLeafs(highest, lowest);
                set.addItemToNode(union, item);
            }

            //System.out.println("---------------- " + i + " -----------------");
            //set.print(set.root, 0);
            out.println(set.head.numberOfElements);


        }
    }
}

class Item {

    private int k;
    int value[];

    Item(int value[], int k) {
        this.k = k;
        this.value = value;
    }

    boolean updateLower(Item item) {

        boolean updated = false;

        for (int i = 0; i < k; i++) {
            if (value[i] > item.value[i]) {
                value[i] = item.value[i];
                updated = true;
            }
        }

        return updated;
    }

    boolean updateUpper(Item item) {

        boolean updated = false;

        for (int i = 0; i < k; i++) {
            if (value[i] < item.value[i]) {
                value[i] = item.value[i];
                updated = true;
            }
        }

        return updated;
    }

    boolean shift(Item from, Item to) {

        boolean updated = false;

        for (int i = 0; i < k; i++) {
            if (value[i] == from.value[i]) {
                value[i] = to.value[i];
                updated = true;
            }
        }

        return updated;
    }

    boolean moreOrEqualThen(Item item) {

        for (int i = 0; i < k; i++) {
            if (value[i] < item.value[i]) {
                return false;
            }
        }
        return true;
    }

    boolean lessThen(Item item) {

        for (int i = 0; i < k; i++) {
            if (value[i] >= item.value[i]) {
                return false;
            }
        }
        return true;
    }

    Item upperBound() {

        int newValue[] = new int[k];
        for (int i = 0; i < k; i++) {
            newValue[i] = value[i] + 1;
        }
        return new Item(newValue, k);
    }

    Item copy() {

        int newValue[] = new int[k];
        for (int i = 0; i < k; i++) {
            newValue[i] = value[i];
        }
        return new Item(newValue, k);
    }
}

class Node {

    Item lowerBound;
    Item upperBound;
    int numberOfElements;
    int height;
    Node parent;
    Node left;
    Node right;
    Node prev;
    Node next;


    Node(Item lowerBound, Item upperBound, int numberOfElements) {
        this.numberOfElements = numberOfElements;
        this.lowerBound = lowerBound;
        this.upperBound = upperBound;
        this.height = 0;
    }

    Node(Item lowerBound, Item upperBound) {
        this.lowerBound = lowerBound;
        this.upperBound = upperBound;
        this.height = 1;
    }

    boolean add(Item item) {
        if (height == 0) {
            numberOfElements++;
        }
        return lowerBound.updateLower(item) | upperBound.updateUpper(item.upperBound());
    }

    boolean removeSelfInterval(Item lower, Item upper) {
        return lowerBound.shift(lower, upper) | upperBound.shift(upper, lower);
    }
}

class LinkedSet {

    Node root;
    Node head;

    LinkedSet() {
        root = null;
        head = null;
    }

    void print(Node node, int deep) {
        System.out.println(deep + " [" + node.lowerBound.value[0] + " "  + node.upperBound.value[0] +"]");
        if (node.left != null)  {
            System.out.println("left  " + deep + ": ");
            print(node.left, deep + 1);
        }
        if (node.right != null)  {
            System.out.println("right " + deep + ": ");
            print(node.right, deep + 1);
        }
    }

    void addItemToNode(Node node, Item item) {

        if (!node.add(item)) {
            return;
        }

        Node parent = node.parent;
        while (parent != null && parent.add(item)) {
            parent = parent.parent;
        }
    }

    void addItemAsNode(Node prevNode, Item item) {

        Node addedNode = new Node(item.copy(), item.upperBound(), 1);

        // тривиальный случай - пустое лерево
        if (root == null) {
            root = addedNode;
            head = addedNode;
            return;
        }

        // проверка идет не сразу, так как если дерево пустое то prevNode нас не интересует
        if (prevNode.height != 0) {
            throw new UnsupportedOperationException("Parameter 'prevNode' is not a leaf.");
        }

        Node parent = new Node(prevNode.lowerBound.copy(), prevNode.upperBound.copy());

        // тривиальный случай - одна вершина
        if (prevNode == root) {
            // формируем дерево
            root = parent;
            parent.left = prevNode;
            prevNode.parent = parent;
            parent.right = addedNode;
            addedNode.parent = parent;
            addItemToNode(parent, item);
            // формируем список, head уже prevNode
            addedNode.prev = prevNode;
            prevNode.next = addedNode;
            return;
        }

        // добавляем в дерево
        parent.parent = prevNode.parent;
        if (prevNode.parent.left == prevNode) {
            prevNode.parent.left = parent;
        } else {
            prevNode.parent.right = parent;
        }

        parent.left = prevNode;
        prevNode.parent = parent;

        parent.right = addedNode;
        addedNode.parent = parent;

        // и в двусвязный список
        if (prevNode.next != null) {
            addedNode.next = prevNode.next;
            addedNode.next.prev = addedNode;
        }
        addedNode.prev = prevNode;
        prevNode.next = addedNode;

        // обновляем предков
        addItemToNode(parent, item);
        updateHeight(parent.parent);
    }

    void addItemAsHeadNode(Item item) {

        Node addedNode = new Node(item.copy(), item.upperBound(), 1);
        Node parent = new Node(head.lowerBound.copy(), head.upperBound.copy());

        // тривиальный случай - одна вершина
        if (head == root) {
            // формируем дерево
            root = parent;
            parent.left = addedNode;
            addedNode.parent = parent;
            parent.right = head;
            head.parent = parent;
            addItemToNode(parent, item);
            // формируем список, head уже prevNode
            addedNode.next = head;
            head.prev = addedNode;
            head = addedNode;
            return;
        }

        // добавляем в дерево
        parent.parent = head.parent;
        head.parent.left = parent;

        parent.left = addedNode;
        addedNode.parent = parent;

        parent.right = head;
        head.parent = parent;

        // и в двусвязный список
        addedNode.next = head;
        head.prev = addedNode;
        head = addedNode;

        // обновляем предков
        addItemToNode(parent, item);
        updateHeight(parent.parent);
    }

    void addItemAsLastNode(Item item) {

        Node lastNode = root;

        while (lastNode.right != null) {
            lastNode = lastNode.right;
        }

        addItemAsNode(lastNode, item);
    }

    void removeLeaf(Node node) {

        if (node.height != 0) {
            throw new UnsupportedOperationException("Parameter 'node' is not a leaf.");
        }

        // тривиальный случай - одна вершина
        if (node == root) {
            root = null;
            head = null;
            return;
        }

        Node parent = node.parent;
        Node brother = parent.left == node ? parent.right : parent.left;

        // тривиальный случай - подвешены к корню справа
        if (parent == root) {
            root = brother;
            brother.parent = null;
            node.prev.next = null;
            return;
        }

        // обновление дерева
        brother.parent = parent.parent;
        if (parent.parent.left == parent) {
            parent.parent.left = brother;
        } else {
            parent.parent.right = brother;
        }

        // обновление двусвязного списока
        if (node == head) {
            // первый в списке
            head = node.next;
            node.next.prev = null;
        } else if (node.next == null) {
            // последний в списке
            node.prev.next = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        // обновляем предков
        parent = brother.parent;
        while (parent != null && parent.removeSelfInterval(node.lowerBound, node.upperBound)) {
            parent = parent.parent;
        }
        updateHeight(brother.parent);
    }

    Node unionLeafs(Node from, Node to) {

        if (from == to) {
            return from;
        }

        while (from.next != to) {
            from = unionLeafWithNext(from);
        }

        return unionLeafWithNext(from);
    }

    Node findLowestLeaf(Item item) {

        if (root == null || root.height == 0) {
            return root;
        }

        Node node = root;

        while (node.height > 0) {
            if (item.moreOrEqualThen(node.right.upperBound)) {
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return node;
    }

    Node findHighestLeaf(Item item) {

        if (root == null || root.height == 0) {
            return root;
        }

        Node node = root;

        while (node.height > 0) {
            if (item.lessThen(node.left.lowerBound)) {
                node = node.right;
            } else {
                node = node.left;
            }
        }

        return node;
    }

    private Node unionLeafWithNext(Node leaf) {

        if (leaf.height != 0 || leaf.next == null) {
            throw new UnsupportedOperationException();
        }

        Item item = leaf.next.lowerBound;

        addItemToNode(leaf, item);
        leaf.numberOfElements += leaf.next.numberOfElements - 1;
        removeLeaf(leaf.next);

        return leaf;
    }

    private void updateHeight(Node node) {
        Node updated = node;
        while (updated != null) {
            if (Math.abs(balanceOfNode(updated)) > 1) {
                updated = balanceSubTree(updated);
            }
            updated.height = Math.max(updated.left.height, updated.right.height) + 1;
            updated = updated.parent;
        }
    }

    private int balanceOfNode(Node node) {
        return node.height == 0 ? 0 : node.left.height - node.right.height;
    }

    private Node balanceSubTree(Node node) {

        if (balanceOfNode(node) > 1) {
            if (balanceOfNode(node.left) >= 0) {
                return littleRightRotate(node);
            } else {
                return bigRightRotate(node);
            }
        } else if (balanceOfNode(node) < -1) {
            if (balanceOfNode(node.left) <= 0) {
                return littleLeftRotate(node);
            } else {
                return bigLeftRotate(node);
            }
        }

        return node;
    }

    private Node littleRightRotate(Node node) {

        Node newParent = node.left;

        newParent.parent = node.parent;
        if (node != root) {
            if (node.parent.left == node) {
                node.parent.left = newParent;
            } else {
                node.parent.right = newParent;
            }
        } else {
            root = newParent;
        }
        node.left = newParent.right;
        newParent.right.parent = node;
        newParent.right = node;
        node.parent = newParent;
        node.height = Math.max(node.left.height, node.right.height) + 1;
        newParent.lowerBound = node.lowerBound.copy();
        node.upperBound = node.left.upperBound.copy();

        return newParent;
    }

    private Node littleLeftRotate(Node node) {

        Node newParent = node.right;

        newParent.parent = node.parent;
        if (node != root) {
            if (node.parent.left == node) {
                node.parent.left = newParent;
            } else {
                node.parent.right = newParent;
            }
        } else {
            root = newParent;
        }
        node.right = newParent.left;
        newParent.left.parent = node;
        newParent.left = node;
        node.parent = newParent;
        node.height = Math.max(node.left.height, node.right.height) + 1;
        newParent.upperBound = node.upperBound.copy();
        node.lowerBound = node.right.lowerBound.copy();

        return newParent;
    }

    private Node bigRightRotate(Node node) {

        Node newParent = node.left.right;

        newParent.parent = node.parent;
        if (node != root) {
            if (node.parent.left == node) {
                node.parent.left = newParent;
            } else {
                node.parent.right = newParent;
            }
        } else {
            root = newParent;
        }
        node.left.right = newParent.left;
        newParent.left.parent = node.left;
        newParent.left = node.left;
        node.left.parent = newParent;
        node.left = newParent.right;
        newParent.right.parent = node;
        newParent.right = node;
        node.parent = newParent;
        updateHeightOfSingleNode(node);
        updateHeightOfSingleNode(newParent.left);
        updateHeightOfSingleNode(newParent);
        updateBoundsOfSingleNode(node);
        updateBoundsOfSingleNode(newParent.left);
        updateBoundsOfSingleNode(newParent);

        return newParent;
    }

    private Node bigLeftRotate(Node node) {

        Node newParent = node.right.left;

        newParent.parent = node.parent;
        if (node != root) {
            if (node.parent.left == node) {
                node.parent.left = newParent;
            } else {
                node.parent.right = newParent;
            }
        } else {
            root = newParent;
        }
        node.right.left = newParent.right;
        newParent.right.parent = node.right;
        newParent.right = node.right;
        node.right.parent = newParent;
        node.right = newParent.left;
        newParent.left.parent = node;
        newParent.left = node;
        node.parent = newParent;
        updateHeightOfSingleNode(node);
        updateHeightOfSingleNode(newParent.right);
        updateHeightOfSingleNode(newParent);
        updateBoundsOfSingleNode(node);
        updateBoundsOfSingleNode(newParent.right);
        updateBoundsOfSingleNode(newParent);

        return newParent;
    }

    private void updateHeightOfSingleNode(Node node) {
        node.height = Math.max(node.left.height, node.right.height) + 1;
    }

    private void updateBoundsOfSingleNode(Node node) {
        node.lowerBound = node.right.lowerBound.copy();
        node.upperBound = node.left.upperBound.copy();
    }
}
