Chiaki has just learned hash in today's lesson. A hash function is any function that can be used to map data of arbitrary size to data of fixed size. As a beginner, Chiaki simply chooses a hash table of size n with hash function
%20%3D%20x%20%5Cbmod%20n)
.
Unfortunately, the hash function may map two distinct values to the same hash value. For example, when n = 9 we have h(7) = h(16) = 7. It will cause a failure in the procession of insertion. In this case, Chiaki will check whether the next position
%20%2B%201)%20%5Cbmod%20n)
is available or not. This task will not be finished until an available position is found. If we insert {7, 8, 16} into a hash table of size 9, we will finally get {16, -1, -1, -1, -1, -1, -1, 7, 8}. Available positions are marked as -1.
After done all the exercises, Chiaki became curious to the inverse problem. Can we rebuild the insertion sequence from a hash table? If there are multiple available insertion sequences, Chiaki would like to find the smallest one under lexicographical order.
Sequence a
1, a
2, ..., a
n is lexicographically smaller than sequence b
1, b
2, ..., b
n if and only if there exists i (1 ≤ i ≤ n) satisfy that a
i < b
i and a
j = b
j for all 1 ≤ j < i.