• Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
Wednesday, February 1, 2023
  • Login
Zeroplusfour
No Result
View All Result
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
No Result
View All Result
Zeroplusfour
No Result
View All Result
Home Code Solutions Hackerrank Algorithms

String Transmission – HackerRank Solution

String Transmission - HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

admin by admin
August 24, 2022
Reading Time: 1 min read
0
15 Days to learn SQL Hard SQL(Advanced)-Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution alt text

Spread the love

Table of Contents

  • String Transmission  – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
  • Solutions of Algorithms Data Structures Hard HackerRank:
    • Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
  • C++ replace HackerRank Solution
  • Java rep HackerRank Solution
  • Python 3 rep HackerRank Solution
  • Python 2 rep HackerRank Solution
  • C rep HackerRank Solution
    • Warmup Implementation Strings Sorting Search Graph Theory Greedy Dynamic Programming Constructive Algorithms Bit Manipulation Recursion Game Theory NP Complete Debugging
    • Leave a comment below
      • Related posts:

String Transmission  – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Solutions of Algorithms Data Structures Hard HackerRank:

Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts

C++ replace HackerRank Solution


Copy Code Copied Use a different Browser

#include <cstdio>
#include <cstring>

const int mod = 1000000007;

#define MAXN 1005

int T, N, K;
char b[ MAXN ];

int c[ MAXN ][ MAXN ];
int cnt[ MAXN ][ 2 ];
int dp[ MAXN ];
int p[ MAXN ];

int main( void )
{
  scanf( "%d", &T );

  for( int i = 0; i < MAXN; ++i ) {
    for( int j = 0; j < MAXN; ++j ) {
      if( j > i ) continue;
      if( i == 0 ) { c[i][j] = 1; continue; }
      c[i][j] = c[i-1][j] + c[i-1][j-1];
      if( c[i][j] > mod ) c[i][j] -= mod;
    }
  }

  while( T-- ) {
    scanf( "%d%d", &N, &K );
    scanf( "%s", b );

    for( int i = 1; i < N; ++i )
      p[i] = 0;

    int periodic = 0;

    for( int i = 1; i < N; ++i ) {
      if( N % i != 0 ) continue;

      for( int j = 0; j < i; ++j ) 
	cnt[j][0] = cnt[j][1] = 0;

      for( int j = 0; j < N; ++j )
	cnt[j%i][1-b[j]+'0']++;

      for( int j = 0; j <= K; ++j )
	dp[j] = 1;

      for( int j = 0; j < i; ++j ) {
	for( int k = K; k >= 0; --k ) {
	  dp[k] = ( !cnt[j][0] || !cnt[j][1] ) ? dp[k] : 0;
	  if( k >= cnt[j][0] && cnt[j][0] ) dp[k] += dp[k-cnt[j][0]];
	  if( k >= cnt[j][1] && cnt[j][1] ) dp[k] += dp[k-cnt[j][1]];
	  if( dp[k] > mod ) dp[k] -= mod;
	}
      }

      p[i] = dp[K];

      for( int j = 1; j < i; ++j ) {
	if( i % j == 0 ) p[i] = p[i] + mod - p[j];
	if( p[i] > mod ) p[i] -= mod;
      }

      periodic += p[i];
      if( periodic >= mod ) periodic -= mod;
    }

    int total = 0;

    for( int i = 0; i <= K; ++i ) {
      total += c[N][i];
      if( total >= mod ) total -= mod;
    }

    int Sol = total - periodic + mod;
    if( Sol >= mod ) Sol -= mod;

    printf( "%d\n", Sol );
  }

  return 0;
}

Java rep HackerRank Solution


Copy Code Copied Use a different Browser

