1010 Radix

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll convert(string t,ll r){
 ll ans=0;
 for(ll i=0;i<t.length();i++){
  if(isdigit(t[i])){
   ans=ans*r+t[i]-'0';
  }else{
   ans=ans*r+t[i]-'a'+10;
  }
 }
 return ans;
}
void findradix(string s,ll low,ll high,ll n){
 while(low<=high){
  ll mid=(low+high)/2;
  if(convert(s,mid)>n||convert(s,mid)<0){
   high=mid-1;
  }else if(convert(s,mid)<n){
   low=mid+1;
  }else if(convert(s,mid)==n){
   //cout<<mid;
   printf("%lld",mid);
   return;
  }
 }
 cout<<"Impossible";
 return;
}
int main()
{
 string n1,n2;ll tag,radix;
 cin>>n1>>n2>>tag>>radix;
 ll n;
 string s;
 if(tag==1){
  n=convert(n1,radix);
  s=n2;
 }else{
  n=convert(n2,radix);
  s=n1;
 }
 ll low,high;
 string ss=s;
 sort(ss.begin(),ss.end());
 low=isdigit(ss[ss.length()-1])==1?(ss[ss.length()-1]-'0'):(ss[ss.length()-1]-'a'+10)+1;
 high=max(low,n);
 findradix(s,low,high,n);
 return 0;
}