← 返回题目列表

Codeforces · 774/E

E. 大数和余数

中文机器翻译题面 查看原题

Stepan 有一个非常大的正整数。

让我们考虑 Stepan 整数的所有循环移位(如果我们像看字符串一样查看他的整数),它们也是整数(即它们没有前导零)。我们将这种转变称为良好的转变。例如,对于整数 10203,好的移位是整数本身 10203 以及整数 20310 和 31020。

Stepan 想知道所有好的移位中除以给定数字 m 的最小余数。你的任务是确定除以 m 的最小余数。

输入

第一行包含 Stepan 拥有的整数。 Stepan 整数的长度介于 2 到 200 000 位数字之间(含 2 和 200 000 位数字)。保证 Stepan 的整数不包含前导零。

第二行包含整数 m (2 ≤ m ≤ 108) — Stepan 将其整数的良好移位除以的数字。

输出

打印 Stepan 将其整数的所有良好移位除以给定数字 m 时可以得到的最小余数。

示例

输入 #1

521
3

输出 #1

2

输入 #2

1001
5

输出 #2

0

输入 #3

5678901234567890123456789
10000

输出 #3

123

注意

在第一个示例中,整数 521 的所有良好移位(良好移位等于 521、215 和 152)除以 3 时具有相同的余数 2。

在第二个示例中,只有两个好的移位:Stepan 整数本身和向右移位一位。整数本身是 1001,除以 5 后的余数等于 1。向右移动一位等于 1100,除以 5 后的余数等于 0,这是可能的最小余数。