KEY PAD DIALING

#include<bits/stdc++.h>
using namespace std;
/*
int n,a[105];

int fun()
{
    bool dp[n+1][sum+1];
    
    for(int i=0;i<=n;i++)
    {
        dp[i][0]=true;
    }
    
    for(int i=1;i<=sum;i++)
    {
          dp[0][i]=false;
        
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=sum;j++)
        {
            if(a[i-1]>j)
              dp[i][j] = dp[i-1][j];
              
            if(j>=a[i-1])
            dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]];
            
        }
    }
    
    return dp[n][sum];
    
}*/



 map<char,string>mp;

void print_str(string number,int i,string ans)
{
    if(i==number.length())
      {
          cout<<ans<<" ";
          return;
      }
      
      string s=mp[number[i]];
      
      for(auto x:s)
      {
          ans+=x;
          print_str(number,i+1,ans);
          ans.erase(ans.length()-1,1);
      }
}







void key_pad_dialing(string number)
{
  
   mp['0']="0";
   mp['1']="1";
   mp['2']="ABC";
   mp['3']="DEF";
   mp['4']="GHI";
   mp['5']="JKL";
   mp['6']="MNO";
   mp['7']="PQRS";
   mp['8']="TUV";
   mp['9']="WXYZ";
   
   string ans="";
   
   print_str(number,0,ans);
    
}
    

int main()
{
     string s; cin>>s;
    
   
    
    key_pad_dialing(s);
    
    
    
}