B. Bigint
time limit per test
0.4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You might already know that, in most modern C++ compilers, int is a 32-bit integer, so it can store numbers from $$$-2^{31}$$$ (-2147483648) to $$$2^{31}-1$$$ (2147483647). If you use long long you can store 64-bit integers (around 18 digits long), but if you want to work with numbers longer than that, you are on your own.

In this problem we ask you to write code that can add arbitrarily long positive integers, and that can read and write them in the standard form (base 10 representation).

Your first instinct might be to use strings: every digit in your number is a char from '0' to '9'. This works great for input and output, but sums are kind of slow because your program must add digit by digit.

Your second instinct might be to use vector<int>, and make every number of your vector a "big-digit" in base $$$2^{31}$$$ (or $$$2^{32}$$$ if you know how to use unsigned ints). You can add two "big-digits" by transforming them first into "long long". Now sums are fast: every time you add up two "big-digits" you are adding a bit more than 9 of the old base-10 digits. But reading and writing requires translating base 10 numbers into base $$$2^{31}$$$ or $$$2^{32}$$$, which is not a trivial task.

Let's hope you have a third instinct that will allow you to solve this problem.

Input

The input consists of a number $$$n$$$, followed by $$$n$$$ arbitrary long numbers $$$x_1, \ldots, x_n$$$ given in base-10.

Then, the number $$$k$$$ of sums of the form $$$x_{i_1} + \ldots + x_{i_t}$$$ that your program must perform. For each sum, you will be given the number $$$t$$$ followed by $$$t$$$ indexes $$$i_1, \ldots, i_k$$$, all separated by spaces.

We guarantee that the size of the input or the output won't be larger than 1 megabyte. Make sure, though, that your program is using fast I/O for competitive programming.

Output

Output $$$k$$$ lines with the results of the $$$k$$$ sums, again in base 10.

Examples
Input
1
1
1
2 1 1
Output
2
Input
1
999999999
4
1 1
2 1 1
3 1 1 1
4 1 1 1 1
Output
999999999
1999999998
2999999997
3999999996
Input
4
1
999999999
1000000000
1000000001
3
2 1 2
2 1 3
4 1 2 3 4
Output
1000000000
1000000001
3000000001
Input
4
1234567890123456789012345678901234
11234567890123456789012345678901234
111234567890123456789012345678901234
1111234567890123456789012345678901234
3
1 1
4 1 2 3 4
4 4 3 2 1
Output
1234567890123456789012345678901234
1234938271560493827156049382715604936
1234938271560493827156049382715604936