“Khi chúng ta tâm sự, nỗi phiền muộn vơi đi. Một nửa nỗi buồn của người tâm sự được trao cho người đối diện, nửa còn lại theo sóng âm trở về với thế giới. Cứ thế, phiền muộn truyền qua mọi người rồi yếu dần, cho đến khi tan theo gió.”

Trong nhóm bạn nhỏ của 小 I có $n$ người. Người thứ $i$ ($1\le i\le n$) ban đầu có lượng phiền muộn là số nguyên dương $a_i$.

Để giúp mọi người bớt phiền muộn, 小 I tổ chức một buổi trò chuyện. Trong buổi này, $n$ người ngồi thành một hàng từ trái sang phải theo thứ tự số hiệu tăng dần.

Thời gian có hạn, nên 小 I có thể tổ chức không quá $k$ lần tâm sự. Trong mỗi lần, một người $p$ ($1\le p\le n-1$) tâm sự với người bên phải mình là $p+1$. Trước tiên thực hiện $a_{p+1}\leftarrow a_{p+1}+\frac12a_p$, rồi $a_p\leftarrow0$, trong đó $\leftarrow$ là phép gán. 小 I được tùy ý chọn người tâm sự trong mỗi lần. Lưu ý rằng người mang số hiệu $n$ không tâm sự với người khác.

小 I muốn mọi người có càng ít phiền muộn càng tốt, nên muốn biết: sau buổi trò chuyện, giá trị lớn nhất trong lượng phiền muộn cuối cùng của tất cả mọi người có thể nhỏ nhất là bao nhiêu?

Bạn cần in giá trị chính xác của đáp án. Cụ thể, đáp án luôn có thể viết dưới dạng $\frac{S}{2^n}$, trong đó $S$ là một số nguyên dương không vượt quá $2^n\times\left(\max_{i=1}^n a_i\right)$. Bạn cần in biểu diễn nhị phân của $S$.

Dữ liệu vào

Đọc dữ liệu từ tệp confide.in.

Bài toán có nhiều bộ dữ liệu kiểm thử. Dòng đầu tiên chứa một số nguyên $T$, biểu thị số bộ dữ liệu; tiếp theo là mô tả từng bộ dữ liệu theo thứ tự.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $n,k$, lần lượt là số người và giới hạn số lần tâm sự; dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\ldots,a_n$, mô tả lượng phiền muộn ban đầu của mỗi người.

Dữ liệu ra

Ghi kết quả vào tệp confide.out.

Với mỗi bộ dữ liệu, in một dòng chứa một xâu chỉ gồm các ký tự 0 và 1, mô tả biểu diễn nhị phân của $S$ từ bit cao đến bit thấp. Kết quả không được có số 0 ở đầu.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

100100
10100
10100

Ghi chú

Với bộ dữ liệu thứ nhất, chiến lược tối ưu là để người thứ nhất tâm sự. Lượng phiền muộn cuối cùng là $(0,4.5,1)$, nên in biểu diễn nhị phân 100100 của $4.5\times2^3=36$.

Với bộ dữ liệu thứ hai và thứ ba, chiến lược tối ưu là để người thứ hai tâm sự trước, rồi đến người thứ nhất. Lượng phiền muộn cuối cùng là $(0,2.5,2)$, nên in biểu diễn nhị phân 10100 của $2.5\times2^3=20$.

Ví dụ 2

Xem các tệp confide/confide2.in và confide/confide2.ans trong thư mục của thí sinh.

Ghi chú

Đáp án của bảy bộ dữ liệu trong ví dụ này lần lượt là $10,10,8,5,3.5,2.75,2.5$.

Nhiệm vụ con

Gọi $\sum n$ là tổng các giá trị $n$ của tất cả bộ dữ liệu trong một tệp kiểm thử. Với mọi bộ dữ liệu, đảm bảo:

• $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$.