class Solution {
public:

    inline string rotate(string s,int b){
        return s.substr(s.size()-b,b)+s.substr(0,s.size()-b);
    }

    string add(string s,int a){
        string ret;
        for(int i=0;i<s.size();i++){
            if(i%2==1){
                ret+=(char)((s[i]+a-'0')%10+'0');
            }else{
                ret+=s[i];
            }

        }
        return ret;
    }

    void bfs(string s,unordered_map<string,int>& visited, int a, int b){

        queue<string> q;
        q.push(s);

        while(!q.empty()){

            int size=q.size();
            for(int i=0;i<size;i++){

                string str=q.front();
                q.pop();

                visited[str]=1;
                string added=add(str,a);
                string rotated=rotate(str,b);
                if(visited[rotated]!=1){
                    q.push(rotated);
                }
                if(visited[added]!=1){
                    q.push(added);
                }

            }
        }

        return;

    }

    string findLexSmallestString(string s, int a, int b) {

        unordered_map<string,int> visited;

        bfs(s,visited,a,b);

//         for(auto iter:visited){
//             cout<<iter.first<<' ';
//         }


        return visited.begin()->first;
    }
};