本题没有可用的提交语言。

问题描述

矿泉水生产大学的支付系统完全自动化（完全用番茄编程语言编写），允许用户输入想提取的金额。由于教授的工资很高，他们可能会以指数形式输入金额。例如，想提取16 MWU（矿泉水单位），可以输入16、2^4或2^2^2。

一天，斯坦内斯库试图从他余额为80 MWU的账户中取钱。他误输入了2^3^2，结果惊讶地取出了512 MWU，尽管他本不应取出超过80。系统由两个主要模块组成：第一个模块检查账户是否有足够金额执行交易，第二个模块向用户付款。结果发现，第一个模块在处理'^'运算符时从左到右计算，而第二个模块按正确的右到左顺序计算（即指数右结合）。因此，对于第一个模块，2^3^2被计算为(2^3)^2=64，而第二个模块计算为2^(3^2)=512。

你需要编写程序，帮助斯坦内斯库从系统中提取尽可能多的金额。请注意，矿泉水生产大学是邪恶的，所以无需考虑合法性。

输入

输入文件包含斯坦内斯库的账户金额，每行一个整数，范围在2到10¹⁰⁰−1之间。

输出

对于每个金额，输出斯坦内斯库应输入的表达式，满足以下条件：

1. 仅由整数和'^'运算符组成。
2. 通过第一个模块的检查（即左结合计算结果≤账户金额），且在第二个模块中（右结合计算）的结果尽可能大。
3. 不包含数字1（无意义）。
4. 若有多个解，按表达式中数字依次最小的原则选择（即先最小化第一个数，若相同则最小化第二个数，依此类推）。

输入输出示例

输入数据 1

16  
80  
49  
1025  
12341234  
12345678901234567890  

输出数据 1

2^2^2  
2^3^2  
7^2  
2^2^5  
2^2^2^5  
2^2^2^2^3^2  

来源

Southeastern Europe 2006