시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 75 4 4 7.547%

문제

6과 9를 곱하면 몇이 될까? 정답은 42이다. 54로 생각했다면, 잠시 쉬었다가 문제를 푸는 것을 권장한다. 그 이유는 42는 13진법으로 계산했을 때 결과이기 때문이다.

2보다 크거나 같은 정수 B에 대해서, B진법의 모든 자리수는 0보다 크거나 같고, B-1보다 작거나 같은 정수이다. B진법 수를 읽으려면 가장 오른쪽 자리에 1을 곱하고, 두 번째 오른쪽 자리에 B를 곱하고, 세 번째 오른쪽 자리에 B2를 곱하고, ... 이와 같은 식으로 계속 곱해야 한다.

일부 등식은 어떤 진법을 사용했냐에 따라서 참과 거짓일 결정된다. 예를 들어, 2+2=4의 경우에 B≥5이면 항상 참이다. 4진법에는 4를 자리로 사용할 수 없기 때문에 B≥5이다. 하지만, 2+2=5와 같은 등식은 어떤 진법을 사용해도 참이 될 수 없다.

등식이 주어졌을 때, 어떤 진법을 사용하면 참이 되는지 구하는 프로그램을 작성하시오. 

입력

입력의 각 줄은 테스트 케이스 하나를 나타내며, 각 테스트 케이스는 "EXPR=EXPR"과 같은 형태이다. EXPR는 17자리를 넘지 않는 수식이다.

모든 수식은 항상 올바르며, '+', '*'와 '0'-'9'까지 숫자로 이루어져 있다. 수식이 '+'기호로 시작하는 경우는 없으면, 수의 앞에 불필요한 0이 붙어있는 경우도 없다.

입력의 마지막 줄에는 '='이 주어진다.

출력

각 테스트 케이스마다 어떤 진법을 사용하면 입력으로 주어진 등식이 참이 되는지 출력한다.

등식을 참으로 만드는 진법이 무한대인 경우에는 "B+"를 출력한다. 여기서 B는 등식을 참으로 만드는 가장 작은 진법이다.

진법의 수가 유한개인 경우에는 진법을 오름차순으로 공백으로 구분하여 출력한다.

어떤 진법을 사용해도 등식이 참이 되지 않는 경우에는 '*'을 출력한다.

예제 입력 1

6*9=42
10000+3*5*334=3*5000+10+0
2+2=3
2+2=4
0*0=0
=

예제 출력 1

