import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Adv19D4_3 { InputStream is; PrintWriter out; // String INPUT = "2 50\r\n" + // "4 5\r\n" + // ""; String INPUT = ""; // String INPUT = "4 500000 65 66 67 68"; // String INPUT = "6 500000 1 2 3 4 5 6"; // String INPUT = "4 500000 3 4 5 6"; // String INPUT = "18 500000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"; // String INPUT = "10 500000 1 1 1 2 2 3 4 5 6 7"; // String INPUT = "6 500000 5 7 11 13 17 23"; long[][] bit; long ct = 0; void paint(long[] a, int s, int X, int K) { if(K < 32) { for(int i = s;i>>>6 == s>>>6;i+=K) { a[i>>>6] |= 1L<>>6)+1;j <= X>>>6;j++) { // s+ak >= j*64 // a = (j*64-s+k-1)/k long first = (j*64-s+K-1)/K; long ss = s+first*K&63; a[j] |= bit[K][(int)ss]; } // for(int i = s;i <= X;i+=K) { // a[i>>>6] |= 1L<>>6] |= 1L< X) { for(int i = 0;i < X;i++) { out.print(0); } out.println(); return; } } Arrays.sort(a); int[][] f = uniqcount(a); int[] fi = new int[f.length]; for(int i = 0;i < f.length;i++)fi[i] = f[i][1] + 1; Denom de = new Denom(fi); bit = new long[32][32]; for(int i = 1;i < 32;i++) { for(int j = 0;j < i;j++) { for(int k = j;k < 64;k+=i) { bit[i][j] |= 1L< 0;k--) { F /= f[j][0]+1; } } F++; for(int j = 0;j < f.length;j++) { if(de.in(i, j, 1)) { int ni = de.add(i, j, 1); if(i == 0) { dp[ni][f[j][0]>>>6] |= 1L<>>6]<<~k<0) { paint(dp[ni], k*(l+1)+l, F, k); // for(int m = k*(l+1)+l;m <= X;m+=k) { // dp[ni][m>>>6] |= 1L<>>6] |= 1L<>>6]<<~i<0 ? 1 : 0); } out.println(); } public static int[] getind(int[][] a, int ind) { int[] b = new int[a.length]; for(int i = 0;i < a.length;i++)b[i] = a[i][ind]; return b; } public static class Denom { int[] a; int[] ia; Denom(int... ia) { this.ia = ia; int n = ia.length; a = new int[n+1]; a[0] = 1; for(int i = 0;i < n;i++){ a[i+1] = a[i] * ia[i]; } } int[] dec(int code) { int[] ret = new int[a.length-1]; for(int i = 0;i < a.length-1;i++) { ret[i] = code % a[i+1] / a[i]; } return ret; } int ind(int... x) { assert x.length == ia.length; int ret = 0; for(int i = 0;i < x.length;i++){ ret += x[i] * a[i]; } return ret; } boolean in(int code, int which, int plus) { int v = v(code, which); return 0 <= v + plus && v + plus < ia[which]; } int v(int code, int which) { return code / a[which] % ia[which]; } int add(int code, int which, int plus) { return code + a[which] * plus; } int update(int code, int which, int val) { return code + (-code / a[which] % ia[which] + val) * a[which]; } int all() { return a[a.length-1]; } } public static int[][] uniqcount(int[] a) { int n = a.length; int p = 0; int[][] b = new int[n][]; for(int i = 0;i < n;i++){ if(i == 0 || a[i] != a[i-1])b[p++] = new int[]{a[i], 0}; b[p-1][1]++; } return Arrays.copyOf(b, p); } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new Adv19D4_3().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }