G. Карты, числа, два заклинания
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд расположены $$$n$$$ карт. У каждой карты есть сила, выраженная целым неотрицательным числом. Также существует два заклинания.

Заклинание «Равные шансы» уменьшает в два раза силу карт, у которых эта сила чётная.

Заклинание «Странное событие» уменьшает на $$$1$$$ силу всех карт, у которых эта сила нечётная.

Обработайте заданную последовательность применения заклинаний, выводя после каждого применения очередного заклинания суммарную силу карт.

Входные данные

Первая строка содержит целое число $$$n$$$ — размер ряда ($$$1 \leq n \leq 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$, разделённых пробелами ($$$1 \leq a_i \leq 2^{30}-1$$$) — изначальные силы карт.

Третья строка содержит последовательность применения заклинаний в виде символов «0» (заклинание «Равные шансы») и «1» (заклинание «Странное событие»).

Количество заклинаний от $$$1$$$ до $$$10^5$$$.

Выходные данные

После каждого заклинания выведите сумму сил карт в отдельной строке.

Примеры
Входные данные
5
1 2 3 4 5
0110
Выходные данные
12
8
8
4
Входные данные
3
1 1 1
01
Выходные данные
3
0
Примечание

s Чётное число — число, которое при делении на $$$2$$$ даёт остаток $$$0$$$.

Нечётное число — число, которое не является чётным.