Optimal RLE Re‐Encoding

This problem is about re‐encoding a sequence using a variant of run‐length encoding (RLE). In this scheme, we have an alphabet of n digits, namely \(\Sigma=\{0,1,\dots,n-1\}\). The encoded sequence is a sequence of characters from \(\Sigma\). At any moment a special repetition marker \(e\) is defined (initially, \(e=0\)). The encoding is interpreted as follows:

• Any character a not equal to \(e\) stands for itself.
• If the repetition marker \(e\) appears in the encoding then the next two characters have a special meaning:
  • If it is followed by \(e\,k\) (i.e. the next character is \(e\)), then it represents \(e\) repeated \(k+1\) times.
  • Otherwise, if it is followed by \(b0\) where \(b\ne e\), then the repetition marker is switched to \(b\) (this command does not output any character).
  • Otherwise, if it is followed by \(b\,k\) with \(b\ne e\) and \(k>0\), then it represents the character \(b\) repeated \(k+3\) times.

For example, with \(n=4\) the sequence 1002222223333303020000 can be encoded as 10010230320100302101. Here the decoding is interpreted as follows: The first character 1 is a literal. The next three symbols 001 decode as two 0's (since 0 is currently the repetition marker and \(0\,0\,1\) means \(0\) repeated \(1+1=2\) times). Then 023 yields six 2's, 032 yields five 3's, 010 switches the repetition marker to 1, 0302 outputs itself, and finally 101 encodes four 0's. Note that a sequence may have several valid encodings of different lengths.

Your task is: Given the value of n and an already encoded sequence, find an encoding (following the same rules) that is as short as possible. Output that shortest possible encoding.

inputFormat

The input consists of two lines. The first line is an integer n indicating the size of the alphabet. The second line is a string representing the already encoded sequence. The alphabet is \(\{0, 1, \dots, n-1\}\) and the initial repetition marker is 0.

outputFormat

Output the shortest valid encoding for the original sequence (obtained by decoding the given input) according to the rules described.

sample

4
10010230320100302101

10010230320100302101