import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

/**
 *
 * @param <PositionType>
 * @param <X>
 */
class IntervalMap<PositionType, X> {
    TreeMap<PositionType, X> map;

    X voidValue;

    Comparator<PositionType> comparator;

    public IntervalMap(X voidValue) {
        map = new TreeMap<>();// 区間の左端に対して、その区間の色を返す

        this.voidValue = voidValue;
    }

    // [l, r)
    public void set(PositionType l, PositionType r, X val) {
        var mR = map.floorEntry(r);
        if ((mR != null) && (!mR.getKey().equals(r))) {
            // r-1, r ∈[a, b) となる区間を [a, r) [r, b) で分割
            map.put(r, mR.getValue());
        } else {
            // r-1, r ∈[-∞, b)の場合
            map.put(r, voidValue);// [-∞, r) [r, b) で分割

        }
        do {
            PositionType ml = map.ceilingKey(l);
            if (compare(ml, r) == (-1)) {
                map.remove(ml);
            } else {
                break;
            }
        } while (true );
        map.put(l, val);
        mergeAt(l);
        mergeAt(r);
    }

    public Interval get(PositionType pos) {
        var l = map.floorEntry(pos);
        return new Interval(l.getKey(), map.higherKey(pos), l.getValue());
    }

    class Interval {
        public PositionType l;

        public PositionType r;

        public X x;

        public Interval(PositionType l, PositionType r, X x) {
            this.l = l;
            this.r = r;
            this.x = x;
        }

        @Override
        public String toString() {
            return (((("(l,r,x)=" + l) + ",") + r) + ",") + x;
        }
    }

    /**
     * [hoge,  pos)[pos, fuga) の二つの区間が同じ値ならマージする
     *
     * @param pos
     */
    public void mergeAt(PositionType pos) {
        var left = map.lowerEntry(pos);
        if ((left != null) && left.getValue().equals(map.get(pos))) {
            map.remove(pos);
        }
    }

    @SuppressWarnings("unchecked")
    int compare(PositionType k1, PositionType k2) {
        return comparator == null ? ((Comparable<? super PositionType>) (k1)).compareTo(k2) : comparator.compare(k1, k2);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (var es : map.entrySet()) {
            sb = sb.append(((("[l=" + es.getKey()) + ",x=") + es.getValue()) + ")");
        }
        return sb.toString();
    }
}

class FastScanner {
    private static FastScanner instance = null;

    private final InputStream in = System.in;

    private final byte[] buffer = new byte[1024];

    private int ptr = 0;

    private int buflen = 0;

    private FastScanner() {
    }

    public static FastScanner getInstance() {
        if (instance == null) {
            instance = new FastScanner();
        }
        return instance;
    }

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }
        ptr = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return buflen > 0;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private boolean isPrintableChar(int c) {
        return (33 <= c) && (c <= 126);
    }

    public boolean hasNext() {
        while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
            ptr++;
        } 
        return hasNextByte();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while ((b >= '0') && (b <= '9')) {
            n = (n * 10) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }

    public int nextInt() {
        return ((int) (nextLong()));
    }
}

class MyPrintWriter extends PrintWriter {
    private static MyPrintWriter instance = null;

    private MyPrintWriter() {
        super(System.out);
    }

    public static MyPrintWriter getInstance() {
        if (instance == null) {
            instance = new MyPrintWriter();
        }
        return instance;
    }
}

public class Main implements Runnable {
    public static void main(String[] args) throws IOException {
        Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
        // new Main().gen();
        // new Thread(null, new Main(), "MainThreadWithLargeStack", (1024 * 1024) * 1024).start();// 1024MBスタックを確保して実行
        // new Main().test();
        // new Main().gen();
        new Main().run();
        // MergeFilesTest.test();
    }

    void solve() {
        FastScanner sc = FastScanner.getInstance();
        MyPrintWriter pw = MyPrintWriter.getInstance();
        long D = sc.nextLong();
        int Q = sc.nextInt();
        long ans = 0;
        IntervalMap<Long, Integer> set = new IntervalMap<>(-1);
        for (int QUERY = 0; QUERY < Q; QUERY++) {
            long A = sc.nextLong();
            long B = sc.nextLong();
            set.set(A, B + 1, 1);
            var interval = set.get(A);
            ans = Math.max(ans, interval.r - interval.l);
            System.out.println(ans);
        }
    }

    public void run() {
        var sc = FastScanner.getInstance();
        var pw = MyPrintWriter.getInstance();
        solve();
        // long ans=new Solver().sole(N, x, y);
        pw.flush();
    }
}