import java.util.*; public class Main { static final int MOD = 1000000007; public static void main (String[] args) { Scanner sc = new Scanner(System.in); long d = sc.nextLong(); int q = sc.nextInt(); PriorityQueue queue = new PriorityQueue<>(); PriorityQueue next = new PriorityQueue<>(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { queue.add(new Work(sc.nextLong(), sc.nextLong())); Work prev = queue.poll(); long max = prev.getCount(); while (queue.size() > 0) { Work x = queue.poll(); if (prev.end >= x.start - 1) { prev.add(x); } else { next.add(prev); prev = x; } max = Math.max(max, prev.getCount()); } sb.append(max).append("\n"); next.add(prev); PriorityQueue tmp = next; next = queue; queue = tmp; } System.out.print(sb); } static class Work implements Comparable { long start; long end; public Work(long start, long end) { this.start = start; this.end = end; } public int compareTo(Work another) { if (start == another.start) { if (end == another.end) { return 0; } else if (end < another.end) { return -1; } else { return 1; } } else { if (start == another.start) { return 0; } else if (start < another.start) { return -1; } else { return 1; } } } public long getCount() { return end - start + 1; } public void add(Work another) { start = Math.min(start, another.start); end = Math.max(end, another.end); } public String toString() { return "start:" + start + " end:" + end; } } }