[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
declare long long variables x and y
exgcd is a long long function with long long arguments a and b
    if b = 0
        assign 1 to x
        assign 0 to y
        return a
    end of the block
    declare long long d = exgcd(b, a % b)
    declare long long variable t = x
    change x to y
    set y to t - a / b * y
    return d
end of the block
define the main function
    create long longs m, h1, a1, x1, y1, h2, a2, x2 and y2
    declare long longs p1, p2, q1 and q2
    loop, reading m, h1, a1, x1, y1, h2, a2, x2 and y2 from the input
        change p1, p2, q1 and q2 to 0
        change i from 1 to 2 * m inclusive in a loop
            set h1 to (h1 * x1 + y1) % m
            if h1 is equal to a1
                if p1 = 0
                    assign i to p1
                else if q1 is equal to 0
                    assign i - p1 to q1
                    break the loop
                end of the block
            end of the block
        end of the block
        for i = 1 to 2 * m inclusive
            set h2 to (h2 * x2 + y2) % m
            if h2 = a2
                if p2 = 0
                    set p2 to i
                else if q2 = 0
                    assign i - p2 to q2
                    stop the loop
                end of the block
            end of the block
        end of the block
        declare long long d = exgcd(q1, -q2)
        create long long c = p2 - p1
        if d = 0
            print "-1" to stdout
            go to the start of the loop
        end of the block
        if c % d != 0
            print "-1" to stdout
            skip the rest of the loop
        end of the block
        if p1 = 0 or p2 is equal to 0
            print "-1" to stdout
            skip the rest of the loop
        end of the block
        if q2 = 0 and q1 = 0 and p1 != p2
            print "-1" to stdout
            skip the rest of the loop
        end of the block
        if (q2 = 0 and p2 - p1 < 0) is true or (q1 = 0 and p1 - p2 < 0) is true
            print "-1" to standard output
            skip the rest of the loop
        end of the block
        declare long long variable k = c / d
        multiply x by k
        multiply y by k
        if d is less than 0, invert the sign of d
        if x < 0 or y < 0
            start infinite loop
                add q2 / d to x
                add q1 / d to y
                if x >= 0 and y >= 0, stop the loop
            end of the block
        end of the block
        if x > 0 and y > 0
            start infinite loop
                subtract q2 / d from x
                decrease y by q1 / d
                if x < 0 or y < 0
                    add q2 / d to x
                    add q1 / d to y
                    break
                end of the block
            end of the block
        end of the block
        create long long ans = x * q1 + p1
        print ans
    end of the block
    return to indicate successful execution
end of the block

[CODE]:

long long x, y;
long long exgcd(long long a, long long b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b, a % b);
    long long t = x;
    x = y;
    y = t - a / b * y;
    return d;
}
int main() {
    long long m, h1, a1, x1, y1, h2, a2, x2, y2;
    long long p1, p2, q1, q2;
    while (cin >> m >> h1 >> a1 >> x1 >> y1 >> h2 >> a2 >> x2 >> y2) {
        p1 = p2 = q1 = q2 = 0;
        for (long long i = 1; i <= 2 * m; i++) {
            h1 = (h1 * x1 + y1) % m;
            if (h1 == a1) {
                if (p1 == 0)
                    p1 = i;
                else if (q1 == 0) {
                    q1 = i - p1;
                    break;
                }
            }
        }
        for (long long i = 1; i <= 2 * m; i++) {
            h2 = (h2 * x2 + y2) % m;
            if (h2 == a2) {
                if (p2 == 0)
                    p2 = i;
                else if (q2 == 0) {
                    q2 = i - p2;
                    break;
                }
            }
        }
        long long d = exgcd(q1, -q2);
        long long c = p2 - p1;
        if (d == 0) {
            puts("-1");
            continue;
        }
        if (c % d) {
            puts("-1");
            continue;
        }
        if (p1 == 0 || p2 == 0) {
            puts("-1");
            continue;
        }
        if (q2 == 0 && q1 == 0 && p1 != p2) {
            puts("-1");
            continue;
        }
        if ((q2 == 0 && p2 - p1 < 0) || (q1 == 0 && p1 - p2 < 0)) {
            puts("-1");
            continue;
        }
        long long k = c / d;
        x *= k;
        y *= k;
        if (d < 0) d = -d;
        if (x < 0 || y < 0) {
            while (1) {
                x += q2 / d;
                y += q1 / d;
                if (x >= 0 && y >= 0) break;
            }
        }
        if (x > 0 && y > 0) {
            while (1) {
                x -= q2 / d;
                y -= q1 / d;
                if (x < 0 || y < 0) {
                    x += q2 / d;
                    y += q1 / d;
                    break;
                }
            }
        }
        long long ans = x * q1 + p1;
        cout << ans << endl;
    }
    return 0;
}