989. [NOIP 2010冲刺二]符文之语

【题目描述】

当宁采臣 来到兰若寺时，兰若寺已经破败不堪了。但兰若寺的中央有一个光亮如新的石台。宁采臣 走近石台，发现石台上有一个数串，而数串的上方刻着一串古老的符文之语。精通古符文之语的宁采臣 不费吹灰之力就读懂了文章的意思，其大意是：对于石台上的一串数字，你可以在适当的位置加入乘号（设加了 k 个，当然也可不加，即分成 k+1 个部分），设这 k+1 个部分的乘积（如果 k=0 ，则乘积即为原数串的值）对 m 的余数（即 mod m ）为 x ；现求 x 能达到的最小值及该情况下 k 的最小值，以及 x 能达到的最大值及该情况下的 k 的最小值（可以存在 x 的最小值与最大值相同的

情况）。宁采臣 还知道，如果他找到了正确的答案，那么就可以通往兰若寺的下层了。但这个问题似乎不太好解决，宁采臣 就找到了你，并答应找到财宝以后和你二八分 ( 当然你拿二…… ) 。

【输入格式】

第一行为数串，且数串中不存在 0 ；

第二行为 m 。

【输出格式】

四个数，分别为 x 的最小值和该情况下的 k ，以及 x 的最大值和该情况下的 k ，相邻两个数之间用一个空格隔开。

【输入样例】

4421

22

【输出样例】

0 1 21 0

【数据范围】

对于 30% 的数据： 2 ≤字符串长度 L ≤ 50 。

对于 100% 的数据： 2 ≤字符串长度 L ≤ 1000;2 ≤ m ≤ 50 。