«Коли ми ділимося переживаннями, тривоги слабшають. Половину свого смутку оповідач передає співрозмовнику, а другу половину звукові хвилі повертають світові. Так тривоги передаються між людьми, дедалі слабшаючи, аж поки не зникнуть за вітром».

У тісному колі 小 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}+\frac12a_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.

Для кожного набору виведіть в окремому рядку рядок із символів 0 та 1, який задає двійкове подання $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$.