Board Game Sequences Advanced - A possible New Problem

You should have solved the Board Game Sequences problem before attempting this one. The problem description remains exactly the same. The only difference is that the board sizes are now considerably larger. You may need to find a more sophisticated approach to solve this version of the problem.

Example:

input:
1 2 5 9 18 23
6
100000000
1000000000
100000000000000
10000000000000000
100000000000000000
1000000000000000000

answer:
100135026 468319036 178877739 365242738 229053783 947435429