A linear congruential generator

The classic way computers make pseudo-random numbers is one line of arithmetic, repeated. Run it.

What to build

A program that prints the numbers produced by a linear congruential generator.

Requirements

  • Starting from the seed, compute x ← (a × x + c) mod m, n times.
  • Print the n values on one line, separated by spaces.

Input

One line: a, c, m, seed and n.

Output

One line.

Constraints

All whole numbers; 1 ≤ m ≤ 10⁹; 1 ≤ n ≤ 1000.

Example

Input:

5 3 16 7 5

Output:

6 1 8 11 10

Why it works

Each value depends only on the previous one, so the whole sequence is fixed by the seed: that makes it repeatable, and good constants make it look random.

Examples

Example 1 · Input
5 3 16 7 5
Expected output
6 1 8 11 10
Example 2 · Input
1 1 10 0 4
Expected output
1 2 3 4

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Each step: x = (a × x + c) % m.

Hint 2

Start from the seed and print each new x, not the seed itself.

Solution

Show one correct solution (try it yourself first)
a, c, m, x, n = map(int, input().split())
out = []
for _ in range(n):
    x = (a * x + c) % m
    out.append(x)
print(*out)

Lesson: Sampling and randomness →