package waruagaki; 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<>(); for(int i=0;i map = new HashMap<>(); ArrayList weight = new ArrayList<>(); int ind = 0; long bef = -1; for(Long lg:ts) { map.put(lg, ind++); if (bef != -1) { weight.add(lg - bef); } bef = lg; } weight.add(0L); // System.out.println(map); // System.out.println(weight); int m = weight.size(); Splarrraaay[] sp = new Splarrraaay[5]; for(int i=0;i<5;i++) { // if (i == 0) { sp[i] = new Splarrraaay(m, weight); // }else{ // sp[i] = new Splarrraaay(m, sp[0].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); }else{ sp[i].set(map.get(l[qq]), map.get(r[qq]), 0); } // System.out.println(sp[i]); } } } 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; long[] weight; private byte[] lazy; private int[] 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]; } } public Splarrraaay(int size,long[] w) { this.size = size; n = 1; while(n>>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,int x) { add(begin,end,x,0,0,n); } public void add(int begin,int end,int 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] = 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]; } long ret = sum(begin,end,k*2+1,l,(l+r)/2) + sum(begin,end,k*2+2,(l+r)/2,r); sum[k] = sum[k*2+1] + sum[k*2+2]; return ret; } //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