״כשאנחנו משתפים אחרים במה שמעיק עלינו, הדאגות נחלשות. מחצית מעצבו של המשתף נמסרת לאדם שמולו, והמחצית האחרת חוזרת לעולם עם גלי הקול. כך הדאגות עוברות מאדם לאדם ונחלשות עוד ועוד, עד שהן נישאות ברוח ונעלמות.״

בחוג החברים הקטן של 小 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\left(\max_{i=1}^{n}a_i\right)$. עליך להדפיס את הייצוג הבינרי של $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)$, ולכן יש להדפיס את הייצוג הבינרי של $4.5\times2^3=36$, שהוא 100100.

במקרי הבדיקה השני והשלישי, האסטרטגיה המיטבית היא לתת תחילה לאדם השני לשתף, ואז לאדם הראשון. כמויות הדאגות הסופיות הן $(0,2.5,2)$, ולכן יש להדפיס את הייצוג הבינרי של $2.5\times2^3=20$, שהוא 10100.

דוגמה 2

ראה את הקבצים confide/confide2.in ו־confide/confide2.ans בתיקיית המתחרה.

הסבר

התשובות לשבעת מקרי הבדיקה בדוגמה זו הן, לפי הסדר, $10,10,8,5,3.5,2.75,2.5$.

תתי־משימות

נסמן ב־$\sum n$ את סכום ערכי $n$ של כל מקרי הבדיקה בקובץ בדיקה יחיד. לכל נתוני הבדיקה מובטח כי:

• $1\le T\le2\times10^4$,
• $1\le n,\sum n\le2\times10^4$, ‏$1\le k\le10^9$,
• $\forall 1\le i\le n,1\le a_i\le10^6$.