import static java.lang.Math.*; import static java.util.Arrays.*; import java.io.*; import java.lang.reflect.Array; import java.math.BigInteger; import java.util.*; import java.util.concurrent.ArrayBlockingQueue; import java.util.concurrent.ThreadLocalRandom; import java.util.function.*; import java.util.stream.IntStream; class Solver{ long st = System.currentTimeMillis(); long elapsed(){ return System.currentTimeMillis() -st; } void reset(){ st = System.currentTimeMillis(); } static int infI = (1 <<30) -1; static long infL = 1L <<60; // static long mod = (int) 1e9 +7; static long mod = 998244353; static String yes = "Yes"; static String no = "No"; static Random rd = ThreadLocalRandom.current(); MyReader in = new MyReader(System.in); MyWriter out = new MyWriter(System.out); MyWriter log = new MyWriter(System.err){ @Override void println(Object obj){ super.println(obj == null ? "null" : obj); }; @Override protected void ln(){ super.ln(); flush(); }; }; Object solve(){ long D = in.lg(); int Q = in.it(); var set = new RangeSet(); long max = 0; while (Q-- > 0) { long l = in.lg(); long r = in.lg() +1; set.add(l,r); long[] t = set.get(l); max = max(max,t[1] -t[0]); out.println(max); } return null; } } class RangeSet{ @Override public String toString(){ List list = new ArrayList<>(); for (var s:set) list.add(Arrays.toString(s)); return list.toString(); } private TreeSet set; public RangeSet(){ set = new TreeSet<>(Comparator.comparing(t -> t[0])); long infL = Solver.infL; set.add(new long[]{-infL, -infL}); set.add(new long[]{infL, infL}); } void add(long l,long r){ long[] t = {l, r}; for (var s = t;t[0] <= s[1];s = set.floor(t)) adj(t,s); for (var s = t;s[0] <= t[1];s = set.ceiling(t)) adj(t,s); set.add(t); } void adj(long[] t,long[] s){ set.remove(s); t[0] = min(t[0],s[0]); t[1] = max(t[1],s[1]); } public long[] get(long l){ return set.floor(new long[]{l}); } } abstract class Dijkstra> extends Graph{ private L[] len; private int[] arr; private int[] rev; private int size; private Edge[] pre; @SuppressWarnings("unchecked") public Dijkstra(int n,boolean dir){ super(n,dir); len = (L[]) new Comparable[n]; arr = new int[n]; rev = new int[n]; } protected abstract L zero(); protected abstract L inf(); protected abstract L f(L l,E val); @SuppressWarnings("unchecked") public void calcFrom(int s){ init(); pre = new Edge[n]; set(s,zero()); while (!isEmpty()) { var cur = poll(); L l = len[cur]; for (var e:go(cur)) { L ll = f(l,e.val); if (ll.compareTo(len[e.v.id]) < 0) { pre[e.v.id] = e; set(e.v.id,ll); } } } } public L len(int t){ return len[t]; } public Deque> path(int t){ Deque> ret = new ArrayDeque<>(); while (pre[t] != null) { ret.addFirst(pre[t]); t = pre[t].u.id; } return ret; } private void init(){ setAll(len,i -> inf()); setAll(arr,i -> i); setAll(rev,i -> i); size = n; } private boolean isEmpty(){ return size == 0; } private void set(int i,L l){ if (size <= rev[i] || len[i].compareTo(l) <= 0) return; len[i] = l; heapfy(rev[i]); } private int poll(){ int ret = arr[0]; heapfy(swap(0,--size)); return ret; } private void heapfy(int k){ int p = k -1 >>1; if (0 <= p && len[arr[p]].compareTo(len[arr[k]]) > 0) { heapfy(swap(p,k)); return; } int c = k <<1 |1; if (size <= c) return; if (c +1 < size && len[arr[c +1]].compareTo(len[arr[c]]) < 0) c++; if (len[arr[c]].compareTo(len[arr[k]]) < 0) heapfy(swap(c,k)); } private int swap(int i,int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; rev[arr[i]] = i; rev[arr[j]] = j; return i; } } class Edge extends Nd{ Node u,v; L val; Edge(int id,Node u,Node v,L val){ super(id); this.u = u; this.v = v; this.val = val; } @Override public String toString(){ return "(" +u.id +"," +v.id +")"; } } class Node extends Nd{ Node p,hp; Node(int id){ super(id); } @Override public String toString(){ return "" +id; } } class Nd{ int id,l,r; Nd(int id){ this.id = id; } } class Graph { public int n; List> es; Node[] nds; private List>> go,back; public Graph(int n,boolean dir){ this.n = n; nds = new Node[n]; go = new ArrayList<>(); back = dir ? new ArrayList<>() : go; for (int i = 0;i < n;i++) { nds[i] = new Node(i); go.add(new ArrayList<>()); back.add(new ArrayList<>()); } es = new ArrayList<>(); } public void addEdge(int u,int v){ addEdge(u,v,null); } public void addEdge(int u,int v,L l){ Edge e = new Edge<>(es.size(),nds[u],nds[v],l); es.add(e); go.get(u).add(e); back.get(v).add(new Edge<>(e.id,e.v,e.u,e.val)); } public List> go(int ui){ return go.get(ui); } public List> back(int ui){ return back.get(ui); } } class Util{ static char[] arrC(int N,IntUnaryOperator f){ char[] ret = new char[N]; for (int i = 0;i < N;i++) ret[i] = (char) f.applyAsInt(i); return ret; } static int[] arrI(int N,IntUnaryOperator f){ int[] ret = new int[N]; setAll(ret,f); return ret; } static long[] arrL(int N,IntToLongFunction f){ long[] ret = new long[N]; setAll(ret,f); return ret; } static double[] arrD(int N,IntToDoubleFunction f){ double[] ret = new double[N]; setAll(ret,f); return ret; } static T[] arr(T[] arr,IntFunction f){ setAll(arr,f); return arr; } } class MyReader{ private byte[] buf = new byte[1 <<16]; private int ptr = 0; private int tail = 0; private InputStream in; MyReader(InputStream in){ this.in = in; } private byte read(){ if (ptr == tail) try { tail = in.read(buf); ptr = 0; } catch (IOException e) {} return buf[ptr++]; } private boolean isPrintable(byte c){ return 32 < c && c < 127; } private byte nextPrintable(){ byte ret = read(); while (!isPrintable(ret)) ret = read(); return ret; } int it(){ return toIntExact(lg()); } int[] it(int N){ return Util.arrI(N,i -> it()); } int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); } int idx(){ return it() -1; } int[] idx(int N){ return Util.arrI(N,i -> idx()); } int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); } long lg(){ byte i = nextPrintable(); boolean negative = i == 45; long n = negative ? 0 : i -'0'; while (isPrintable(i = read())) n = 10 *n +i -'0'; return negative ? -n : n; } long[] lg(int N){ return Util.arrL(N,i -> lg()); } long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); } double dbl(){ return Double.parseDouble(str()); } double[] dbl(int N){ return Util.arrD(N,i -> dbl()); } double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); } char[] ch(){ return str().toCharArray(); } char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); } String line(){ StringBuilder sb = new StringBuilder(); for (byte c;(c = read()) != '\n';) sb.append((char) c); return sb.toString(); } String str(){ StringBuilder sb = new StringBuilder(); sb.append((char) nextPrintable()); for (byte c;isPrintable(c = read());) sb.append((char) c); return sb.toString(); } String[] str(int N){ return Util.arr(new String[N],i -> str()); } } class MyWriter{ OutputStream out; byte[] buf = new byte[1 <<16]; byte[] ibuf = new byte[20]; int tail = 0; MyWriter(OutputStream out){ this.out = out; } void flush(){ try { out.write(buf,0,tail); tail = 0; } catch (IOException e) { e.printStackTrace(); } } protected void ln(){ write((byte) '\n'); } private void write(byte b){ buf[tail++] = b; if (tail == buf.length) flush(); } private void write(byte[] b,int off,int len){ for (int i = off;i < off +len;i++) write(b[i]); } private void write(long n){ if (n < 0) { n = -n; write((byte) '-'); } int i = ibuf.length; do { ibuf[--i] = (byte) (n %10 +'0'); n /= 10; } while (n > 0); write(ibuf,i,ibuf.length -i); } private void print(Object obj){ if (obj instanceof Boolean) print((boolean) obj ? Solver.yes : Solver.no); else if (obj instanceof Integer) write((int) obj); else if (obj instanceof Long) write((long) obj); else if (obj instanceof char[] cs) for (char b:cs) write((byte) b); else if (obj.getClass().isArray()) { int l = Array.getLength(obj); for (int i = 0;i < l;i++) { print(Array.get(obj,i)); if (i +1 < l) write((byte) ' '); } } else print(Objects.toString(obj).toCharArray()); } void println(Object obj){ if (obj == null) return; if (obj instanceof Collection co) for (Object e:co) println(e); else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) { int l = Array.getLength(obj); for (int i = 0;i < l;i++) println(Array.get(obj,i)); } else { print(obj); ln(); } } void printlns(Object... o){ print(o); ln(); } } class Main{ public static void main(String[] args) throws Exception{ new Solver(){ public void exe(){ out.println(solve()); // Optional.ofNullable(solve()).ifPresent(System.out::println); out.flush(); log.println(elapsed()); } }.exe(); } }