Input
123123
1
2->00
Output
10031003
Input
123123
1
3->
Output
1212
Input
222
2
2->0
0->7
Output
777
Input
1000000008
0
Output
1