| Author: | A. Zhuplev | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
There are many special competitions and entertainments for fans during a typical racing weekend. In order to improve attractiveness of circuit racing it was decided to introduce Fortunate ticket lottery as new kind of entertainment. Lottery participants may buy tickets, each ticket numbered with a unique sequence of digits. Additionally, a small integer constant R is randomly selected by lottery organizers and published before the start of the lottery.
Let F(R) denote the maximum number of non-overlapping occurrences of any pattern with length R. The Ticket fortune value T is defined as max{F(i) × i | 1 ≤ i ≤ R}. For instance, if R = 2 and ticket number is 1234125634123412 then F(2) = 4, (because 12 pattern occurs 4 times), F(1) = 4 , so T = 2 × 4 = 8. Let's call the pattern which gives the maximum value of F optimal pattern.
The lottery jackpot is divided between all tickets with the maximum fortune value. To claim the prize, participant must go to the lottery office and show his ticket. Unfortunately, ticket numbers are very long, so to prove that his ticked does indeed have the winning value, he must highlight the optimal pattern in the number.
You program must, given R and a ticket number, find the optimal pattern, and output the number, separating every occurrence of the optimal pattern from the surrounding digits by minus signs (ASCII 45).
If there is more than one optimal pattern, select lexicographically smallest one. If there is more than one way to separate optimal pattern, select one with the leftmost first occurrence, i.e. if number is 222 and optimal pattern is 22, then the answer is 22-2 rather than 2-22.
First line of input file contains a single natural number R.
Second line of input file contains ticket number.
Output file should contain one line — ticket number with highlighted optimal pattern.
1 ≤ R ≤ 9
Number length is between 1 and 5 × 105 digits.
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|