H :: Hunger

Time Limit: 10 Seconds    Memory Limit: 32768 KB

پس از اتمام جنگِ سختِ کپک‌آبادی‌ها با سرزمین‌هایِ جنوبی و یک محاصره‌ی طولانی مدت، منابع غذایی کپک‌آبادی‌ها تمام شد. حاکم کپک‌آباد از پس مشاهده‌ی گرسنگی مردم، تصمیم گرفت یک گروه را به شهرهای شمالی اعزام کند تا غذا بیاورند. هر شهر با شهر‌هایی که باهم مرز مشترک دارند، همسایه است.

کپک‌آبادی‌ها به علت علاقه‌ی خاصی که به سرزمین خود داشته‌اند هیچوقت از آن خارج نشده‌ و سرزمین‌های کناری خود را نمی‌شناسند. به همین دلیل، این گروه برای پیدا کردن غذا، به طور تصادفی یک شهر همسایه را انتخاب کرده و همگی به آن شهر رفتند. از آن شهر به بعد این کار را کردند:

• اگر در آن شهر غذایی پیدا بکنند، غذا را از آن شهر می‌گیرند و برمی‌گردند.

• اگر در آن شهر غذایی پیدا نکردند، تصادفاً به یکی از شهرهای همسایه می‌روند. (ممکن است از فرط گرسنگی متوجه نشوند که به شهر قبلی برگشته‌اند!)

در بعضی از شهرها غذا هست و در بقیه‌ی شهرها به علت قحطی غذا موجود نیست. در شهرi، غذا به مقدار Vi موجود است. (اگر غذایی نباشد، این عدد صفر می‌¬شود)حاکم قصد دارد بداند میانگین مقدار غذایی که ممکن است از یک اعزام کاملاً تصادفی به دست بیاید چقدر است. شما با برنامه‌ی خود به او کمک کنید.

Input

در خط اول عدد صحیح و مثبت T که مشخص‌کننده‌ی تعداد مورد‌های آزمون است، داده می­شود.در خط اول هر مورد آزمون، عدد صحیح N داده شده () و در خط دوم هر مورد آزمون، N عدد V_i () داده می‌شوند که مقدار غذای موجود در شهرها را مشخص می‌کنند. درN+1خط بعد هر تست، در هر خطN+1 عدد صفر یا یک داده می‌شود که عدد صفر مبین همسایه نبودن و عدد یک مبین همسایگی دو شهر است.

Output

میانگین مقدار غذایی که ممکن است عاید کپک‌آبادی‌ها شود را تا دو رقم اعشار، در خروجی بنویسید.

Sample Input

1
4
0 2 14 8
0 1 1 0 0
1 0 0 1 0
1 0 0 1 0
0 1 1 0 1
0 0 0 0 1

Sample Output

6.00

Submit