codeforces#P774E. Big Number and Remainder
Big Number and Remainder
Description
Stepan has a very big positive integer.
Let's consider all cyclic shifts of Stepan's integer (if we look at his integer like at a string) which are also integers (i.e. they do not have leading zeros). Let's call such shifts as good shifts. For example, for the integer 10203 the good shifts are the integer itself 10203 and integers 20310 and 31020.
Stepan wants to know the minimum remainder of the division by the given number m among all good shifts. Your task is to determine the minimum remainder of the division by m.
The first line contains the integer which Stepan has. The length of Stepan's integer is between 2 and 200 000 digits, inclusive. It is guaranteed that Stepan's integer does not contain leading zeros.
The second line contains the integer m (2 ≤ m ≤ 108) — the number by which Stepan divides good shifts of his integer.
Print the minimum remainder which Stepan can get if he divides all good shifts of his integer by the given number m.
Input
The first line contains the integer which Stepan has. The length of Stepan's integer is between 2 and 200 000 digits, inclusive. It is guaranteed that Stepan's integer does not contain leading zeros.
The second line contains the integer m (2 ≤ m ≤ 108) — the number by which Stepan divides good shifts of his integer.
Output
Print the minimum remainder which Stepan can get if he divides all good shifts of his integer by the given number m.
Samples
521
3
2
1001
5
0
5678901234567890123456789
10000
123
Note
In the first example all good shifts of the integer 521 (good shifts are equal to 521, 215 and 152) has same remainder 2 when dividing by 3.
In the second example there are only two good shifts: the Stepan's integer itself and the shift by one position to the right. The integer itself is 1001 and the remainder after dividing it by 5 equals 1. The shift by one position to the right equals to 1100 and the remainder after dividing it by 5 equals 0, which is the minimum possible remainder.