003 - ビー玉占い

時間制限 8 秒 / メモリ制限 256 MB / 得点 12 / x 20 /


TLE
8sec
MLE
256MB
得点
12

問題

Bowls with Marbles

今日のラッキーナンバーを見つけよう.

椀を四つとビー玉をたくさん用意する. 椀を横一列に並べ、深く瞑想してから,それぞれの椀にいくつかのビー玉を入れる. ビー玉の個数はばらばらでよく, 空の椀があってもよいが,少なくとも一つは空でないようにする.

空でない椀のうちでビー玉が一番少ないものを選ぶ. 一番少ない同数の椀が二つ以上あるときは,一番左の椀を選ぶ. 選んだ以外の空でないすべての椀から、 選んだ椀のビー玉と同数のビー玉を取り除く. 選んだ椀の中のビー玉はそのままにしておく.

この手続きを空でない椀が一つだけになるまで繰り返す. その椀に残ったビー玉の個数があなたの今日のラッキーナンバーだ.

Operations

右図に Sample Input の最初のデータセットに対応する例を示す.

  1. 右から二番目の椀のビー玉の個数が最少の 4 個である.
  2. 他の各椀からビー玉を 4 個ずつ取り除くと, 一番右の椀に残るビー玉 2 個が最少になる.
  3. 他の各椀からビー玉を 2 個ずつ取り除くと, 一番左以外の三つの椀すべてに 2 個のビー玉が残り, これが最少である. その三つの中で最も左にあるのは全体の左から二つ目の椀なので,それを選ぶ.
  4. 他の各椀からビー玉を 2 個ずつ取り除くと, これでビー玉が残る椀は二つだけで,両方共 2 個になる. そこで一番左の椀を選ぶ.
  5. 二番目の椀からビー玉 2 個を取り除くと, 空でないのは一番左の椀だけになり,その中のビー玉は 2 個である. そう,あなたの今日のラッキーナンバーは 2 だ!

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

a1 a2 a3 a4

各データセットは a1 から a4 の 4 整数を含む 1 行からなる. これらの 4 整数は四つの椀に最初に入れるビー玉の個数を意味し, いずれも 0 以上 100 以下で,少なくとも一つは 0 でない.

入力の終わりは四つのゼロを含む行で示す.

データセットは 100 個以内である.

Output

各データセットに対して, 上述の手順で求めたラッキーナンバーを 1 行に出力せよ.

Sample Input

10 8 4 6
0 21 7 35
5 45 13 3
52 13 91 78
0 0 0 0
  

Output for the Sample Input

2
7
1
13