package test; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.HashMap; import java.util.InputMismatchException; import java.util.NoSuchElementException; import java.util.TreeSet; public class Main { public static void main(String[] args) { IO io = new IO(); long n = io.nextLong(); int q = io.nextInt(); int[] x = new int[q]; long[] l = new long[q]; long[] r = new long[q]; for(int i=0;i ts = new TreeSet<>(); ts.add(0L); ts.add((long) n-1); for(int i=0;i map = new HashMap<>(); ArrayList weight = new ArrayList<>(); int ind = 0; long bef = -1; for(Long lg:ts) { if (bef + 1 < lg) { ind++; weight.add(lg - bef - 1); } map.put(lg, ind++); weight.add(1L); bef = lg; } // System.out.println(map); // System.out.println(weight); int m = weight.size(); Splarrraaay[] sp = new Splarrraaay[5]; for(int i=0;i<5;i++) { sp[i] = new Splarrraaay(m, weight); } long[] ans = new long[5]; for(int qq=0;qq max) { max = point[i]; maxi = i; }else if(point[i] == max) { maxi = -1; } } if (maxi >= 0) { ans[maxi] += max; } // System.out.println(Arrays.toString(point)); // System.out.println(maxi + " gain " + max + " points"); }else{ for(int i=0;i<5;i++) { if (x[qq] - 1 == i) { sp[i].add(map.get(l[qq]), map.get(r[qq]) + 1, 1); }else{ sp[i].set(map.get(l[qq]), map.get(r[qq]) + 1, 0); } } } } for(int i=0;i<5;i++) { ans[i] += sp[i].sum(0, m); } for(int i=0;i<5;i++) { if (i > 0) { io.print(" "); } io.print(ans[i] % 1000000009); } io.println(); io.flush(); } } class Splarrraaay { private int size,n; private long[] sum; private long[] weight; private int[] lazy; private long[] lazyValue; public Splarrraaay(int size,ArrayList w) { this.size = size; n = 1; while(n=0;k--) { weight[k] = weight[k*2+1] + weight[k*2+2]; } } private void propagate(int k) { if (k < n - 1) { if (lazy[k] == 1) { //set for(int i=k*2+1;i<=k*2+2;i++) { sum[i] = weight[i] * lazyValue[k]; lazy[i] = 1; lazyValue[i] = lazyValue[k]; } }else if(lazy[k] == 2) { //add for(int i=k*2+1;i<=k*2+2;i++) { sum[i] = (sum[i] + lazyValue[k] * weight[i]); if (lazy[i] == 0) { lazy[i] = 2; lazyValue[i] = lazyValue[k]; }else if(lazy[i] == 1) { lazy[i] = 1; lazyValue[i] += lazyValue[k]; }else{ //lazy[i] = 2; lazyValue[i] += lazyValue[k]; } } } } lazy[k] = 0; } public void set(int begin,int end,long x) { set(begin,end,x,0,0,n); } private void set(int begin,int end,long x,int k,int l,int r) { propagate(k); if (r <= begin || end <= l) { return; } if (begin <= l && r <= end) { sum[k] = x * weight[k]; lazy[k] = 1; lazyValue[k] = x; propagate(k); return; } set(begin,end,x,k*2+1,l,(l+r)>>>1); set(begin,end,x,k*2+2,(l+r)>>>1,r); sum[k] = sum[k*2+1] + sum[k*2+2]; } public void add(int begin,int end,long x) { add(begin,end,x,0,0,n); } public void add(int begin,int end,long x,int k,int l,int r) { propagate(k); if (r <= begin || end <= l) { return; } if (begin <= l && r <= end) { sum[k] = (sum[k] + x * (r - l)); lazy[k] = 2; lazyValue[k] = x; propagate(k); return; } add(begin,end,x,k*2+1,l,(l+r)>>>1); add(begin,end,x,k*2+2,(l+r)>>>1,r); sum[k] = sum[k*2+1] + sum[k*2+2]; } public long sum(int begin,int end) { return sum(begin,end,0,0,n); } private long sum(int begin,int end,int k,int l,int r) { propagate(k); if (r <= begin || end <= l) { return 0; } if (begin <= l && r <= end) { return sum[k]; } sum[k] = sum(begin,end,k*2+1,l,(l+r)/2) + sum(begin,end,k*2+2,(l+r)/2,r); return sum[k]; } //debug public String toString() { ArrayList data = new ArrayList<>(); for(int i=0;i Integer.MAX_VALUE) { throw new NumberFormatException(); } return (int) nl; } public char nextChar() { if (!hasNext()) { throw new NoSuchElementException(); } return (char) readByte(); } public double nextDouble() { return Double.parseDouble(next());} public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i