지급 시스템

광천수 생산 대학교의 지급 시스템은 완전히 자동화되어 있고(전부 토마토 프로그래밍 언어로 작성되었습니다), 출금하려는 금액을 입력하면 됩니다. 교수들의 급여가 워낙 높다 보니 금액을 ^ 연산자를 써서 지수 형태로 입력할 수도 있습니다. 예를 들어 16 MWU(광천수 단위, mineral water units)를 출금하려면 16, 2^4, 2^2^2 중 무엇으로 입력해도 됩니다.

어느 날 잔액이 80 MWU였던 스타네스쿠가 2^3^2를 입력했는데, 80보다 많이 가져갈 수 없어야 함에도 놀랍게도 512 MWU를 받았습니다. 이 시스템은 두 개의 모듈로 이루어져 있습니다. 첫 번째 모듈은 계좌에 거래를 처리할 만큼의 돈이 있는지 확인하고, 두 번째 모듈은 실제로 돈을 내어 줍니다. 알고 보니 두 모듈은 ^ 연산자를 다르게 계산했습니다. 첫 번째 모듈은 왼쪽에서 오른쪽으로, 두 번째 모듈은 (수학적으로 올바른 방식인) 오른쪽에서 왼쪽으로 계산합니다. 그래서 첫 번째 모듈에서는 2^3^2 = (2^3)^2 = 64이지만, 두 번째 모듈에서는 2^3^2 = 2^(3^2) = 512입니다.

스타네스쿠가 이 시스템에서 가능한 한 많은 돈을 출금하도록 돕는 프로그램을 작성하세요. (혹시 이게 부당하다고 생각된다면, 광천수 생산 대학교는 원래 나쁘고 사악한 곳이니 안심하세요.)

입력의 각 줄에는 스타네스쿠 계좌의 잔액이 하나씩 주어지며, 2 이상 10^100 − 1 이하의 정수입니다. 입력은 파일 끝(EOF)에서 종료됩니다.

각 금액에 대해, 스타네스쿠가 가장 많은 돈을 받으려면 무엇을 입력해야 하는지 한 줄에 출력하세요. 입력 문자열은 다음을 만족해야 합니다.

• 정수들과 그 사이의 ^ 연산자만으로 이루어져야 합니다.
• 첫 번째 모듈의 검사를 통과하면서(왼쪽에서 오른쪽으로 계산한 값이 잔액을 넘지 않아야 합니다) 두 번째 모듈의 값(오른쪽에서 왼쪽으로 계산)이 가능한 한 커야 합니다.
• 숫자 1을 포함하면 안 됩니다(어차피 쓸모없습니다).

같은 최댓값을 주는 답이 여러 개면 첫 번째 숫자가 가장 작은 것을, 그래도 여러 개면 두 번째 숫자가 가장 작은 것을, 그런 식으로 출력하세요.