// A1010 Radix (25分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
题意：
1、给出四个数，N1,N2（不超过10位，进制小于36），tag表示选择哪一个， radic表示选中那个数的进制
2、找出另外一个数字的36进制内，有没有可能等于这个指定进制的数

总结就是：一个指定进制的数，看另一个数从36进制内是否能够匹配，是则输出这个进制，不是则输出impossible

解题：
1、n1存放确定进制数，n2存放未知进制数
2、n1转为10进制，然后n2转为10进制，看大还是小（也就是二分）
如何实现这一步呢

learn && wrong:
1、因为一个特性，一个确定的数字串，他的进制越大，转为10进制也就越大
2、因为10个数字，转为36，是有可能超过int的！
3、按权展开不会
4、如何实现那个，二分弄进制呢！
5、strcpy函数，是copy
*/

include <iostream>

include <algorithm>

include <cstring>

using namespace std;

typedef long long LL;//(!!!)
LL map[256]; //0_9、az、与0~35对应

LL inf = (1LL << 63) - 1; //long long 的最大值2的63次方 - 1，注意加括号（！！！）

void init() {
for (char c = '0'; c <= '9';c++) {
map[c] = c - '0'; //将0_{9（字符串）映射到0}9
}
for (char c = 'a';c <= 'z';c++) {
map[c] = c - 'a' + 10; //将'a'_{'z'映射到10}35
}
}

LL convertNum10(char a[], LL radix, LL t) { //将a转为10进制，t为上界
LL ans = 0;
int len = strlen(a);
for (int i = 0;i < len;++i) {
ans = ans * radix + map[a[i]]; //进制转换
if (ans < 0 || ans > t) return -1;
}
}

int cmp(char N2[], LL radix, LL t) {//将N2的十进制与t比较
int len = strlen(N2);
LL num = convertNum10(N2, radix, t); //将N2转换为10进制
if (num < 0) return 1; //t较大，返回-1
else if (t == num)return 0; //相等，返回0
else return 1; //num较大，返回1

}

LL binarySearch(char N2[], LL left, LL right, LL t) {
LL mid;
while (left <= right) {
mid = (left + right) / 2;
int flag = cmp(N2, mid, t); //判断N22转换为10进制后与t比较
if (flag == 0) return mid; //找到解，返回mid
else if (flag == -1) left = mid + 1; //往右子区间继续查找
else right = mid - 1;//往左子区间继续查找
}
return -1; //解不存在
}

int findLargest(char N2[]){//求最大的数位
int ans = -1, len = strlen(N2);
for (int i = 0;i < len;i++) {
if (map[N2[i]] > ans) {
ans = map[N2[i]];
}
}
return ans + 1; //最大数位为ans，说明进制数的底线是ans + 1
}

char N1[20], N2[20], temp[20];

int tag, radix;

int main()
{
init();
scanf_s("%s %s %d %d", N1, N2, &tag, &radix);
if (tag == 2) { //交换N1和N2（！！！）
strcpy_s(temp, N1);
strcpy_s(N1, N2);
strcpy_s(N2, temp);
}
LL t = convertNum10(N1, radix, inf); //将N1从radix进制转换为10进制
LL low = findLargest(N2); //找到N2中数位最大的位+1，当成二分下界
LL high = max(low, t) + 1; //上界
LL ans = binarySearch(N2, low, high, t); //二分
if (ans == -1) printf("Impossible\n");
else printf("%lld\n", ans);
return 0;
}