13
6 10
*
5+
2+
W3sicHJvYmxlbV9pZCI6IjU3MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzRcdWJjOTUgXHVjNTRjXHVjNTQ0XHViMGI0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD42XHVhY2ZjIDlcdWI5N2MgXHVhY2YxXHVkNTU4XHViYTc0IFx1YmE4N1x1Yzc3NCBcdWI0MjBcdWFlNGM/IFx1YzgxNVx1YjJmNVx1Yzc0MCA0Mlx1Yzc3NFx1YjJlNC4gNTRcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTg4XHViMmU0XHViYTc0LCBcdWM3YTBcdWMyZGMgXHVjMjZjXHVjNWM4XHViMmU0XHVhYzAwIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0NzhcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWQ4Y1x1YzdhNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCA0Mlx1YjI5NCAxM1x1YzljNFx1YmM5NVx1YzczY1x1Yjg1YyBcdWFjYzRcdWMwYjBcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YWNiMFx1YWNmY1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjJcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMTggQlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIEJcdWM5YzRcdWJjOTVcdWM3NTggXHViYWE4XHViNGUwIFx1Yzc5MFx1YjlhY1x1YzIxOFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIEItMVx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gQlx1YzljNFx1YmM5NSBcdWMyMThcdWI5N2MgXHVjNzdkXHVjNzNjXHViODI0XHViYTc0IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzkwXHViOWFjXHVjNWQwIDFcdWM3NDQgXHVhY2YxXHVkNTU4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWI5YWNcdWM1ZDAgQlx1Yjk3YyBcdWFjZjFcdWQ1NThcdWFjZTAsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjNjI0XHViOTc4XHVjYWJkIFx1Yzc5MFx1YjlhY1x1YzVkMCBCPHN1cD4yPFwvc3VwPlx1Yjk3YyBcdWFjZjFcdWQ1NThcdWFjZTAsIC4uLiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzJkZFx1YzczY1x1Yjg1YyBcdWFjYzRcdWMxOGQgXHVhY2YxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzdjXHViZDgwIFx1YjRmMVx1YzJkZFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVjOWM0XHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU4OFx1YjBkMFx1YzVkMCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjYzM4XHVhY2ZjIFx1YWM3MFx1YzlkM1x1Yzc3YyBcdWFjYjBcdWM4MTVcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDIrMj00XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBCJmdlOzVcdWM3NzRcdWJhNzQgXHVkNTZkXHVjMGMxIFx1Y2MzOFx1Yzc3NFx1YjJlNC4gNFx1YzljNFx1YmM5NVx1YzVkMFx1YjI5NCA0XHViOTdjIFx1Yzc5MFx1YjlhY1x1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgQiZnZTs1XHVjNzc0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIDIrMj01XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWI0ZjFcdWMyZGRcdWM3NDAgXHVjNWI0XHViNWE0IFx1YzljNFx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWIzYzQgXHVjYzM4XHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0ZjFcdWMyZGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWI0XHViNWE0IFx1YzljNFx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQgXHVjYzM4XHVjNzc0IFx1YjQxOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWFjMDEgXHVjOTA0XHVjNzQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVkNTU4XHViMDk4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgJnF1b3Q7RVhQUj1FWFBSJnF1b3Q7XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWQwZGNcdWM3NzRcdWIyZTQuIEVYUFJcdWIyOTQgMTdcdWM3OTBcdWI5YWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWMyMThcdWMyZGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWMyMThcdWMyZGRcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzYyY1x1YmMxNFx1Yjk3NFx1YmE3MCwgJiMzOTsrJiMzOTssICYjMzk7KiYjMzk7XHVjNjQwICYjMzk7MCYjMzk7LSYjMzk7OSYjMzk7XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMyMThcdWMyZGRcdWM3NzQgJiMzOTsrJiMzOTtcdWFlMzBcdWQ2MzhcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWM3M2NcdWJhNzQsIFx1YzIxOFx1Yzc1OCBcdWM1NWVcdWM1ZDAgXHViZDg4XHVkNTQ0XHVjNjk0XHVkNTVjIDBcdWM3NzQgXHViZDk5XHVjNWI0XHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0ICYjMzk7PSYjMzk7XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWM1YjRcdWI1YTQgXHVjOWM0XHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjRmMVx1YzJkZFx1Yzc3NCBcdWNjMzhcdWM3NzQgXHViNDE4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNGYxXHVjMmRkXHVjNzQ0IFx1Y2MzOFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjOWM0XHViYzk1XHVjNzc0IFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7QismcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgQlx1YjI5NCBcdWI0ZjFcdWMyZGRcdWM3NDQgXHVjYzM4XHVjNzNjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzljNFx1YmM5NVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWM0XHViYzk1XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM3MjBcdWQ1NWNcdWFjMWNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzljNFx1YmM5NVx1Yzc0NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWM5YzRcdWJjOTVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTc0XHViM2M0IFx1YjRmMVx1YzJkZFx1Yzc3NCBcdWNjMzhcdWM3NzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJiMzOTsqJiMzOTtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU3MjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYXNlcyIsImRlc2NyaXB0aW9uIjoiPHA+V2hhdCBkbyB5b3UgZ2V0IGlmIHlvdSBtdWx0aXBseSA2IGJ5IDk/IFRoZSBhbnN3ZXIsIG9mIGNvdXJzZSwgaXMgNDIsIGJ1dCBvbmx5IGlmIHlvdSBkbyB0aGUgY2FsY3VsYXRpb25zIGluIGJhc2UgMTMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGFuIGludGVnZXIgQiAmZ2U7IDIsIHRoZSBiYXNlIEIgbnVtYmVyaW5nIHN5c3RlbSBpcyBhIG1hbm5lciBvZiB3cml0aW5nIGludGVnZXJzIHVzaW5nIG9ubHkgZGlnaXRzIGJldHdlZW4gMCBhbmQgQiAmbWludXM7IDEsIGluY2x1c2l2ZS4gSW4gYSBudW1iZXIgd3JpdHRlbiBpbiBiYXNlIEIsIHRoZSByaWdodG1vc3QgZGlnaXQgaGFzIGl0cyB2YWx1ZSBtdWx0aXBsaWVkIGJ5IDEsIHRoZSBzZWNvbmQgcmlnaHRtb3N0IGRpZ2l0IGhhcyBpdHMgdmFsdWUgbXVsdGlwbGllZCBieSBCLCB0aGUgdGhpcmQgcmlnaHRtb3N0IGRpZ2l0IGhhcyBpdHMgdmFsdWUgbXVsdGlwbGllZCBieSBCPHN1cD4yPFwvc3VwPiwgYW5kIHNvIG9uLjxcL3A+XHJcblxyXG48cD5Tb21lIGVxdWF0aW9ucyBhcmUgdHJ1ZSBvciBmYWxzZSBkZXBlbmRpbmcgb24gdGhlIGJhc2UgdGhleSBhcmUgY29uc2lkZXJlZCBpbi4gVGhlIGVxdWF0aW9uIDIgKyAyID0gNCwgZm9yIGluc3RhbmNlLCBpcyB0cnVlIGZvciBhbnkgQiAmZ2U7IDUgJm1kYXNoOyBpdCBkb2VzIG5vdCBob2xkIGluIGJhc2UgNCwgZm9yIGluc3RhbmNlLCBzaW5jZXRoZXJlIGlzIG5vIGRpZ2l0ICZsc3F1bzs0JnJzcXVvOyBpbiBiYXNlIDQuIE9uIHRoZSBvdGhlciBoYW5kLCBhbiBlcXVhdGlvbiBsaWtlIDIgKyAyID0gNSBpcyBuZXZlciB0cnVlLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBnaXZlbiBhbiBlcXVhdGlvbiBkZXRlcm1pbmVzIGZvciB3aGljaCBiYXNlcyBpdCBob2xkcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSB0ZXN0IGNhc2U7IGVhY2ggdGVzdCBjYXNlIGlzIGFuIGVxdWF0aW9uIG9mIHRoZSBmb3JtICZsZHF1bztFWFBSPUVYUFImcmRxdW87LCB3aGVyZSBib3RoICZsZHF1bztFWFBSJnJkcXVvOyBhcmUgYXJpdGhtZXRpYyBleHByZXNzaW9ucyB3aXRoIGF0IG1vc3QgMTcgY2hhcmFjdGVycy48XC9wPlxyXG5cclxuPHA+QWxsIGV4cHJlc3Npb25zIGFyZSB2YWxpZCwgYW5kIGNvbnRhaW4gb25seSB0aGUgY2hhcmFjdGVycyAmbHNxdW87KyZyc3F1bzssICZsc3F1bzsqJnJzcXVvOyBhbmQgdGhlIGRpZ2l0cyBmcm9tICZsc3F1bzswJnJzcXVvOyB0byAmbHNxdW87OSZyc3F1bzsuIE5vIGV4cHJlc3Npb25zIGNvbnRhaW4gbGVhZGluZyBwbHVzIHNpZ25zLCBhbmQgbm8gbnVtYmVycyBpbiBpdCBoYXZlIGxlYWRpbmcgemVyb3MuPFwvcD5cclxuXHJcbjxwPlRoZSBlbmQgb2YgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIG9ubHkgJmxkcXVvOz0mcmRxdW87LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBpbiB0aGUgaW5wdXQgeW91ciBwcm9ncmFtIHNob3VsZCBwcm9kdWNlIGEgc2luZ2xlIGxpbmUgaW4gdGhlIG91dHB1dCwgaW5kaWNhdGluZyBmb3Igd2hpY2ggYmFzZXMgdGhlIGdpdmVuIGVxdWF0aW9uIGhvbGRzLjxcL3A+XHJcblxyXG48cD5JZiB0aGUgZXhwcmVzc2lvbiBpcyB0cnVlIGZvciBpblx1ZmIwMW5pdGVseSBtYW55IGJhc2VzLCBwcmludCAmbGRxdW87QismcmRxdW87LCB3aGVyZSBCIGlzIHRoZSBcdWZiMDFyc3QgYmFzZSBmb3Igd2hpY2ggdGhlIGVxdWF0aW9uIGhvbGRzLjxcL3A+XHJcblxyXG48cD5JZiB0aGUgZXhwcmVzc2lvbiBpcyB2YWxpZCBvbmx5IGZvciBhIFx1ZmIwMW5pdGUgc2V0IG9mIGJhc2VzLCBwcmludCB0aGVtIGluIGFzY2VuZGluZyBvcmRlciwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuPFwvcD5cclxuXHJcbjxwPklmIHRoZSBleHByZXNzaW9uIGlzIG5vdCB0cnVlIGluIGFueSBiYXNlLCBwcmludCB0aGUgY2hhcmFjdGVyICZsc3F1bzsqJnJzcXVvOy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=