50006. Final Prob. 6: A+B Problem

I'm a slow walker, but I never walk backwards.

相信大家有看過類似這樣的簡單題目:

請在999999189999999插入一個加號和一個等號,使得等式成立。

解出來了嗎?答案是9999991+8=9999999喔!有沒有很簡單?

因為這個問題實在是太簡單了,為了讓問題稍微有挑戰性一點,我們要多加上幾個條件:
(1) 加號一定要插入在等號的左邊。
(2) 由加號和等號分開的三個數字都不能有前導零。例如說,012300都算是有前導零,但是1000都不算有前導零。
(3) 如果存在很多組解,答案是分開後第一個數字最小的那組解。如果還是有很多第一個數字最小的解,則答案是第二個數字最小的那組。
(4) 如果不存在任何一組解,由於受到彥仁的電場影響,你必須輸出Meow才能獲得AC的機會。(注意大小寫。)

雖然多了這幾個條件,但好像也還是很簡單。你的任務就是寫一個程式來解決這個簡單的問題。

Input / Output

第一行有一個正整數$T$,代表總共有幾筆測資。 接下來每一行為一筆測資,即是題目給定的字串。保證字串全部由數字0~9組成。

對於每筆測資請輸出一行,即上述問題的答案。

Subtasks / Constraints

所有測資皆符合:$T\leq 10^ 4, N\leq 10^ 6$,且$T$個字串的長度總和不超過$2\times 10^ 7$。

  1. 輸入字串的第一個字元是0 (2 pts)
  2. $N\leq 18$ (4 pts)
  3. $N\leq 100, T\leq 200$,保證一定有解 (2 pts)
  4. $N\leq 1000, T\leq 200$,輸入字串只由0~4組成 (4 pts)
  5. $N\leq 1000, T\leq 200$,保證一定有解 (2 pts)
  6. $N\leq 1000, T\leq 200$ (2 pts)
  7. 保證一定有解 (6 pts)
  8. 無額外限制 (3 pts)

Sample Input

3
1230123
3036
999999189999999

Sample Output

123+0=123
Meow
9999991+8=9999999

Discussion