111 . Firepersons
Description
The Association for Courtly Manners, an international organization for standardization
of social interactions (Better known under the name Absurdly Clumsy Moralists, but let's
not take prejudice.) has decided to create a new international standard defining
ranks of firepersons (Formerly firemen, but the international standards
of course must be politically correct.) - each fireperson receives an integer number
describing his rank and when they arrive to a fire, they must enter the fire ground
in order of increasing ranks and the low ranked firepersons must keep the fire burning
long enough for the high ranked firepersons to enjoy extinguishing sufficiently.
The ranks are assigned according to an Arbitrary Constant Multiplier Sequence. An ACM-sequence
of order k is an integer sequence defined by its first k terms
a0, a1,...ak-1 and
a recurrence relation 
mod 10 000 for
n >= k,
where the bi's are integer constants. The i-th oldest fireperson then gets
rank ai.
Your task is to calculate the rank of the i-th fireperson, given parameters of the
ACM-sequence and the number i.
Input Format
The input consists of several instances. Each instance is described on a single
line containing the following integers separated by a single space: k, a0,
, ak-1, b1, , bk, i. Here
1 <= k <= 100 is the order of the sequence,
0 <= ai < 10 000 are the first k elements of the sequence,
0 <= bi < 10 000 are the
multipliers and
0 <= i < 1 000 000 000 is the number of the element we ask for.
The input ends with a line containing a number 0.
Output Format
The output consists of several lines corresponding to the instances on the input.
The l-th line contains a single integer ai which is the i-th element of the
sequence described by the l-th input instance.
Sample Input 1
2 0 1 1 1 6 0
Sample Output 1
8
Hints
Problem Source
Migrated from old NTUJ.
Subtasks
| No. | Testdata Range | Score |
|---|