Recurring Decimals

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

繰り返す10進数

数の10進表現は数字を並べ替えることで別の数になる. このことを使って数列を作ってみよう.

最初に,非負の整数a0と桁数Lを与える. 以下の規則を適用してaiからai+1を得る.

  1. 整数aiを,L桁の10進数で表記する. 必要であれば上位の桁に 0 を付け加える. たとえば 2012 という数は 6 桁の10進数で表記する場合は 002012 となる.
  2. 各桁の数字を並べ替えて,最も大きい整数と最も小さい整数を作る. 上の例では,最も大きい整数は 221000 であり, 最も小さい整数は 000122 = 122となる.
  3. 最も大きい整数から最も小さな整数を引いて,整数ai+1を得る. 上の例では 221000 − 122 を計算して 220878 を得る.

この計算を繰り返すと,数列 a0 , a1 , a2 , ... が得られる.

例えば 83268 という整数と桁数6が与えられた時,この計算を繰り返すと次のような数列 a0 , a1 , a2 , ... が得られる.

a0 = 083268
a1 = 886320 − 023688 = 862632
a2 = 866322 − 223668 = 642654
a3 = 665442 − 244566 = 420876
a4 = 876420 − 024678 = 851742
a5 = 875421 − 124578 = 750843
a6 = 875430 − 034578 = 840852
a7 = 885420 − 024588 = 860832
a8 = 886320 − 023688 = 862632
   …

整数を表すための桁数が指定されているので, a0 , a1 , a2 , ... と順に計算していくといずれ同じ数が現れる. すなわち,条件 ai = aj   を満たすような i  と j  (ただし i  > j  ) の組が必ず存在する. 上の例では,a8 = a1 = 862632 なので (i = 8, j = 1) の組が条件を満たす.

最初の整数 a0 と桁数 L  が与えられた場合に,条件 ai = aj (ただしi  > j  ) を満たす最小の i  を求めるプログラムを作成せよ.

Input

入力は複数のデータセットからなる. 各データセットは2つの整数 a0  と L  が1個のスペースで区切られた1行であり, a0  が最初の整数を, L  が桁数を表す. ただし, 1 ≤ L  ≤ 6 かつ 0 ≤ a0  < 10L である.

入力の終わりは2個の0を含む行で示される.この行はデータセットではない.

Output

各データセットに対して,条件 ai = aj   (i  > j  ) を満たす最小の i  を求め, そのときの j  の値, ai   の値, i  − j  の値をスペース1個ずつで区切り,1行で出力せよ. 数値を出力する時は,余分な上位のゼロは有ってはならない. 出力に余分な文字は含んではならない.

上記の i  は20を超えないと仮定して構わない.

Sample Input

2012 4
83268 6
1112 4
0 1
99 2
0 0

Output for the Sample Input

3 6174 1
1 862632 7
5 6174 1
0 0 1
1 0 1

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2012-07-6
http://www.cs.titech.ac.jp/icpc2012/