B - すべては1になる Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

Description

O氏は長い間ずっと大学に閉じ込められていたが,自分の後継となる者Fを見つけ後の事を全てそのFにたくし,n年の時を経て外の世界に旅立つことにした.(0は自然数)

大学から外の世界に出るためには,まず大学を卒業しなければならない.なんと,O氏はこの事を事前に想定し,一定時間がたつと自動的にO氏が卒業したことにするプログラムを大学のコンピュータに埋め込んでいたのだ.しかし,仕込んだ日時は記録しているのだがプログラムを仕込んだのがずいぶん昔なため卒業する正確な時刻を忘れてしまった.仕込んだプログラムを見てみると,仕込んだ時刻から2進数で111....11秒後に発動する設定になっていた.

O氏は周りの人に不審に思われないように卒業するために,仕込んだプログラムが発動する時刻を計算することにした.

(この問題では,閏秒はないものとして考えること)

Input

入力は複数のテストケースからなる.入力の終わりは1つの0のみを含んだ行で示される. 各テストケースは以下の形式で与えられる.

year/month/day hh:mm:ss
time
  • 1900 ≦ year ≦ 20012
  • 01 ≦ month ≦ 12
  • 01 ≦ day ≦ 31
  • 00 ≦ hh ≦ 23
  • 00 ≦ mm,ss ≦ 59

テストケースの1行目には,年,月,日,時間,分,秒が書かれている.これらはO氏がプログラムを仕込んだ時刻を表している.月,日,時間,分,秒は必ず2桁で与えられる.(値が10未満の場合,10の位は0埋めされる)

テストケースの2行目には,1のみから成る文字列timeが書かれている.これはプログラムが発動するまでの時間を2進数で表したものである.timeの長さは1文字以上30文字以下である.

存在しない日付は与えられないことが保証されている.テストケースの数は1つのファイルにつき5,000個以下であることが保証されている.

Output

各テストケースに対して,プログラムが発動する時刻を入力と同じ形式で1行に出力せよ.

Sample Input

2012/04/14 17:45:00
1
2012/02/29 17:45:00
111
2012/02/02 00:00:00
11111111
2012/04/14 20:16:15
1111111111111111
2002/09/28 02:35:44
1111111111111111111111111111
2005/12/11 12:00:00
111111111111
2009/12/20 15:00:00
11111111111111
2006/11/18 05:11:29
11111111111111111111111111111
20012/12/31 23:59:59
111111111111111111111111111111
0

Sample Output

2012/04/14 17:45:01
2012/02/29 17:45:07
2012/02/02 00:04:15
2012/04/15 14:28:30
2011/03/31 23:59:59
2005/12/11 13:08:15
2009/12/20 19:33:03
2023/11/23 00:00:00
20047/01/10 13:37:02

Hint

各月はそれぞれ以下の日数分ある.

  • 1月:31日
  • 2月:28日
  • 3月:31日
  • 4月:30日
  • 5月:31日
  • 6月:30日
  • 7月:31日
  • 8月:31日
  • 9月:30日
  • 10月:31日
  • 11月:30日
  • 12月:31日

ただし,年が400の倍数で割り切れるか,100の倍数で割り切れず4の倍数で割り切れる閏年の時には2月は29日分存在する.


Source Name

ふか杯 5th Contest