整数分解

题目描述

正整数 N 的 K-P 分解是指将 N 写成 K 个正整数的 P 次方的和。本题就请你对任意给定的正整数 N、 K、 P，写出 N 的 K-P 分解。

时间限制： 8000        内存限制： 262144

输入

输入在一行给出 3 个正整数 N (≤ 400)、 K (≤ N)、 P (1 < P ≤ 7)，以空格分隔。

输出

如果存在解，则按下列格式输出： N = n[1 ]^P + ... n[K]^P 其中 n[i] (i = 1 , ..., K) 是第 i 个分解因子。所有的分解因子要按非增顺序输出。注意： 解可能是不唯一的。例如 169 的 5-2 分解就存在 9 个解，如 12^2 + 4^2 + 2^2 + 2^2 + 1 ^2 或 11 ^2 + 6^2 + 2^2 + 2^2 + 2^2 等等。你必须输出分解因子和最大的那个解。如果还不唯一，则输出具有最大的分解因子序列的解 —— 我们称序列 { a¹ , a² , … , a^K} 比序列 { b¹ , b² , … , b^K } 大，如果存在 1 ≤ L ≤ K 使得 aⁱ =bⁱ 对于 i < L 成立，并且有 a^iL > b^L 。如果解不存在，则输出`Impossible`。

样例输入

样例#1：

169  5  2

样例#2：

169  167  3

样例输出

样例#1：

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

样例#2：

Impossible