Нашествие зомби
Группа выживших прибыла на изолированный остров на вертолете. Остров представляет собой длинную узкую полосу деревень. Зараженные выжившие прибыли в деревню на крайнем востоке и случайно заразили местных жителей. Теперь островитяне пытаются сбежать от зомби, которые появились на восточном побережье.
Вам даны N наборов данных, каждый из которых содержит 20 неотрицательных целых чисел, представляющих количество островитян в каждой деревне. Деревни расположены с запада на восток (слева направо), и зомби движутся с востока. У островитян есть особые обычаи путешествий: они перемещаются между деревнями только парами. Интересно, что из каждой пары, путешествующей между двумя деревнями, выживает только один. По мере продвижения зомби на запад, островитяне будут перемещаться в деревню, находящуюся непосредственно к западу от их текущей, если там есть хотя бы два островитянина. Если в деревне нечетное количество людей, один остается, а остальные перемещаются в следующую деревню парами. Как только островитяне достигнут деревни на западном побережье, они прекращают путешествие.
Определите, сколько островитян останется в каждой деревне и сколько из них благополучно доберется до деревни на западном побережье (крайняя левая).
Входные данные
Первая строка входных данных содержит количество наборов данных, которые вам предстоит обработать, N (1 ≤ N ≤ 50).
Далее следуют N строк, каждая из которых содержит двадцать 20 неотрицательных целых чисел. Каждое число (≤ 1000) представляет количество островитян в деревне. Левое число соответствует деревне на западном побережье, а правое — деревне на восточном побережье.
Выходные данные
Ваш вывод должен состоять из N строк, каждая из которых содержит двадцать 20 неотрицательных целых чисел. Левое число будет представлять количество островитян, достигших западного побережья. Каждое последующее число будет представлять количество людей, оставшихся в каждой деревне.