“เมื่อเราระบายความในใจ ความทุกข์ก็ลดลง ความเศร้าของผู้เล่าครึ่งหนึ่งถูกส่งให้ผู้ฟัง อีกครึ่งหนึ่งถูกส่งคืนสู่โลกผ่านคลื่นเสียง ความทุกข์จึงค่อย ๆ อ่อนลงเมื่อส่งต่อกันไปในฝูงชน จนกระทั่งเลือนหายไปกับสายลม”

ในกลุ่มเพื่อนของเสี่ยว 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(\max_{i=1}^n a_i)$ คุณต้องส่งออกรูปฐานสองของ $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$