import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Solution implements Runnable {

    // leave empty to read from stdin/stdout
    private static final String TASK_NAME_FOR_IO = "";

    // file names
    private static final String FILE_IN = TASK_NAME_FOR_IO + ".in";
    private static final String FILE_OUT = TASK_NAME_FOR_IO + ".out";

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tokenizer = new StringTokenizer("");

    public static void main(String[] args) {
        new Solution().run();
    }

    final long MOD = 1000000007L;

    int N_MAX = 1005;
    long[][] cnk = new long[N_MAX][N_MAX];

    private void solve() throws IOException {
        for (int n = 0; n < N_MAX; n++) {
            cnk[n][0] = 1;
            cnk[n][n] = 1;
            for (int k = 1; k < n; k++) {
                cnk[n][k] = cnk[n - 1][k - 1] + cnk[n - 1][k];
                cnk[n][k] %= MOD;
            }
        }

        /*
        System.out.println("int[][] COEFF = new int[][] {");
        for (int n = 0; n <= 1000; n++) {
            fastPrecalc(n);
        }
        System.out.println("};");
        */

        /*
        Random r = new Random();
        for (int n = 1; n <= 50; n++) {
            System.out.println("N=" + n);
            for (int d = 0; d <= 4; d++)
                for (int attempts = 0; attempts < 20; attempts++) {
                    long mask = r.nextLong() & (1L << 3);

                    String maskC = "";

                    long num = mask;
                    for (int j = 0; j < n; j++) {
                        maskC += num & 1;
                        num >>= 1;
                    }

                    long a = naive(n, d, maskC.toCharArray());
                    long b = fast(n, d, maskC.toCharArray());

                    if (a != b) {
                        System.err.println(n + " - " + d + " - " + maskC + "(" + a + " vs. " + b + ", delta " + (a - b) + ")");
                    }
                }
        }

        for (int n = 1; n <= 1000; n++) {
            String maskC = "";
            for (int j = 0; j < n; j++) {
                maskC += "1";
            }

            long b = fast(n, 0, maskC.toCharArray());
            if (b > 0) {
                System.err.println(n + " - " + b);
            }
        }
        */

        int tc = nextInt();
        for (int tcIdx = 0; tcIdx < tc; tcIdx++) {
            int n = nextInt();
            int maxD = nextInt();
            char[] c = nextToken().toCharArray();

            out.println(fast(n, maxD, c));
        }
    }

    static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    static int MAX_GCD_NUM = 1005;
    static int[][] GCD_STATIC = new int[MAX_GCD_NUM][MAX_GCD_NUM];

    static {
        for (int i = 0; i < MAX_GCD_NUM; i++)
            for (int j = 0; j <= i; j++) {
                int g = gcd(i, j);
                GCD_STATIC[i][j] = g;
                GCD_STATIC[j][i] = g;
            }
    }

    @SuppressWarnings({"UnusedDeclaration"})
    private long notFastEnough(int n, int maxD, char[] c) {

        int cnt = 0;
        for (int period = 1; period < n; period++) {
            if (n % period == 0) {
                cnt++;
            }
        }

        int[] periods = new int[cnt];
        {
            int idx = 0;
            for (int period = 1; period < n; period++)
                if (n % period == 0) {
                    periods[idx++] = period;
                }
        }

        long[] periodicAnswer = new long[n];
        for (int i = 0; i < cnt; i++) {
            periodicAnswer[periods[i]] = countPeriodic(n, maxD, periods[i], c);
        }

        // calculate total
        long total = 0;
        for (int i = 0; i <= maxD; i++) {
            total += cnk[n][i];
            total %= MOD;
        }

        // calculate partial gcd
        int lBits = cnt / 2;
        int lBits2 = 1 << lBits;
        int[] lGcd = new int[lBits2];

        {
            for (int mask = 0; mask < lBits2; mask++) {
                int common = -1;
                for (int i = 0; i < lBits; i++)
                    if ((mask & (1 << i)) != 0) {
                        common = (common == -1) ? periods[i] : GCD_STATIC[common][periods[i]];
                        if (common == 1) {
                            break;
                        }
                    }
                lGcd[mask] = common;
            }
        }

        int rBits = cnt - lBits;
        int rBits2 = 1 << rBits;

        int[] rGcd = new int[rBits2];
        {
            for (int mask = 0; mask < rBits2; mask++) {
                int common = -1;
                for (int i = 0; i < rBits; i++)
                    if ((mask & (1 << i)) != 0) {
                        common = (common == -1) ? periods[i + lBits] : GCD_STATIC[common][periods[i + lBits]];
                        if (common == 1) {
                            break;
                        }
                    }
                rGcd[mask] = common;
            }
        }

        long cnt2 = 1L << cnt;
        for (long mask = 1; mask < cnt2; mask++) {
            // determine sign by the number of bits in the mask
            int sign = (bitCount(mask) & 1) == 0 ? 1 : -1;

            // fast calculate gcd by analysing left and right part
            int gcdLeft = lGcd[(int) (mask & (lBits2 - 1))];
            int gcdRight = rGcd[(int) (mask >> lBits)];

            int common;
            if (gcdLeft == -1) {
                common = gcdRight;
            } else if (gcdRight == -1) {
                common = gcdLeft;
            } else {
                common = GCD_STATIC[gcdLeft][gcdRight];
            }

            /*
            int common = -1;
            for (int i = 0; i < cnt; i++)
                if ((mask & (1 << i)) != 0) {
                    common = (common == -1) ? periods[i] : GCD_STATIC[common][periods[i]];
                    if (common == 1) {
                        break;
                    }
                }
                */

            total += sign * periodicAnswer[common];
            total %= MOD;
        }

        total %= MOD;
        total += MOD;
        total %= MOD;

        return total;
    }

    private long fast(int n, int maxD, char[] c) {

        int cnt = 0;
        for (int period = 1; period < n; period++) {
            if (n % period == 0) {
                cnt++;
            }
        }

        int[] periods = new int[cnt];
        {
            int idx = 0;
            for (int period = 1; period < n; period++)
                if (n % period == 0) {
                    periods[idx++] = period;
                }
        }

        long[] periodicAnswer = new long[n];
        for (int i = 0; i < cnt; i++) {
            periodicAnswer[i] = countPeriodic(n, maxD, periods[i], c);
        }

        // calculate total
        long total = 0;
        for (int i = 0; i <= maxD; i++) {
            total += cnk[n][i];
            total %= MOD;
        }

        int[] coeff = COEFF[n];
        if (coeff.length != cnt) {
            throw new IllegalStateException("INVALID STATE");
        }

        for (int i = 0; i < cnt; i++) {
            total += coeff[i] * periodicAnswer[i];
            total %= MOD;
        }

        total %= MOD;
        total += MOD;
        total %= MOD;

        return total;
    }

    int[][] COEFF = new int[][] {
      {},
      {},
      {-1,},
      {-1,},
      {0,-1,},
      {-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,-1,},
      {0,-1,},
      {1,-1,-1,},
      {-1,},
      {0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,-1,},
      {-1,},
      {0,0,1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,1,0,-1,-1,},
      {0,-1,},
      {1,-1,-1,},
      {0,0,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,},
      {0,0,0,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,0,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {0,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,1,0,-1,-1,},
      {0,-1,},
      {0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {0,0,0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,-1,0,1,0,1,1,-1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {0,1,0,-1,-1,},
      {0,0,0,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {0,0,1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,1,0,-1,0,-1,},
      {0,0,0,-1,},
      {1,-1,-1,},
      {-1,},
      {0,-1,0,1,1,0,-1,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,},
      {0,0,-1,0,1,1,0,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,1,0,-1,-1,},
      {-1,},
      {0,0,1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,0,0,1,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,1,0,-1,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,1,0,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,-1,0,0,1,0,1,0,1,-1,0,-1,-1,},
      {0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,-1,},
      {0,0,-1,1,0,1,0,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,-1,0,1,1,0,-1,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,1,0,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,-1,1,0,0,1,1,-1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {0,0,0,-1,0,1,1,1,-1,-1,-1,},
      {-1,},
      {0,0,1,-1,0,0,-1,},
      {0,1,-1,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,-1,0,0,1,1,0,0,-1,1,0,-1,-1,},
      {0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,0,-1,-1,},
      {0,0,0,1,0,-1,0,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,-1,0,0,1,0,1,0,1,-1,0,-1,-1,},
      {-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,0,1,0,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,0,0,1,-1,0,-1,},
      {-1,},
      {0,0,-1,1,1,0,-1,0,1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,0,1,0,-1,0,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,-1,1,-1,1,1,1,1,-1,1,-1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,-1,1,0,1,0,-1,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,1,0,-1,0,-1,},
      {0,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,},
      {0,0,-1,1,1,0,-1,0,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
      {-1,},
      {0,0,1,-1,-1,},
      {0,0,0,0,-1,},
      {0,1,-1,0,-1,},
      {0,0,1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {0,0,0,0,1,-1,-1,},
      {-1,},
      {0,0,0,0,-1,0,0,1,0,1,0,0,-1,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,0,0,0,0,0,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,-1,1,0,1,0,-1,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,-1,0,1,0,1,0,-1,0,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {0,0,0,0,0,-1,0,0,1,1,0,1,-1,-1,-1,},
      {-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,1,0,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,-1,0,0,1,0,0,1,1,0,-1,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {0,0,0,0,-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {0,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,-1,0,0,1,0,1,1,-1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {1,-1,-1,},
      {0,0,-1,1,1,0,-1,0,1,-1,-1,},
      {-1,},
      {0,-1,1,0,0,1,1,-1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,-1,0,1,1,0,-1,0,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {0,-1,0,0,1,1,1,0,-1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,-1,1,1,-1,1,1,-1,1,1,-1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,-1,0,0,1,0,1,0,0,-1,1,0,-1,-1,},
      {-1,},
      {0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,-1,1,0,1,0,-1,1,-1,0,-1,},
      {1,-1,-1,},
      {0,0,-1,1,1,-1,0,0,1,-1,-1,},
      {0,0,-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {0,0,-1,0,1,0,1,1,-1,-1,-1,},
      {0,0,1,0,-1,0,-1,},
      {0,0,0,0,0,1,0,-1,0,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,0,1,-1,0,-1,-1,},
      {0,-1,},
      {1,-1,-1,},
      {0,0,1,-1,-1,},
      {0,-1,1,0,0,1,1,-1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {0,1,-1,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,0,0,1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,-1,0,1,0,1,0,-1,1,-1,-1,},
      {-1,},
      {0,-1,1,0,1,0,-1,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {1,-1,-1,-1,1,1,-1,1,1,-1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,-1,0,0,1,1,0,0,-1,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,0,0,0,1,0,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,-1,0,1,1,0,-1,0,0,1,0,-1,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {0,0,-1,1,1,-1,0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,1,0,-1,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,},
      {0,1,0,-1,0,-1,0,-1,1,-1,0,1,0,1,1,0,1,-1,1,-1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,1,-1,0,0,-1,},
      {0,1,0,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
      {0,0,0,0,1,0,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
      {-1,},
      {0,0,0,0,0,0,0,-1,0,0,1,1,0,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,0,-1,0,1,1,0,-1,0,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {0,0,1,0,-1,0,-1,},
      {0,-1,1,0,1,-1,0,1,-1,0,-1,},
      {-1,},
      {1,-1,-1,1,-1,-1,1,1,1,1,-1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,-1,0,1,0,1,0,-1,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,0,-1,-1,},
      {0,-1,1,0,1,0,-1,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,0,0,0,1,-1,0,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,1,-1,-1,},
      {-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {0,0,0,-1,0,1,1,1,-1,-1,-1,},
      {-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,-1,0,1,0,1,1,-1,0,-1,-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,0,0,-1,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,0,1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,-1,},
      {0,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
      {-1,},
      {0,0,-1,1,1,-1,0,0,1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {0,0,-1,0,1,0,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,-1,0,0,1,0,1,0,0,-1,0,1,0,-1,-1,},
      {0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,-1,1,0,1,0,-1,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,1,0,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,1,0,-1,0,0,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,1,-1,-1,1,1,1,1,-1,-1,1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {0,0,-1,1,0,0,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,-1,0,1,1,0,-1,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {0,0,-1,1,1,-1,0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,-1,0,0,1,0,0,0,1,1,0,-1,-1,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,1,0,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,},
      {1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
      {-1,},
      {0,-1,1,0,0,1,1,-1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,0,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {-1,},
      {0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,-1,1,0,1,-1,0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {0,-1,0,1,0,1,1,-1,0,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,-1,0,1,1,0,-1,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {-1,},
      {0,0,0,0,-1,0,1,0,1,0,-1,0,1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {0,0,1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,1,0,-1,0,0,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,-1,0,1,0,1,0,-1,0,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,0,-1,0,1,0,0,0,1,1,-1,0,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,-1,1,0,1,-1,0,1,-1,0,-1,},
      {0,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,-1,0,0,1,1,0,0,-1,0,0,1,0,-1,-1,},
      {0,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {0,0,1,0,-1,0,-1,0,0,-1,1,-1,1,0,1,1,1,0,-1,1,-1,-1,-1,},
      {-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {0,1,0,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,-1,1,0,1,0,-1,1,-1,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {0,0,-1,1,0,1,0,-1,1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {0,1,-1,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,1,0,-1,0,-1,-1,0,1,0,1,-1,1,0,1,0,-1,1,1,-1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,-1,1,1,-1,0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,0,-1,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,1,0,-1,-1,},
      {0,0,0,0,1,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,-1,0,1,1,0,-1,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {0,-1,0,1,0,1,1,-1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,-1,0,1,1,-1,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,-1,0,1,0,0,0,1,1,-1,-1,0,-1,},
      {-1,},
      {0,0,0,0,-1,0,1,0,1,0,-1,0,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,1,0,-1,0,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,1,-1,1,-1,1,1,-1,1,-1,1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,1,0,1,0,0,1,-1,0,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {0,0,0,0,-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,-1,0,1,0,0,0,1,1,-1,0,-1,0,-1,},
      {0,0,0,0,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {0,0,0,-1,0,1,1,1,-1,-1,-1,},
      {0,0,0,0,1,0,-1,0,0,0,-1,},
      {1,-1,-1,},
      {0,0,-1,1,1,-1,0,0,1,-1,-1,},
      {-1,},
      {0,-1,1,0,1,-1,0,1,-1,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,-1,0,1,1,-1,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,-1,1,0,0,1,1,-1,-1,0,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,-1,0,1,1,1,-1,-1,-1,},
      {-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,0,-1,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,-1,0,1,1,0,-1,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,-1,1,-1,1,1,1,1,-1,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {0,0,-1,1,1,-1,0,0,1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,1,0,-1,0,-1,-1,1,0,0,1,-1,1,0,1,-1,0,1,1,-1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,-1,0,0,1,0,1,0,0,-1,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,},
      {1,-1,-1,1,-1,1,-1,1,1,-1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,-1,0,0,1,1,0,1,-1,-1,-1,},
      {-1,},
      {0,-1,1,0,1,-1,0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,-1,0,1,0,1,0,-1,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,0,1,1,-1,0,-1,-1,},
      {0,-1,1,0,1,-1,0,1,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,1,-1,0,0,-1,},
      {0,0,-1,0,1,1,0,1,-1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,-1,0,1,1,0,-1,0,0,0,1,0,-1,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,1,0,-1,0,0,-1,},
      {0,1,0,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,-1,1,0,0,1,1,-1,-1,0,-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,1,0,0,0,-1,0,-1,0,0,-1,0,1,-1,0,0,1,0,1,1,0,1,0,-1,1,-1,0,-1,-1,},
      {0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,1,-1,-1,},
      {0,0,-1,1,1,-1,0,0,1,-1,-1,},
      {0,0,1,-1,-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {1,-1,-1,},
      {0,0,-1,1,0,1,0,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,-1,0,1,1,0,-1,1,0,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {-1,},
      {1,-1,-1,1,-1,-1,1,1,1,1,-1,-1,1,-1,-1,},
      {-1,},
      {0,-1,1,0,1,-1,0,1,-1,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,-1,},
      {0,-1,1,0,1,-1,0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {0,1,-1,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,0,1,0,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,-1,0,0,1,0,0,1,0,0,-1,1,0,-1,0,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,-1,1,0,1,0,-1,1,-1,-1,},
      {-1,},
      {0,-1,1,0,0,1,1,-1,-1,0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,-1,0,1,1,-1,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,0,0,0,1,0,-1,0,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,-1,1,-1,1,1,1,1,-1,1,-1,-1,-1,},
      {-1,},
      {0,0,0,0,0,-1,0,1,0,1,0,-1,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {0,0,0,0,-1,0,1,1,0,0,-1,0,1,-1,-1,},
      {-1,},
      {0,0,-1,0,1,0,1,0,-1,0,1,0,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,1,0,-1,-1,0,0,1,-1,0,-1,1,0,1,1,1,0,-1,-1,1,0,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,0,0,0,1,0,-1,0,0,0,-1,},
      {-1,},
      {1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,-1,-1,},
      {0,1,0,-1,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {0,0,0,0,0,0,0,-1,0,0,1,0,1,0,0,-1,0,0,0,1,0,-1,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,-1,1,0,1,-1,0,1,-1,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {0,0,0,0,-1,0,0,1,0,1,1,0,-1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {1,-1,-1,},
      {0,0,-1,1,0,1,0,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,-1,0,1,0,0,1,0,-1,1,0,-1,0,-1,},
      {-1,},
      {0,0,-1,1,1,-1,0,0,1,-1,-1,},
      {1,-1,-1,},
      {0,1,-1,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,0,1,0,1,-1,0,-1,-1,},
      {0,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {1,-1,-1,1,-1,1,1,-1,-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,1,-1,0,0,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {-1,},
      {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {1,-1,-1,},
      {0,0,-1,0,1,1,0,1,-1,-1,-1,},
      {0,0,0,1,-1,0,0,0,-1,},
      {-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,0,0,0,0,0,-1,0,1,0,0,1,1,-1,-1,0,-1,},
      {0,1,-1,0,-1,},
      {1,-1,-1,},
      {-1,},
      {0,0,0,-1,0,1,1,-1,0,0,0,1,0,-1,-1,},
      {1,-1,-1,},
      {-1,1,1,1,-1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {0,-1,1,0,0,1,1,-1,-1,0,-1,},
      {1,-1,-1,},
      {0,0,1,0,-1,-1,0,0,-1,1,0,1,-1,1,0,1,-1,1,0,1,-1,-1,-1,},
      {-1,},
      {0,0,0,0,1,0,-1,0,0,0,-1,},
      {1,-1,-1,},
      {-1,1,1,-1,1,-1,-1,},
      {1,-1,-1,},
      {0,-1,0,1,1,-1,0,1,0,-1,-1,},
      {-1,},
      {1,-1,-1,},
      {0,0,1,-1,0,0,-1,},
      {0,0,0,0,0,0,0,0,0,0,1,0,-1,0,-1,},
    };

    private void fastPrecalc(int n) {

        int cnt = 0;
        for (int period = 1; period < n; period++) {
            if (n % period == 0) {
                cnt++;
            }
        }

        int[] periods = new int[cnt];
        {
            int idx = 0;
            for (int period = 1; period < n; period++)
                if (n % period == 0) {
                    periods[idx++] = period;
                }
        }

        if (cnt > 30) {
            System.err.println("N = " + n + ", CNT = " + cnt);
        }

        long cnt2 = 1L << cnt;
        long[] coeff = new long[cnt];
        for (long mask = 1; mask < cnt2; mask++) {
            // determine sign by the number of bits in the mask
            int sign = (bitCount(mask) & 1) == 0 ? 1 : -1;

            int common = -1;
            for (int i = 0; i < cnt; i++)
                if ((mask & (1L << i)) != 0) {
                    common = (common == -1) ? periods[i] : gcd(common, periods[i]);
                    if (common == 1) {
                        break;
                    }
                }

            int j = -1;
            for (int i = 0; i < cnt; i++)
                if (periods[i] == common) {
                    j = i;
                    break;
                }

            coeff[j] += sign;
        }

        System.out.print("  {");
        for (int i = 0; i < cnt; i++) {
            System.out.print(coeff[i] + ",");
        }
        System.out.println("},");
    }

    private long countPeriodic(int n, int maxD, int period, char[] c) {
        int[] zeroes = new int[period];
        int[] ones = new int[period];
        for (int i = 0; i < period; i++) {
            int j = i;
            while (j < n) {
                if (c[j] != '0') {
                    ones[i]++;
                } else {
                    zeroes[i]++;
                }
                j += period;
            }
        }

        long[][] d = new long[period + 1][maxD + 1];
        d[0][maxD] = 1;
        for (int i = 0; i < period; i++)
            for (int remD = 0; remD <= maxD; remD++)
                if (d[i][remD] > 0) {
                    // replace zeroes with ones
                    if (remD - zeroes[i] >= 0) {
                        d[i + 1][remD - zeroes[i]] += d[i][remD];
                        d[i + 1][remD - zeroes[i]] %= MOD;
                    }

                    // replace ones with zeroes
                    if (remD - ones[i] >= 0) {
                        d[i + 1][remD - ones[i]] += d[i][remD];
                        d[i + 1][remD - ones[i]] %= MOD;
                    }
                }

        long result = 0;
        for (int i = 0; i <= maxD; i++) {
            result += d[period][i];
            result %= MOD;
        }
        return result;
    }

    @SuppressWarnings({"UnusedDeclaration"})
    private long naive(int n, int maxD, char[] c) {
        return naive3(n, maxD, toMask(c));
    }

    private boolean isPeriodic(int n, long mask) {
        for (int period = 1; period < n; period++)
            if (n % period == 0 && isPeriodic(n, mask, period)) {
                return true;
            }
        return false;
    }

    private boolean isPeriodic(int n, long mask, int period) {
        for (int i = 0; i < period; i++) {
            boolean bitHere = (mask & (1L << i)) != 0;

            int j = i;
            while (j < n) {
                boolean bitThere = (mask & (1L << j)) != 0;
                if (bitHere != bitThere) {
                    return false;
                }
                j += period;
            }
        }

        return true;
    }

    @SuppressWarnings({"UnusedDeclaration"})
    private long naive1(int n, int maxD, long c) {
        long result = 0;
        long n2 = 1 << n;
        for (long mask = 0; mask < n2; mask++) {
            if (distinctBits(n, mask, c) <= maxD && !isPeriodic(n, mask)) {
                result++;
            }
        }
        return result;
    }

    @SuppressWarnings({"UnusedDeclaration"})
    private long naive2(int n, int maxD, long c) {
        Set<Long> periodic = new HashSet<Long>();

        // count only periodic
        for (int periodLength = 1; periodLength < n; periodLength++)
            if (n % periodLength == 0) {
                int periodTimes = n / periodLength;

                // brute force period mask
                long p2 = 1L << periodLength;
                for (long pMask = 0; pMask < p2; pMask++) {
                    // calculate overall mask
                    long totalMask = 0;
                    for (int i = 0; i < periodTimes; i++) {
                        totalMask <<= periodLength;
                        totalMask |= pMask;
                    }

                    // see if it is applicable
                    if (distinctBits(n, totalMask, c) <= maxD) {
                        periodic.add(totalMask);
                    }
                }
            }

        int total = 0;
        for (int k = 0; k <= maxD; k++) {
            total += cnk[n][k];
        }

        return total - periodic.size();
    }

    private long naive3(int n, int maxD, long c) {
        long total = 0;
        for (int k = 0; k <= maxD; k++) {
            total += cnk[n][k];
        }

        return total - periodicGen(0, n, maxD, c);
    }

    private long periodicGen(int pos, int n, int maxD, long c) {
        if (pos >= n) {
            return isPeriodic(n, c) ? 1 : 0;
        }
        long total = periodicGen(pos + 1, n, maxD, c);
        if (maxD > 0) {
            total += periodicGen(pos + 1, n, maxD - 1, c ^ (1L << pos));
        }
        return total;
    }

    static int BIT_COUNT_LIMIT_POW = 18;
    static int BIT_COUNT_LIMIT_MASK = (1 << BIT_COUNT_LIMIT_POW) - 1;
    static int[] BIT_COUNT = new int[1 << BIT_COUNT_LIMIT_POW];

    static {
        for (int i = 1; i < BIT_COUNT.length; i++)
            BIT_COUNT[i] = BIT_COUNT[i & (i - 1)] + 1;
    }

    @SuppressWarnings({"UnusedParameters"})
    private int distinctBits(int n, long m1, long m2) {
        return bitCount(m1 ^ m2);
    }

    private int bitCount(long mask) {
        return BIT_COUNT[(int) (mask & BIT_COUNT_LIMIT_MASK)] + BIT_COUNT[(int) ((mask >> BIT_COUNT_LIMIT_POW) & BIT_COUNT_LIMIT_MASK)];
    }

    private long toMask(char[] c) {
        long result = 0;
        for (char v : c) {
            result <<= 1;
            result += v - '0';
        }
        return result;
    }

    public void run() {
        long timeStart = System.currentTimeMillis();

        boolean fileIO = TASK_NAME_FOR_IO.length() > 0;
        try {

            if (fileIO) {
                in = new BufferedReader(new FileReader(FILE_IN));
                out = new PrintWriter(new FileWriter(FILE_OUT));
            } else {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }

            solve();

            in.close();
            out.close();
        } catch (IOException e) {
            throw new IllegalStateException(e);
        }
        long timeEnd = System.currentTimeMillis();

        if (fileIO) {
            System.out.println("Time spent: " + (timeEnd - timeStart) + " ms");
        }
    }

    private String nextToken() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) {
                return null;
            }
            tokenizer = new StringTokenizer(line);
        }
        return tokenizer.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

}

 



Python 3 rep HackerRank Solution


Copy Code Copied Use a different Browser

 



Python 2 rep HackerRank Solution


Copy Code Copied Use a different Browser



import math
MODULUS = 1000000007
def countFact(n,p):
    k=0
    while n>=p:
    
        k+=n/p
        n/=p
    
    return k


def pow(a,b,MOD):
    x=1
    y=a 
    while b > 0 :
        if b%2 == 1:
            x=(x*y);
            if(x>MOD):
                x%=MOD;
        y = (y*y);
        if(y>MOD): y%=MOD 
        b /= 2;
    return x;

#     Modular Multiplicative Inverse
#    Using Euler's Theorem
#    a^(phi(m)) = 1 (mod m)
#    a^(-1) = a^(m-2) (mod m) 
def InverseEuler(n,MOD):
    return pow(n,MOD-2,MOD);

def factMOD(n,MOD):
    res = 1; 
    while (n > 0):
        iter=2
        m=n%MOD
        while iter<=m:
            res = (res * iter) % MOD;
            iter=iter+1
        n=n/MOD
        if (n%2 > 0): 
            res = MOD - res;
    return res;

def C(n,r,MOD):
    if (countFact(n, MOD) > countFact(r, MOD) + countFact(n-r, MOD)):
        return 0;
    return (factMOD(n, MOD) *
            ((InverseEuler(factMOD(r, MOD), MOD) * 
            InverseEuler(factMOD(n-r, MOD), MOD)) % MOD)) % MOD;

def binomial(n, k):
    if not 0 <= k <= n:
        return 0
    if k == 0 or k == n:
        return 1
    P = k+1
    for i in xrange(k+2, n+1):
        P *= i
    return P/math.factorial(n-k)

def numSubsets(arr,sumN):
    if sumN == 0:
        return 0;
    if sumN < 0:
        return 0;
       
    a = [[0]*sumN for x in xrange(len(arr)+1)]
    
    for i in range(sumN):
        a[0][i] = 1    
    for i in range(1,len(arr)+1):
        for j in range(sumN):

            if j-arr[i-1] >= 0 :
                a[i][j] = (a[i-1][j] + a[i-1][j-arr[i-1]])%MODULUS
            else:
                a[i][j] = a[i-1][j]            
    return a[len(arr)][sumN-1]


t = input()
for i in range(t):
    inp = raw_input()
    arr = inp.split()
    n = int(arr[0])
    k = int(arr[1])
    stringTransmit = raw_input()
    bigsome = 0
    periods = [0]    
    for period in range(1,n):
        if n%period != 0:
            periods.append(0)
            continue
        else:            
            subsetBag = []
            tempK= k
            for j in range(period):
                numzeroes = 0
                pointer = j
                while pointer < n:
                    if stringTransmit[pointer] == '0':
                        numzeroes=numzeroes + 1
                    pointer = pointer + period
                numones = n/period - numzeroes
                if (numzeroes<numones):
                    tempK = tempK - numzeroes
                    subsetBag.append(numones - numzeroes)
                else:
                    tempK = tempK - numones
                    subsetBag.append(numzeroes - numones)
            numSub = numSubsets(subsetBag,tempK+1)            
            for iter in range(1,period):
                if period%iter==0:
                    numSub = numSub - periods[iter]
            bigsome = (bigsome + numSub)% MODULUS
            periods.append(numSub)
    
    allReachable = 1
    val = 1
    for i in range(1,k+1):
        val = ((val*(n-(i-1)))*InverseEuler(i,MODULUS))%MODULUS
        allReachable = (allReachable + val)%MODULUS
    print (allReachable-bigsome)%MODULUS            
                
             



C rep HackerRank Solution


Copy Code Copied Use a different Browser

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define DEBUG 0

#if DEBUG
#define TRACE(...) fprintf(stdout, __VA_ARGS__)
#else
#define TRACE(...) 
#endif

/*
 * Modular arithmetic
 */
#define MOD 1000000007
typedef unsigned long mpz_t;

#define mpz_init(var)                  __mpz_init(&(var))
#define mpz_clear(var)                 __mpz_clear(&(var))
#define mpz_set(var, value)            __mpz_set(&(var), (value))
#define mpz_set_ui(var, value)         __mpz_set_ui(&(var), (value))
#define mpz_add(sum, add1, add2)       __mpz_add(&(sum), (add1), (add2))
#define mpz_neg(neg, val)              __mpz_neg(&(neg), (val))
#define mpz_sub(diff, sub1, sub2)      __mpz_sub(&(diff), (sub1), (sub2))
#define mpz_mul(prod, mul1, mul2)      __mpz_mul(&(prod), (mul1), (mul2))
#define mpz_mul_ui(prod, mul1, mul2)   __mpz_mul(&(prod), (mul1), (mul2))
#define mpz_pow_ui(res, base, pow)     __mpz_pow_ui(&(res), (base), (pow))
#define mpz_ui_pow_ui(res, base, pow)  __mpz_ui_pow_ui(&(res), (base), (pow))
#define mpz_inv(inv, val)              __mpz_inv(&(inv), val)
#define mpz_div(quot, div, divs)       __mpz_div(&(quot), (div), (divs))
#define mpz_bin_uiui(res, n, m)        __mpz_bin_uiui(&(res), (n), m)

void __mpz_init(mpz_t *var)
{
    *var = 0;
}

void __mpz_clear(mpz_t *var)
{
    *var = 0;
}

void __mpz_set(mpz_t *var, mpz_t value)
{
    *var = value;
}

void __mpz_set_ui(mpz_t *var, unsigned long int value)
{
    *var = value % MOD;
}

void __mpz_add(mpz_t *sum, mpz_t add1, mpz_t add2)
{
    *sum = (add1 + add2);
    if (*sum >= MOD) *sum -= MOD;
}

void __mpz_neg(mpz_t *neg, mpz_t val)
{
    *neg = MOD - val;
}

void __mpz_sub(mpz_t *diff, mpz_t sub1, mpz_t sub2)
{
    mpz_t tmp;

    mpz_neg(tmp, sub2);
    __mpz_add(diff, sub1, tmp);
}

void __mpz_mul(mpz_t *prod, mpz_t mul1, mpz_t mul2)
{
    unsigned long long tmp = (mul1 * mul2); 
    if (tmp >= MOD) tmp %= MOD;
    *prod = (mpz_t)tmp;
}

void __mpz_mul_ui(mpz_t *prod, mpz_t mul1, unsigned long mul2)
{
    unsigned long long tmp = (mul1 * mul2);
    if (tmp >= MOD) tmp %= MOD;
    *prod = (mpz_t)tmp;
}

void __mpz_pow_ui(mpz_t *res, mpz_t base, unsigned long pow)
{
    unsigned long long tmp = 1;
    unsigned long long a = base;

    while (pow) {
        if (pow & 1) {
            tmp *= a;
            if (tmp >= MOD) tmp %= MOD;
            pow --;
        } else {
            a *= a;
            if (a >= MOD) a %= MOD;
            pow >>=1;
        }
    }

    *res = tmp;
}

void __mpz_ui_pow_ui(mpz_t *res, unsigned long base, unsigned long pow)
{
    mpz_t tmp;

    mpz_set_ui(tmp, base);
    __mpz_pow_ui(res, tmp, pow);
}

void __mpz_inv(mpz_t *inv, mpz_t val)
{
    __mpz_pow_ui(inv, val, MOD-2);
}

void __mpz_div(mpz_t *quot, mpz_t div, mpz_t divs)
{
    mpz_t tmp;

    __mpz_inv(&tmp, divs);
    __mpz_mul(quot, div, tmp);
}

#define MAX_NM 1024
void __mpz_bin_uiui(mpz_t *res, unsigned long n, unsigned long m)
{
    unsigned long long numer;
    unsigned long long denom;
    unsigned long i;

    static mpz_t cache[MAX_NM][MAX_NM];

    if (n < MAX_NM && m < MAX_NM && cache[n][m]) {
        *res = cache[n][m];
        return;
    }

    numer = 1;
    denom = 1;

    if (m > n/2) {
        for (i = m + 1; i <= n; i++) {
            numer *= i;
            if (numer >= MOD * 1000ULL) numer %= MOD;
        }
 
        for (i=1; i <= (n - m); i++) {
            denom *= i;
            if (denom >= MOD * 1000ULL) denom %= MOD;
        }
    } else {
        for (i = n - m + 1; i <= n; i++) {
            numer *= i;
             if (numer >= MOD * 1000ULL) numer %= MOD;
        }

        for (i=1; i <= m; i++) {
            denom *= i;
            if (denom >= MOD * 1000ULL) denom %= MOD;
         }
    }

    numer %= MOD;
    denom %= MOD;

    __mpz_div(res, numer, denom);

    if (n < MAX_NM && m < MAX_NM) {
        cache[n][m] = *res;
    }
}

void
array_print(int n, const int *a)
{
    int i;
    TRACE("[");
    if (n > 0) {
        TRACE("%d", a[0]);
        for (i = 1; i < n; i++) {
            TRACE(", %d", a[i]);
        }
    }
    TRACE("]\n");
}

void 
run_print(int n_runs, const int runs[], const int counts[]) 
{
    int i;

    TRACE("[");
    if (n_runs > 0) {
        TRACE("%dx%d", runs[0], counts[runs[0]]);
        for (i = 1; i < n_runs; i++) {
            TRACE(",  %dx%d", runs[i], counts[runs[i]]);
        }
    }
    TRACE("]\n");
}

void
repr_print(int n_runs, const int repr[], const int runs[])
{
    int i;
    int first = 1;

    for (i = 0; i < n_runs; i++) {
        if (repr[i]) {
            if (first) {
                TRACE("%dx%d", runs[i], repr[i]);
                first = 0;
            } else {
                TRACE(" + %dx%d", runs[i], repr[i]);
            }
        }
    }
    TRACE("\n");
}

int int_asc(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int int_desc(const void *a, const void *b)
{
    return *(int *)b - *(int *)a;
}

/* Create an list of all divisors of the number n, not exceeding n */
int *
get_periods(int n, int *n_divisors)
{
    int *divisors;
    int max_divisors = ceil(sqrt(n)) * 2;
    int i, d, r;

    divisors = malloc(max_divisors * sizeof(int));
    if (divisors == NULL) {
        TRACE("Not enough memory for divisors\n");
        return divisors;
    }

    memset(divisors, 0, max_divisors * sizeof(int));

    divisors[0] = 1;
    *n_divisors = 1;

    for (i = 2; i < n; i++) {
        d = n / i;
        r = n % i;
        if ( d < i ) break; /* We are past sqrt(n) */
        if ( r ) continue;  /* Not a dvisor */
        divisors[(*n_divisors)++] = i;
        if ( d > i ) {
            divisors[(*n_divisors)++] = d;
        }
    }

    qsort(divisors, *n_divisors, sizeof(int), int_asc);

    TRACE("Divisors: ");
    array_print(*n_divisors, divisors);

    return divisors;
}

int *
compute_diffs(int n, const int *m, int p, 
              int *min_flips, int *max_flips)
{   
    int i, j, np;
    int ones, zeroes;
    int *diffs;

    diffs = malloc(p * sizeof(int));
    if (diffs == NULL) {
        return diffs;
    }

    np = n / p;
    *min_flips = 0;
    *max_flips = 0;

    /* Get the counts */
    for (i = 0; i < p; i++) {
        ones = 0;
        for (j = i; j < n; j += p) {
            ones += m[j];
        }
        zeroes = np - ones;

        if (ones < zeroes) {
            *min_flips += ones;
            *max_flips += zeroes;
            diffs[i] = zeroes - ones;
        } else {
            *min_flips += zeroes;
            *max_flips += ones;
            diffs[i] = ones - zeroes;
        };
    }

    TRACE("Distance: %d..%d (%d)\n", 
          *min_flips, *max_flips, *max_flips - *min_flips);
    TRACE("Flip Counts (raw): ");
    array_print(p, diffs);

    return diffs;
}

/*
 * Compress the array of diffs (increments) using RLE. 
 * runs[i] is a sorted (in descending order) list of all different values 
 *         from diff[]
 * count[run[i]] contains the number of given elements in diff[]
 * sums[i] contains the sum of runs[j]*count[runs[j]] for j = i..n_runs
 */
int
compress_diffs(int p, int *diffs, int **runs, int **counts, int **sums)
{
    int n_runs;
    int i;
    int last_sum;

    /* Sort flip counts in descending order */
    qsort(diffs, p, sizeof(int), int_desc);
    
    *runs = malloc(p * sizeof(int));
    *sums = malloc(p * sizeof(int));
    *counts = malloc((diffs[0] + 1) * sizeof(int));
    
    if ((*runs == NULL) || (*sums == NULL) || (*counts == NULL)) {
        return -1;
    }

    memset(*counts, 0, sizeof(int) * (diffs[0] + 1));

    n_runs    = 1;
    (*runs)[0]   = diffs[0];
    (*counts)[diffs[0]] = 1;

    /* RLE Compression */
    for (i = 1; i < p; i++) {
        if (diffs[i] == (*runs)[n_runs-1]) {
            (*counts)[diffs[i]]++;
        } else {
            (*runs)[n_runs] = diffs[i];
            (*counts)[diffs[i]] = 1;
            n_runs++;
        }
    }

    /* Computing the sums of the runs */
    last_sum = 0;
    for (i = n_runs-1; i >= 0; i--) {
        last_sum += (*runs)[i] * (*counts)[(*runs)[i]];
        (*sums)[i] = last_sum;
    }

    TRACE("Compressed diffs: %d runs\n", n_runs);
    for (i = 0; i < n_runs; i++) {
        TRACE("[%d:  %d]  (%d)\n", 
              (*runs)[i], (*counts)[(*runs)[i]], (*sums)[i]);
    }

    return n_runs;
}

/*
 * Get the first representaiton of the number n
 *
 * Return TRUE if success, 0 if failure
 */
int 
get_first(int n, int n_runs,  
          const int runs[], 
          const int counts[], 
          const int sums[], 
          int       repr[])
{
    int max_n;
    int rem;
    int i, j;
    int do_trace = 0;

    /* If n is bigger the sum of all the elements, no way */
    if (n > sums[0]) {
        if (do_trace) {
            TRACE("%d is too big for ", n);
            run_print(n_runs, runs, counts);
        }
        return 0;
    }

    /* 
     * Opitmization in case of 1 element.
     * It must be the multiple of runs[0] and less than or equal to
     * runs[0] * counts[runs[0]]
     */
    if (n_runs == 1) {
        if (n % runs[0] == 0) {
            if (n / runs[0] <= counts[runs[0]]) {
                repr[0] = n / runs[0];
                if (do_trace) {
                    TRACE("%d = ", n);
                    repr_print(n_runs, repr, runs);
                }
                return 1;
            } else { 
                /* Would be OK, but the number's too big, We should not
                 * be getting there, due to the check n > sums[0] above */
                if (1) {
                    TRACE("****** %d cannot be represented using ", n);
                    run_print(n_runs, runs, counts);         
                }
                return 0;
            }           
        } else {
            /* Unfortunately, that was the only option */
            if (do_trace) {
                TRACE("%d cannot be represented using ", n);
                run_print(n_runs, runs, counts);         
            }
            return 0;
        }
    }

    /* Start from the biggest value and attempt to go down */
    for (i = 0; i < n_runs; i++) {
        max_n = n / runs[i];
        if (counts[runs[i]] < max_n) {
            max_n = counts[runs[i]];
        }
        for (j = max_n; j > 0; j--) {
            rem = n - runs[i] * j;
            if (rem == 0) { 
                /* The number fit perfectly */
                repr[i] = j;
                if (do_trace) {
                    TRACE("%d = ", n); repr_print(n_runs, repr, runs);
                }
                return 1;
            } else {
                /* We still have enough smaller elements to try to split rem */
                if ((i < n_runs - 1) && (sums[i+1] >= rem)) {
                    if (get_first(rem, n_runs-i-1, 
                                  runs+i+1, counts, sums+i+1, repr+i+1)) {
                        repr[i] = j;
                        if (do_trace) {
                            TRACE("%d = ", n); repr_print(n_runs, repr, runs);
                        }
                        return 1;
                    }
                }
            }
        }
    }

    if (do_trace) {
        TRACE("%d cannot be represented using ", n);
        run_print(n_runs, runs, counts);
    }

    return 0;
}

/*
 * Get the first representation of the number n
 *
 * Return TRUE if success, 0 if failure
 */
int 
get_next(int n, int n_runs,  
         const int runs[], 
         const int counts[], 
         const int sums[], 
         int        repr[])
{
    int i, j, sum;
    int do_trace = 0;

    /* If there is only 1 element in runs[], there is no next representation */
    if (n_runs > 1) {
        sum = runs[n_runs - 1] * repr[n_runs - 1];
        repr[n_runs - 1] = 0;
        for (i = n_runs - 2; i >= 0; i --) {
            for (j = repr[i] - 1; j >= 0; j--) {
                /*
                 * If we can represent sum + runs[i] * j using
                 * runs[i+1 .. n_runs, that's our next representation
                 */
                sum += runs[i];
                repr[i]--;
                if (get_first(sum, n_runs - i - 1, 
                              runs + i + 1, counts, sums + i + 1,
                              repr + i + 1)) {
                    if (do_trace) {
                        TRACE("%d = ", n);
                        repr_print(n_runs, repr, runs);
                    }
                    return 1;
                }
            }
        }
    }

    TRACE("No more representations for %d\n", n);
    return 0;
}

/*
 * get_variants: calculate the number of variants for a particular 
 * representation
 */
void
get_variants(mpz_t *variants, const int repr[], 
             int n_runs, const int runs[], const int counts[]) 
{
    int i;
    mpz_t c;

    mpz_set_ui(*variants, 1); 
    mpz_init(c);

    for(i = 0; i < n_runs; i++) {
        if (repr[i]) { /* Small optimization for C(0, n) = 1 */
            mpz_bin_uiui(c, counts[runs[i]], repr[i]);
            mpz_mul(*variants, *variants, c);
        }
    }
}
    
/*
 * THe REAL Workhorse. Similar to get_number_of_sums but works on a filetered
 * set, where runs[0] <= n and runs[n_runs-1] > 0
 *
 * The idea is to generate the sums in the sorted order. 
 *
 * S1 = a0 + a1 +...+ an, where a[i] >= a[i+1]
 * S2 = b0 + b1 +...+ bm, where b[i] >= b[i+1]
 *
 * S2 follows S1 if for i=0..min(m,n) b[i] <= a[i]
 *
 * We first generate the "biggest" run, taking as big numbers from runs[] as
 * possible (and as many as possible) and then work ourselves up.
 */
int
get_number_of_sums_real(int n, int n_runs, 
                        const int runs[], 
                        const int counts[], 
                        const int sums[], 
                        mpz_t *s_count)
{
    int *repr;  /* n = runs[0]*repr[0] + ... + runs[n_runs-1]*repr[n_runs-1] */
    mpz_t variants;

    mpz_init(variants);
    mpz_set_ui(*s_count, 0);

    repr = malloc(n_runs * sizeof(int));
    memset(repr, 0, n_runs * sizeof(int));

    if (get_first(n, n_runs, runs, counts, sums, repr)) {
        get_variants(&variants, repr, n_runs, runs, counts);

        TRACE("First representation for %d = ", n);
        repr_print(n_runs, repr, runs);
        TRACE("%lu variants for this representation\n", variants);

        mpz_add(*s_count, *s_count, variants);

        while(get_next(n, n_runs, runs, counts, sums, repr)) {
            get_variants(&variants, repr, n_runs, runs, counts);

            TRACE("Next representation for %d = ", n);
            repr_print(n_runs, repr, runs);
            TRACE("%lu variants for this representation\n", variants);

            mpz_add(*s_count, *s_count, variants);
        }
    } else {
        TRACE("%d cannot be represented using ", n);
        run_print(n_runs, runs, counts);
    }

    TRACE("TOTAL Variants for %d is %lu\n", n, *s_count);

    mpz_clear(variants);
    free(repr);

    return 0;
}

/*
 * Get number of sums.
 * Calculate the number of ways a number n can be represented using
 * the numbers runs[0]..runs[n_runs-1] when you have counts[runs[i]] of each
 *
 * The routine will first attempt to reduce the runs by:
 *    b) eliminating those runs[i] that are greater than n
 *    c) eliminating cases, where the number cannot be represented
 * After that the work is passed to the real routine
 */
int
get_number_of_sums(int n, int n_runs, 
                   const int *runs, 
                   const int *counts, 
                   const int *sums, 
                   mpz_t *s_count)
{
    int   i;

    /* Deal with the case n==0 -- it can be an empty set */
    if (n == 0) {
        mpz_set_ui(*s_count, 1);
        return 0;
    }

    /* Eliminate runs that are too big */
    for (i = 0; i < n_runs; i++) {
        if (runs[i] <= n) break;
    }

    if (i == n_runs) {
        TRACE("The smallest element %d > %d\n", runs[n_runs - 1], n);
        mpz_set_ui(*s_count, 0);
        return 0;
    }
     
    if (sums[i] < n) {
        TRACE("The sum of suitable elements is %d < %d\n", sums[i], n);
        mpz_set_ui(*s_count, 0);
        return 0;
    }
    
    // TRACE("Using runs %d..%d for number %d\n", i, n_runs-1, n);

    get_number_of_sums_real(n, n_runs-i, runs+i, counts, sums+i, s_count);

    return 0;
}
 
int
get_periodics(mpz_t *count, int n, const int *m, int k, int p)
{
    int ret = 0;
    int min_flips, max_flips;
    int i;
    int *diffs = NULL;
    int *runs= NULL;
    int *counts = NULL;
    int *sums = NULL;
    int n_runs;
    mpz_t s_count;
    mpz_t zero_mul;

    TRACE("\nComputing the periodics for n=%d, p=%d\n", n, p);

    mpz_set_ui(*count, 0);
    mpz_init(s_count);
    mpz_init(zero_mul);

    /* 
     * Compute the max and the min distance to the periodic message,
     * as well as the array of possible increments (from min to max)
     * The size of the array is always p
     */
    diffs = compute_diffs(n, m, p, &min_flips, &max_flips);

    if (diffs) {
        /* Quick check before we go any further */
        if (k >= min_flips) {

            /* Compress the runs using RLE */
            n_runs = compress_diffs(p, diffs, &runs, &counts, &sums);

            if (n_runs > 0) {
                /* Deal with zeros (if any) */
                mpz_ui_pow_ui(zero_mul, 2, counts[0]);
                if (counts[0]) {
                    n_runs--;  /* Forget about zeros */
                    TRACE("%d zeroes will result in multiplier %lu\n",
                          counts[0], zero_mul);
                }

                /*
                 * Now our task is reduced to figuring out the number of
                 * ways a number (i - min_flips), where i=0..k
                 * can be represented as a sum of a subset of nummbers from 
                 * diffs[] (but we'll use the compresed representation)
                 */                
                for (i = 0; i <= k - min_flips; i++) {
                    get_number_of_sums(i, n_runs, runs, counts, sums, &s_count);
                    mpz_add(*count, *count, s_count);
                }

                TRACE("Counts for period %d (no zeroes): %lu\n", p, *count);
                
                mpz_mul(*count, *count, zero_mul);
            } else {
                ret = -1;
                TRACE("Diffs compression failed");
            }
        } else {
            TRACE("No messages with period %d at distance 0..%d\n", p, k);
        }
    } else {
        ret = -1;
        TRACE("Could not compute the diffs\n");
    }

    if (sums)   free(sums);
    if (counts) free(counts);
    if (runs)   free(runs);
    if (diffs)  free(diffs);
    mpz_clear(s_count);
    mpz_clear(zero_mul);

    TRACE("Total count for period %d is %lu\n", p, *count);
    return ret;
}

void 
remove_duplicate_counts(int n_periods, const int periods[], mpz_t periodics[])
{
    int i, j;
    int p;

    TRACE("\nCounts for periods (with duplicates):\n");
    for (i = 0; i < n_periods; i++) {
        TRACE("Period %3d: %lu\n", periods[i], periodics[i]);
    }

    for (i = 0; i < n_periods; i++) {
        p = periods[i];
        for (j = i + 1; j < n_periods; j++) {
            if (periods[j] % p == 0) {
                mpz_sub(periodics[j], periodics[j], periodics[i]);
            }
        }
    }

    TRACE("\nCounts for periods (without duplicates):\n");
    for (i = 0; i < n_periods; i++) {
        TRACE("Period %3d: %lu\n", periods[i], periodics[i]);
    }

}

void
solve_st(int n, const int *m, int k)
{
    int    i;
    mpz_t  mcount, c;

    int   *periods = NULL;    /* Possible values of periods (divisors of n) */
    int    n_periods;         /* Number of possible periods */

    mpz_t  *periodics = NULL; /* Number of messages with period periods[i] */

    /*
     * Messages of length 1 are a special case. They are always non-periodic
     */
    if (n == 1) {
        printf("%d\n", 1<<k);
        return;
    }

    /* 
     * Calculate the total number of messages within the Hamming sphere
     * with the radius k (Hamming distance = 0..k)
     * 
     *     k
     *   -----
     *   \      i
     *    >    C 
     *   /      n
     *   -----
     *   i = 0
     */
    mpz_init(mcount);
    mpz_init(c);

    for (i = 0; i <= k; i++) {
        mpz_bin_uiui(c, n, i); 
        TRACE("C(%d, %d) = %lu\n", i, n, c);
        mpz_add(mcount, mcount, c);
    }

    TRACE("Total number of messages: %lu\n", mcount);

    periods = get_periods(n, &n_periods);
    if (periods == NULL) {
        return;
    }
    
    periodics = malloc(n_periods * sizeof(mpz_t));
    if (periodics == NULL) {
        free(periods);
        return;
    }

    /* 
     * Compute the number of periodic messages within the Hamming Sphere 
     * of the Radius=k for each of the possible period lengths
     */
    for (i = 0; i < n_periods; i++) {
        mpz_init(periodics[i]);
        if (get_periodics(&(periodics[i]), n, m, k, periods[i])) {
            TRACE("Problem computing for period %d\n", periods[i]);
            goto cleanup;
        }
    }

    /*
     * The values, computed in previous steps are excessive. If p2 = i * p1
     * then the counts for p2 include the counts for p1 as well. 
     * Thus, we need to post_process the counts to remove duplicates
     */
    remove_duplicate_counts(n_periods, periods, periodics);

    /*
     * Now, we need to subtract all these counts from mcount
     */
    mpz_set_ui(c, 0);
    for (i = 0; i < n_periods; i++) {
        mpz_add(c, c, periodics[i]);
    }

    TRACE("\nTotal number of non-periodic messages:\n%lu - %lu = ", mcount, c);
    mpz_sub(mcount, mcount, c);
    TRACE("%lu\n==========\n", mcount);

    /* Compute the number mod 1000000007 */
    printf("%lu\n", mcount);

cleanup:
    if (periodics) {
        for (i = 0; i < n_periods; i++) {
            mpz_clear(periodics[i]);
        }
        free(periodics);
    }
    if (periods)   free(periods);
    mpz_clear(c);
    mpz_clear(mcount);
}

void 
do_st(void) 
{
    int  n; /* Number of bits in the message  */
    int *m; /* The message (0's and 1's only) */
    int  k; /* Max number of errors */

    int  i;

    scanf("%d %d", &n, &k);
    if (!((1 <= n) && (n <= 1000))) {
        TRACE("Bad message length %d\n", n);
        return;
    }

    if (!((0 <= k) && (k <= n))) {
        TRACE("Bad number of corrupt bits %d\n", k);
        return;
    }

    m = malloc(n * sizeof(int));
    if (m == NULL) {
        TRACE("Out of memory\n");
        return;
    }
    
    for (i = 0; i < n; i++) {
        scanf("%1d", &m[i]);
        if (m[i] != 0 && m[i] != 1) {
            TRACE("Bad message symbol %d", m[i]);
            free(m);
            return;
        }
    }

    TRACE("Message: ");
    array_print(n, m);
    TRACE("K=%d\n", k);

    solve_st(n, m, k);

    free(m);
}

int
main(int argc, char *argv[])
{
    int test_runs;
    int t;

    scanf("%d", &test_runs);
    if (!((1 <= test_runs) && (test_runs <= 20))) {
        return 1;
    }

    for (t = 1; t <= test_runs; t++) {
        TRACE("Test run #%d\n"
              "============\n", t);
        do_st();
    }

    return(0);
}

 

Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging

Leave a comment below

 

Related posts:

15 Days to learn SQL Hard SQL(Advanced)-SolutionString Reduction – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionSherlock and the Valid String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionRecursive Digit Sum – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionLiars – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAccessory Collection – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionIce Cream Parlor – HackerRank Solution
Tags: Cc++14full solutionGoHackerRank Solutionjavajava 15java 7java 8java8javascriptpypy 3Python 2python 3String Transmission
ShareTweetPin
admin

admin

Related Posts

Leetcode All Problems Solutions
Code Solutions

Exclusive Time of Functions – LeetCode Solution

by admin
October 5, 2022
0
30

Exclusive Time of Functions - LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions...

Read more
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
32
Leetcode All Problems Solutions

Course Schedule III – LeetCode Solution

October 5, 2022
25
Leetcode All Problems Solutions

Maximum Product of Three Numbers – LeetCode Solution

September 11, 2022
52
Leetcode All Problems Solutions

Task Scheduler – LeetCode Solution

September 11, 2022
119
Leetcode All Problems Solutions

Valid Triangle Number – LeetCode Solution

September 11, 2022
28
Next Post
15 Days to learn SQL Hard SQL(Advanced)-Solution

Manipulative Numbers- HackerRank Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution

Stone Game- HackerRank Solution

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may also like

15 Days to learn SQL Hard SQL(Advanced)-SolutionString Reduction – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionSherlock and the Valid String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionRecursive Digit Sum – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionLiars – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAccessory Collection – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionIce Cream Parlor – HackerRank Solution

Categories

  • Algorithms
  • Anime
  • Biography
  • Business
  • Code Solutions
  • Cosmos
  • Countdowns
  • Culture
  • Economy
  • Education
  • Entertainment
  • Finance
  • Games
  • Hackerrank
  • Health
  • How to
  • Investment
  • LeetCode
  • Lifestyle
  • LINUX SHELL
  • Manga
  • News
  • Opinion
  • Politics
  • Sports
  • SQL
  • Tech
  • Travel
  • Uncategorized
  • Updates
  • World
  • DMCA
  • Home
  • My account
  • Privacy Policy
  • Top Posts

Recent Blogs

Leetcode All Problems Solutions

Exclusive Time of Functions – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions
Code Solutions

Shortest Unsorted Continuous Subarray – LeetCode Solution

September 11, 2022
4
15 Days to learn SQL Hard SQL(Advanced)-Solution
Algorithms

Demanding Money- HackerRank Solution

May 26, 2022
70
Leetcode All Problems Solutions
Code Solutions

The Skyline Problem – LeetCode Solution

September 5, 2022
144
15 Days to learn SQL Hard SQL(Advanced)-Solution
Algorithms

Sherlock and the Valid String – HackerRank Solution

May 31, 2022
6

© 2022 ZeroPlusFour - Latest News & Blog.

No Result
View All Result
  • Home
  • Category
    • Business
    • Culture
    • Economy
    • Lifestyle
    • Health
    • Travel
    • Opinion
    • Politics
    • Tech
  • Landing Page
  • Support Forum
  • Contact Us

© 2022 ZeroPlusFour - Latest News & Blog.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept All”, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
Cookie SettingsAccept All
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT
Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?