Let's say Pak Chanek has an array \(A\) consisting of \(N\) positive integers. Pak Chanek will do a number of operations. In each operation, Pak Chanek will do the following:
- Choose an index \(p\) (\(1 \leq p \leq N\)).
- Let \(c\) be the number of operations that have been done on index \(p\) before this operation.
- Decrease the value of \(A_p\) by \(2^c\).
- Multiply the value of \(A_p\) by \(2\).
After each operation, all elements of \(A\) must be positive integers.
An array \(A\) is said to be sortable if and only if Pak Chanek can do zero or more operations so that \(A_1 < A_2 < A_3 < A_4 < \ldots < A_N\).
Pak Chanek must find an array \(A\) that is sortable with length \(N\) such that \(A_1 + A_2 + A_3 + A_4 + \ldots + A_N\) is the minimum possible. If there are more than one possibilities, Pak Chanek must choose the array that is lexicographically minimum among them.
Pak Chanek must solve the following things:
- Pak Chanek must print the value of \(A_1 + A_2 + A_3 + A_4 + \ldots + A_N\) for that array.
- \(Q\) questions will be given. For the \(i\)-th question, an integer \(P_i\) is given. Pak Chanek must print the value of \(A_{P_i}\).
Help Pak Chanek solve the problem.
Note: an array \(B\) of size \(N\) is said to be lexicographically smaller than an array \(C\) that is also of size \(N\) if and only if there exists an index \(i\) such that \(B_i < C_i\) and for each \(j < i\), \(B_j = C_j\).
Output
Print \(Q+1\) lines. The \(1\)-st line contains an integer representing \(A_1 + A_2 + A_3 + A_4 + \ldots + A_N\). For each \(1 \leq i \leq Q\), the \((i+1)\)-th line contains an integer representing \(A_{P_i}\).
Note
In the first example, the array \(A\) obtained is \([1, 2, 3, 3, 4, 4]\). We can see that the array is sortable by doing the following operations:
- Choose index \(5\), then \(A = [1, 2, 3, 3, 6, 4]\).
- Choose index \(6\), then \(A = [1, 2, 3, 3, 6, 6]\).
- Choose index \(4\), then \(A = [1, 2, 3, 4, 6, 6]\).
- Choose index \(6\), then \(A = [1, 2, 3, 4, 6, 8]\).