[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]:
create long longs x, y
declare exgcd with long longs a, b as arguments returning long long
    if b is 0
        set x to 1
        set y to 0
        return a from function
    end of the block
    crate long long d with d = result of run exgcd with b, a % b as arguments
    create long long t with t = x
    set x to y
    set y to t - a / b * y
    return d from function
end of the block
define the main function
    create long longs m, h1, a1, x1, y1, h2, a2, x2, y2
    create long longs p1, p2, q1, q2
    while read m read h1 read a1 read x1 read y1 read h2 read a2 read x2 read y2 is true
        set p1 to p2 to q1 to q2 to 0
        for i = 1 to 2 * m inclusive
            set h1 to (h1 * x1 + y1) % m
            if h1 is a1
                if p1 is 0
                    set p1 to i
                else if q1 is 0
                    set q1 to i - p1
                    break 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 is a2
                if p2 is 0
                    set p2 to i
                else if q2 is 0
                    set q2 to i - p2
                    break loop
                end of the block
            end of the block
        end of the block
        create long long d with d = result of run exgcd with q1, -q2 as arguments
        create long long c with c = p2 - p1
        if d is 0
            print "-1"
            break current loop iteration
        end of the block
        if c % d
            print "-1"
            break current loop iteration
        end of the block
        if p1 is 0 or p2 is 0
            print "-1"
            break current loop iteration
        end of the block
        if q2 is 0 and q1 is 0 and p1 is not p2
            print "-1"
            break current loop iteration
        end of the block
        if ( q2 is 0 and p2 - p1 is less than 0 ) or ( q2 is 0 and p1 - p2 is less than 0 )
            print "-1"
            break current loop iteration
        end of the block
        create long long k with k = c / d
        set x to x * k
        set y to y * k
        if d is less than 0, set d to -d
        if x is less than 0 or y is less than 0
            while 1 is true
                increment x by q2 / d
                increment y by q1 / d
                if x is greater than or equal to 0 and y is greater than or equal to 0, break loop
            end of the block
        end of the block
        if x is greater than 0 and y is greater than 0
            while 1 is true
                decrement x by q2 / d
                decrement y by q1 / d
                if x is less than 0 or y is less than 0, break loop
            end of the block
            increment x by q2 / d
            increment y by q1 / d
        end of the block
        create long long ans with ans = x * q1 + p1
        print ans print newline
    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) break;
            }
            x += q2 / d;
            y += q1 / d;
        }
        long long ans = x * q1 + p1;
        cout << ans << endl;
    }
    return 0;
}