{"problem":{"name":"E. Big Number and Remainder","description":{"content":"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 ze","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF774E"},"statements":[{"statement_type":"Markdown","content":"Stepan has a very big positive integer.\n\nLet'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.\n\nStepan 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_.\n\n## Input\n\nThe 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.\n\nThe second line contains the integer _m_ (2 ≤ _m_ ≤ 108) — the number by which Stepan divides good shifts of his integer.\n\n## Output\n\nPrint the minimum remainder which Stepan can get if he divides all good shifts of his integer by the given number _m_.\n\n[samples]\n\n## Note\n\nIn 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.\n\nIn 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.","is_translate":false,"language":"English"}],"meta":{"iden":"CF774E","tags":["math","number theory"],"sample_group":[["521\n3","2"],["1001\n5","0"],["5678901234567890123456789\n10000","123"]],"created_at":"2026-03-03 11:00:39"}}