- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
توک به مناسبت ولنتاین میخواهد هدیه زیبایی به پوپک بدهد ...
از آنجایی که توک پول زیادی ندارد، به زحمت توانسته است که یک رشته باینری بخرد. توک میداند که رشته باینری خیلی جذاب نیست بنابراین تصمیم گرفته است تغییری در آن ایجاد کند.
او می تواند رشتهاش را به \(a\) رشته با طول برابر افراز کند (که بالطبع طول این رشتهها \(\frac{n} a\) خواهد بود) و در نهایت \(and\) بیتی این \(a\) رشته را به عنوان کادو به پوپک بدهد.
هر چه عدد متناظر با رشته باینریای که توک به پوپک می دهد بیشتر باشد، پوپک شادتر می شود. بهترین رشتهای که توک به پوپک باید هدیه بدهد (یعنی رشتهای که عدد متناظر با آن بیشینه است) را بدون صفر در پشت رشته (leading zeroes) چاپ کنید .
برای مثال اگر رشته توک \(110101\) باشد، توک با انتخاب \(a=3\) ، آن را به سه رشته \(11, 01, 01\) تقسیم میکند که \(and\) بیتی این رشته برابر \(01\) است پس رشتهای که توک به پوپک در این حالت هدیه میدهد \(1\) است. به شکل مشابه اگر توک \(a=2\) را انتخاب کند آنگاه رشتهاش را به دو رشته \(110, 101\) تقسیم میکند و رشتهای که کادو میدهد \(100\) خواهد بود در حالی که با انتخاب \(a=1\) ، رشتهای که توک به پوپک هدیه میدهد \(110101\) میشود، پس چون عدد مربوط به این رشته از بقیه رشتهها بیشتر است توک باید این رشته را به پوپک کادو بدهد! (میتوانید بقیه حالات را نیز بررسی کنید، که به جواب کوچکتری نسبت به این رشته منتهی میشوند)
چنانچه عدد متناظر با رشتهای که توک کادو می دهد \(0\) باشد، در خروجی \(0\) چاپ کنید.
اگر با عملگر \(and\) آشنایی ندارید اینجا را ببینید.
ورودی
در تنها خط ورودی رشته باینری که توک خریده است، آمده است.
اگر طول رشته توک را با \(n\) نشان دهیم \[1 \le n \le 100\ 000\]
خروجی
در تنها خط خروجی رشتهای که توک به پوپک هدیه میدهد را چاپ کنید.
مثال
ورودی نمونه ۱
011
خروجی نمونه ۱
11
ورودی نمونه ۲
110101
خروجی نمونه ۲
110101
این تست نمونه در صورت سوالات توضیح داده شده است .
ورودی نمونه ۳
0000
خروجی نمونه ۳
0