Wstęp do programowania w C++

Napisz program, który będzie realizował drzewo binarne złożone z conajwyżej 20 poziomów. Po wczytaniu wartości wszystkich liści należy odpowiadać na pytania. Pytanie będzie zawierało numer liścia (numerujemy od 1). Jako odpowiedź powinniśmy akutalizować ojców, którzy otrzymują wartość równą sumie wartości synów. Po każdej takiej aktualizacji wypisujemy wartość ojca. Zakładamy, że na początku wszyscy ojcowie mają wartość 0. Zakładamy, że drzewo jest kompletne.

Wejście

W pierwszym wierszu jedna liczba p określająca liczbę poziomów ( 1 < p < 21).

W drugim wierszu wartości w wszystkich liści (0 <= w <= 1000).

W kolejnym wierszu jedna liczba q określająca liczbę zapytań.

Każde zapytanie składa się z jednej liczby z będącą numerem liścia.

Wyjście

Dla każdego zapytania wartości wszystkich ojców począwszy od liścią zakączywszy na korzeniu. Na każdym poziomie drzewa, ojciec przyjmuje sumę wartości swoich synów.

Przykład

Wejście:
3
6 3 9 0 
4
3
4
2
1


Wyjście:
9 9 9 
0 9 9 
3 9 18 
6 9 18