Extrapolation Using a Difference Table

A very old technique for extrapolating a sequence of values relies on a difference table. For example, the difference table for the four values $3, 6, 10, 15$ can be displayed like this.

The original sequence appears in the first column. Each entry in the second column is the difference between adjacent entries in the first column; these are the first differences. Each entry in the third column is the difference between adjacent entries in the second column (the second differences), and so on. The last column always holds exactly one value. If the sequence has $n$ values, the completed table has $n$ columns, and the single value in column $n$ is the $(n-1)$-th difference.

To extrapolate, we assume the $(n-1)$-th differences are constant (nothing in the data suggests otherwise). Under that assumption we compute the next entry in the $(n-2)$-th difference column, then the $(n-3)$-th column, and so on, until we reach the next entry of the first column — the next value of the sequence. The table below adds four entries (boxed) to extend the example, producing the next value $21$. The process can continue as far as we like, always assuming the $(n-1)$-th differences stay constant.

The input is a series of extrapolation requests. Each request begins with an integer $n$, the number of values in the sequence to be extended. When $n$ is $0$, the program terminates. Otherwise $n$ is at most $10$ and is followed by $n$ integers, the given elements of the sequence. Each request ends with $k$ (at least $1$), the number of extrapolation steps to perform: you add $k$ entries to each column of the difference table. Number the given values $1$ through $n$.

Tokens may be separated by any amount of whitespace.

For each request, extrapolate the original sequence $k$ times and report the $(n+k)$-th value. Print exactly one line per request in the form Term X of the sequence is Y, where X is $n+k$ and Y is the extrapolated value.

Hint: $k$ has no stated upper bound, so you may not be able to hold the entire difference table in memory.