Random paths P33549

A random walk consists of a sequence of positions, each one obtained from the previous one by making a random step. In this exercise we consider random walks in the plane, starting at $(0, 0)$. Let $k$ be a strictly positive natural number. Each step will be an increment between $-k$ and $k$, random and independent, of the two coordinates.

Hence, we need a source of randomness. The usual way to simulate it consists in generating pseudorandom numbers. These numbers are the result of an algorithm, so they are not really random, but they look random enough. The linear congruential generators are defined with four natural numbers $m$ (module), $a$ (multiplier), $b$ (adder) and $s$ (initial seed). The generated sequence is $$x_1 = (a*s + b) \mbox{ mod } m, \quad x_2 = (a*x_1 + b) \mbox{ mod } m, \quad x_3 = (a*x_2 + b) \mbox{ mod } m, \quad \dots$$

For instance, if $m = 9, a = 2, b = 7, s = 3$, then we get $$x_1 = (2*3 + 7) \mbox{ mod } 9 = 4, \quad x_2 = (2*4 + 7) \mbox{ mod } 9 = 6, \enspace 1, \enspace 0, \enspace 7, \enspace 3, \enspace 4, \enspace 6, \enspace \dots$$

These numbers are between 0 and $m - 1$, but in this exercise we need numbers between $-k$ and $k$. The easiest way to achieve this is with the following code; use it just like that:

    int random(int k, int m, int a, int b, int& s) {
        s = (a*s + b)%m;
        return s%(2*k + 1) - k;
    }

Following with the example, for $k = 2$ the sequence of increments is $$4 \mbox{ mod } 5 \, - \, 2 = 2, \enspace 6 \mbox{ mod } 5 \, - \, 2 = -1, \enspace 1 \mbox{ mod } 5 \, - \, 2 = -1, \enspace -2, \enspace 0, \enspace 1, \enspace 2, \enspace -1, \enspace \dots$$ and, if we increase the first coordinate before the second one, the steps are $$(0, 0), \enspace (2, -1), \enspace (1, -3), \enspace (3, -3), \enspace \dots$$

Write a program to compute the first $n$ steps of a sequence of random walks defined by $k$, $m$, $a$, $b$ and $s$.

Input

Input is all natural numbers, and consists of several cases, each one in two lines. The first line contains $n$ and $k$. The second line contains $m$, $a$, $b$ and $s$. All $n$, $k$ and $m$ are strictly positive, and $a$, $b$ and $s$ are less than $m$.

Output

For each case of the input, first print its number starting at 1, followed by the walk of $n$ steps defined by $k$, $m$, $a$, $b$ and $s$. If some position gets repeated, indicate it and stop the walk as it is shown in the example. Print an empty line at the end of each case.