Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N​1​​ and N​2​​, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:

6 110 1 10

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible 注意点：1.left<=right; 　　　　2.数据范围用long long

1 #include
     
        2 using namespace std;  3   4 long long digit[256];  5   6 const long long inf = (1LL<<63)-1;  7   8   9  10 void init(){ 11      12     for(char c='0';c<='9';c++) 13         digit[c] = c-'0'; 14          15          16     for(char c='a';c<='z';c++) 17         digit[c] = c-'a'+10; 18 } 19  20 long long convertNum10(string str1,long long radix,long long t){ 21     long long ans=0; 22      23     long long len = str1.size(); 24      25     for(long long i=0;i
      
       t) return -1;         30     } 31      32     return ans; 33      34 } 35  36  37 long long cmp(string str2,long long radix,long long t){ 38     long long n2=convertNum10(str2,radix,t); 39     if(n2<0)return 1; 40     else if(n2==t) return 0; 41     else if(n2>t) return 1; 42     else return -1; 43      44 } 45  46 long long binary_search(string &str2,long long low,long long high,long long t){ 47     long long left=low,right=high; 48     long long mid; 49      50     while(left<=right){ 51         mid=(left+right)/2; 52          53         long long flag=cmp(str2,mid,t); 54          55         if(flag<0)left =mid+1; 56         else if(flag>0)right = mid-1; 57         else return mid; 58     } 59      60      61     return -1; 62  63 } 64  65  66 long long findLargest(string &str){ 67     long long ans=-1; 68     long long len=str.size(); 69      70     for(long long i=0;i
       
        ans) 72             ans=digit[str[i]]; 73     } 74      75      76     return ans+1; 77      78      79 } 80  81  82 int main(){ 83     string str1,str2; 84     long long tag,radix; 85      86     cin>>str1>>str2>>tag>>radix; 87      88     init(); 89      90     if(tag==2) 91         swap(str1,str2); 92          93          94     long long t=convertNum10(str1,radix,inf); 95      96     long long low = findLargest(str2); 97      98     long long high=max(low,t)+1;  99     100     long long ans=binary_search(str2,low,high,t);101     102     103     if(ans==-1)cout<<"Impossible\n";104     else cout<
        
         <