DifferenceSequence

Note that this problem has an unusual TIME AND MEMORY limits: 6 seconds and only 48 MB.

Let A be a vector of length n consisting of non-negative integers. We define f(A) to be a vector of length n of absolute differences of consecutive elements in cyclic order. That is:

f(A) = { abs(A[1]-A[0]), abs(A[2] - A[1]), abs(A[3] - A[2]), ..., abs(A[n-1] - A[n-2]), abs(A[0] - A[n-1]) }.

Let g_A be the sequence defined by iteration of f on A, that is

• g_A(0) = A
• g_A(k) = f( g_A(k-1) ) for all positive integers k

For example, if A = g_A(0) = [2, 1, 0], then g_A(1) = [1, 1, 2], g_A(2) = [0, 1, 1], g_A(3) = [1, 0, 1], g_A(4) = [1, 1, 0], g_A(5) = [0, 1, 1] and so on.

It can be shown that each sequence g_A is eventually periodic, that is, for every A there exist positive integers p and q such that g_A(m) = g_A(m+p) for all m >= q. In the above example, we can pick p = 3 and q = 2.

We denote by r(A) the lexicographically largest element of g_A(m) over all m >= q. In other words, r(A) is the lexicographically largest among the elements that appear in g_A infinitely many times. The vector r(A) is called the representative of A. In the above example, r(A) = [1, 1, 0].

Consider the set of all representatives of vectors of non-negative integers of length n. Return the k-th lexicographically smallest of them (1-based index). If there are fewer than k distinct representatives for the given n, return an empty long[] instead.