«عندما نبوح بهمومنا، تتضاءل. ينتقل نصف حزن المتحدث إلى الطرف الآخر، ويعود النصف الآخر إلى العالم مع الموجات الصوتية. وهكذا تنتقل الهموم بين الناس وتضعف شيئًا فشيئًا، حتى تتلاشى مع الريح».

في دائرة أصدقاء الصغير I يوجد $n$ أشخاص، ولدى الشخص $i$ ($1 \le i \le n$) في البداية مقدار من الهموم يساوي العدد الصحيح الموجب $a_i$.

لتخفيف هموم الجميع، نظم الصغير I جلسة محادثة يجلس فيها الأشخاص $n$ في صف من اليسار إلى اليمين بترتيب أرقامهم تصاعديًا.

الوقت محدود، لذا يستطيع الصغير I تنظيم ما لا يزيد على $k$ عمليات بوح خلال الجلسة. في كل عملية، يبوح شخص $p$ ($1 \le p \le n-1$) للشخص الذي على يمينه، أي $p+1$. يؤدي ذلك أولًا إلى $a_{p+1}\leftarrow a_{p+1}+\frac12 a_p$، ثم إلى $a_p\leftarrow0$، حيث ترمز $\leftarrow$ إلى الإسناد. يستطيع الصغير I اختيار المتحدث في كل عملية بحرية. لاحظ أن الشخص ذي الرقم $n$ لا يبوح لأي شخص آخر.

يريد الصغير I تقليل هموم الجميع قدر الإمكان، ولذلك يريد معرفة أصغر قيمة ممكنة لأكبر مقدار نهائي من الهموم لدى أي شخص بعد انتهاء الجلسة.

يجب إخراج القيمة الدقيقة للإجابة. تحديدًا، يمكن دائمًا كتابة الإجابة على الصورة $\frac{S}{2^n}$، حيث $S$ عدد صحيح موجب لا يتجاوز $2^n\times(\max_{i=1}^n a_i)$. عليك إخراج التمثيل الثنائي للعدد $S$.

الإدخال

تُقرأ البيانات من الملف confide.in.

تحتوي هذه المسألة على عدة حالات اختبار. يحتوي السطر الأول على عدد صحيح $T$ يمثل عدد حالات الاختبار، ثم توصف الحالات بالتتابع.

لكل حالة، يحتوي السطر الأول على عددين صحيحين $n,k$، يمثلان عدد الأشخاص والحد الأعلى لعدد عمليات البوح، على الترتيب. ويحتوي السطر الثاني على $n$ أعداد صحيحة موجبة $a_1,a_2,\ldots,a_n$ تصف مقدار الهموم الأولي لكل شخص.

الإخراج

تُكتب النتيجة في الملف confide.out.

لكل حالة اختبار، أخرج في سطر واحد سلسلة من الأصفار والآحاد تمثل العدد $S$ بالثنائي، من البت الأعلى إلى البت الأدنى. يجب ألا يحتوي الإخراج على أصفار بادئة.

أمثلة

الإدخال 1

3
3 1
5 2 1
3 2
5 2 1
3 3
5 2 1

الإخراج 1

100100
10100
10100

ملاحظة

في حالة الاختبار الأولى، تتمثل الاستراتيجية المثلى في جعل الشخص الأول يبوح. تصبح مقادير الهموم النهائية $(0,4.5,1)$، لذا نخرج التمثيل الثنائي 100100 للعدد $4.5\times2^3=36$.

في حالتي الاختبار الثانية والثالثة، تتمثل الاستراتيجية المثلى في جعل الشخص الثاني يبوح أولًا، ثم الشخص الأول. تصبح مقادير الهموم النهائية $(0,2.5,2)$، لذا نخرج التمثيل الثنائي 10100 للعدد $2.5\times2^3=20$.

المثال 2

انظر إلى الملفين confide/confide2.in وconfide/confide2.ans في مجلد المتسابق.

ملاحظة

إجابات حالات الاختبار السبع في هذا المثال هي على الترتيب $10,10,8,5,3.5,2.75,2.5$.

المهام الفرعية

لنرمز بـ $\sum n$ إلى مجموع قيم $n$ لجميع حالات الاختبار في نقطة اختبار واحدة. تُضمن الشروط التالية لجميع حالات الاختبار:

• $1 \le T \le 2\times10^4$.
• $1 \le n,\sum n \le 2\times10^4$، و$1 \le k \le 10^9$.
• لكل $1 \le i \le n$، لدينا $1 \le a_i \le 10^6$.