AT_joi2022ho_a インターカステラー (Intercastellar)

### 题目简述 有一条长度未知的线段，它被截成了若干段，从左往右数第 $i$ 段的长为 $a_i$。现在不断将长度为偶数的线段截成两条长度相等的线段（不改变线段位置），直至没有长度为偶数的线段。截完后，给出 $q$ 个询问，请按顺序回答每个询问。第 $i$ 个询问会输入一个整数 $x_i$，此时请输出左数第 $x_i$ 条线段的长度并换行。

第一行：$n$ 接下来 $n$ 行：第 $i$ 行为 $a_i$ 接下来一行：$q$ 接下来 $q$ 行：第 $i$ 行为 $x_i$

输出 $q$ 行，第 $i$ 行输出的正整数为截完后左起第 $x_i$ 条线段的长度。

### 制約 - $ 1\ \leqq\ N\ \leqq\ 200\,000 $． - $ 1\ \leqq\ A_i\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ N $)． - $ 1\ \leqq\ Q\ \leqq\ 200\,000 $． - $ 1\ \leqq\ X_j\ \leqq\ 1\,000\,000\,000\,000\,000\ (=\ 10^{15}) $ ($ 1\ \leqq\ j\ \leqq\ Q $)． - $ X_{j}\ \leqq\ X_{j\ +\ 1} $ ($ 1\ \leqq\ j\ \leqq\ Q\ -\ 1 $)． - すべての操作が終了したとき，カステラは $ X_Q $ 個以上のピースに分割されている． ### 小課題 1. ($ 25 $ 点) $ A_i\ \leqq\ 8 $ ($ 1\ \leqq\ i\ \leqq\ N $)． 2. ($ 35 $ 点) $ N\ \leqq\ 1\,000 $，$ Q\ \leqq\ 1\,000 $． 3. ($ 40 $ 点) 追加の制約はない． - - - - - - ### Sample Explanation 1 はじめ，カステラの各ピースの長さは左から順に $ 14,\ 9,\ 8,\ 12 $ である． 一連の操作が終了したとき，カステラは $ 15 $ 個のピースに分割されており，各ピースの長さは左から順に $ 7,\ 7,\ 9,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 3,\ 3,\ 3,\ 3 $ となる． この入出力例は小課題 $ 2,\ 3 $ の制約を満たす． - - - - - - ### Sample Explanation 2 この入出力例はすべての小課題の制約を満たす． - - - - - - ### Sample Explanation 3 この入出力例は小課題 $ 2,\ 3 $ の制約を満たす．