Mohammad Nour and Marcel are close friends. One day Nour borrowed from Marcel some money.
After a few weeks, Nour decided to return the money to his friend, But unfortunately Marcel forgot how much it was. We all know that Nour is a funny person so he took advantage of this opportunity and decided to play with Marcel.
He gave him a huge number $$$a$$$, and asked him to split this number into at least $$$k$$$ numbers (parts), such that each digit belongs to exactly one part and each part contains no more than 9 consecutive digits
The $$$GCD$$$ of the numbers Marcel got after making the operation above is the amount of money Nour borrowed.
Marcel is a cunning, he wants the answer to be maximal possible, so help him to split the number $$$a$$$ such that the $$$GCD$$$ of its parts as big as possible.
The greatest common divisor, $$$GCD(a,b)$$$, of two positive integers $$$a$$$ and $$$b$$$ is the biggest integer that is a divisor of both $$$a$$$ and $$$b$$$.
Please note that: $$$GCD(0,x) = x$$$
The first line of the input contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le k \le {10^3}, 1 \le n \le {2 \times 10^3} )$$$ the length of $$$a$$$ and the minimum size of numbers Marcel should get.
The second line contains the number $$$a$$$ without leading zeros
Print -1 if Marcel can't split the number according to the conditions above. Otherwise print the maximum amount of money he can get.
8 2 63021002
2
9 3 303252015
15
3 4 150
-1
In the first test case, one of the optimal solutions is dividing the string into $$$630210$$$ and $$$02$$$ such that $$$GCD$$$ of them is $$$2$$$.
In the second test case, you can split the string into $$$30$$$, $$$32520$$$ and $$$15$$$.
