برای رشته‌ی دودویی $a_1a_2...a_n$ (که در آن $a_i$، ۰ یا ۱ است) تابع $f$ را به این صورت تعریف می‌کنیم: $f(a_1a_2...a_n)=b_1b_2...b_{n-1}$، که در آن $b_i=a_i xor a_{i+1}$. پس $f^m$ یک رشته‌ی $n$ بیتی، یک رشته‌ی $n-m$ بیتی تولید می‌کند. یک آدم علاف از ما خواست برنامه‌ای بنویسیم که با دریافت رشته‌ی $n$ بیتی $S$ و مقدار $m$، $f^m(S)$ را حساب کند. ما هم دیدیم زورمان فقط به شما می‌رسد. مسئله را دادیم برای امتحان شما. ان‌شاا… که به گندگی خودتان ببخشید.

در سطر اول فایل ورودی به ترتیب اعداد $n$ و $m$ آمده‌اند و در سطر دوم آن $\lceil \frac{n}{4} \rceil$ رقم در مبنای ۱۶ داده شده‌اند که رقم $i$ ام آن نشان‌دهنده‌ی مقدار دودویی $(a_{4i+1}a_{4i+2}a_{4i+3}a_{4i+4})_2$ در مبنای ۱۶ است. آخرین رقم در ورودی شامل $3-(n mod 4)$ بیت بی معنی‌ است که با صفر کردن بیت‌های با ارزش کم‌تر آن (در مبنای ۲) مشخص شده‌اند. ( $1\leq m < n \leq 10^7$)

فایل خروجی باید شامل دقیقا $\lceil \frac{n-m}{4} \rceil$ رقم مبنای ۱۶ به همان فرمت ورودی باشد که نشان‌دهنده‌ی $f^m$ رشته‌ی ورودی است. $3-(n-m)mod 4$ بیت بی‌معنی رقم آخر را مثل ورودی برابر صفر قرار دهید.

توضیح نمونه: $f^9(01110010001110110101110110)=11011011101010110$

• سوال بعد
• سوال قبل