Windmill Lottery

In Windmillia, there is a special national lottery system. Everyone can get a number and participate in countless draws. The numbers owned by the players are put in two lines (Line1 and Line2) based on the number specification, and they will belong to that line forever. The numbers and draws are generated based on the following rules:

• LineHelper_n = (((La * LineHelper_n – 1 + Lb) * Lc) + Ld) mod (10⁹ + 7)
• Line_n = LineHelper_n mod  3 + 1
  The Line_n number can be 1 or 2, which is used to insert a number into the specific line, or 3, which means performing draw if it is possible.
  
• Number_n = (((a * Number_n – 1 + b) * c) % d)
  If Line_n is 1 or 2, then Number_n is used as a number. Else, Number_n is used as rotationCount for the draw.
  
• Offset_i = (((La * Offset_i – 1 + Lb) * Lc) + Ld) mod 21 – 10
  Offset is computed only when Line_n is 3.

A draw can take place at any time if the count of the numbers in the two lines have the same parity. A draw is performed as follows:

• The two lines are being sorted.
• The middle point of Line1 and Line2 is placed on each other (in case of even count number, a virtual center is selected in both lines, between the two middle numbers).
• A rotation count is set (rotationCount) and Line2 is rotated around the middle point rotationCount times by 180 degrees, while Line1 stays fixed.
• From now on, we consider the middle point being the middle point of the two lines if the number of elements in either is an odd number; otherwise, middle point is the middle-left point if Offset_i < 0, and middle-right point if Offset_i ≥ 0, in both lines.
• We take the two numbers with Offset_i offset from the middle points, and calculate their sum modulo m, where m is the maximum value found already in the two lines. If a line is too short to have a corresponding position, we can take 0 for that number.
• The computed value will be the winning number of the draw.

Input Specification

The first line contains the values of a, b, c, d, and the starting value for Number (five space-separated numbers). The second line contains the values of La, Lb, Lc, Ld, and the starting value for LineHelper (five space-separated numbers). The third line contains the initial value of Offset and the value of n, the overall number of numbers generated, separated by a space.

Input Limits and Constraints

• 1 ≤ lottery numbers ≤ 10¹⁰;
• 0 ≤ lottery numbers count ≤ 10⁶;
• –10 ≤ Offset ≤ 10;
• 0 ≤ rotationCount ≤ 10¹⁰;
• 1 ≤ a, b, c, d, La, Lb, Lc, Ld ≤ 10⁵.

Output Specification

The output should contain the result of every draw, one line for every number.

Sample Input

1. 1 1 1 101 123
2. 1 1 1 1 1
3. 2 30

download as text file

Output for Sample Input

1. 54

download as text file

Explanation

After generating 30 numbers, the two arrays are sorted, because a draw is generated. After sorting, they are placed so that the middle points are in the same column:

Line1: 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65
Line2: 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67

The draw is generated with Offset = –6 and rotationCount = 68. Line2 is rotated 68 times, and the –⁠6th elements relative to the middle points are added together: (26 + 28) = 54 (mod 67). The result is printed. There was only one draw.