GameOfInterval

Fox Ciel is playing a single-player game called the 'Game of Interval'.

In this problem an interval is a non-empty segment of consecutive integers. We will use the notation [lo,hi] to denote an interval of all numbers x such that lo <= x <= hi. For example, [1,1] is an interval containing the number 1, and [3,5] is an interval containing the numbers 3, 4, and 5. In other words, [3,5] is the set {3,4,5}.

The union of intervals is simply the set union. Note that the union of two intervals is not necessarily an interval. For example, the union of [1,1] and [3,5] is the set {1,3,4,5} which is not an interval, but the union of [1,1], [3,5], and [2,2] is an interval: the interval [1,5].

Initially, Fox Ciel has n cards: for each i from 0 to n-1, inclusive, there is a card that contains the interval [i,i].

Ciel starts playing the game by choosing a non-negative integer k.

Then, she can do the following operation k times:

1. Choose two different cards that contain intervals I1 and I2 such that their union is again an interval.
2. Create a new card with the interval that is the union of I1 and I2. (You also keep the two original cards.)

For example, if n = 4, Ciel can proceed as follows:

1. She chooses k = 2.
2. She chooses the cards with intervals [1,1] and [2,2] and produces a card with the interval [1,2].
3. She then chooses the cards with intervals [1,2] and [3,3] and produces a card with the interval [1,3].
4. Thus, she now has six cards: the original four with [0,0], [1,1], [2,2], and [3,3], and the two new ones with [1,2] and [1,3].

Once Ciel finishes merging the intervals, we will calculate the penalty p as follows:

Suppose we ask Ciel to show us some cards such that the union of their intervals is exactly the interval [L,R]. Let c(L,R) be the smallest number of cards Ciel needs to show. The penalty p is the largest of all values c(L,R). The maximum is taken over all pairs (L,R) such that 0 <= L <= R <= n-1.

Intuitively, if Ciel chooses a very small k, the penalty p will be large. For example, if she chooses k = 0, the penalty will be p = n because she'll need to show n cards for the pair (L,R) = (0,n-1). On the other hand, if she prepares a lot of cards, the penalty will be small. In particular, if she prepares all possible cards, the penalty will be p = 1.

Ciel's final score in this game is defined as s = k + p * n. Help Ciel play the game in a way that will result in a reasonably small score. Note that you don't have to find the best possible score: any solution with a score that does not exceed 6415 will be accepted.

Use a base-36 encoding when outputting your solution, as described below. We will use digits and uppercase letters. The individual symbols have the following values: '0' = 0, '9' = 9, 'A' = 10, 'Z' = 35. Any number between 0 and n-1 can now be expressed as a number in base-36 with exactly two digits. For example, 4 is "04" and 84 is "2C" (as 84 = 2*36 + 12). An interval [L,R] can be represented as the concatenation of L and R. For example, [0,83] will be "002B".

Output a String of length 4*k: the concatenation of the k intervals you want to produce, in the order in which you'll produce them. For example, if k = 3 and these intervals are [1,2], [2,3], [1,3], then you should output "010202030103". The value of k must not exceed 4500. (I.e., the length of your output must not exceed 4500*4 = 18000). We guarantee the solution always exist under these constraints.