[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 long integers x and y
declare exgcd taking in long long integers a and returning long longand b
    if b is equal to 0
        set x to 1
        set y to 0
        return a
    end of the block
    create long long d = exgcd(b, a % b)
    create long long t = x
    set x to y
    set y to the result of t - a / b * y
    return d
end of the block
define the main function
    create long long integers m, h1, al, x1, y1, h2, a2, x2, y2
    create long long integers p1, p2, q1, q2
    while cin >> m >> h1 >> a1 >> x1 >> y1 >> h2 >> a2 >> x2 >> y2 is truthy
        set p1, p2, q1, and q1 to 0
        for i = 1 to 2 * m
            set h1 to (h1 * x1 + y1) % m
            if h1 is equal to a1
                if p1 is equal to 0
                    set p1 to i
                else if q1 is equal to 0
                    set q1 to the result of i - p1
                    break loop
                end of the block
            end of the block
        end of the block
        for i = 1 to 2 * m
            set h2 to the result of (h2 * x2 + y2) % m
            if h2 is equal to a2
                if p2 is equal to 0
                    set p2 to i
                else if q2 is equal to 0
                    set q2 to the result of i - p2
                    break loop
                end of the block
            end of the block
        end of the block
        create long long d = exgcd(q1, -q2)
        create long long c = p2 - p1
        if d is equal to 0
            print "-1"
            continue to next loop iteration
        end of the block
        if c modulo d is truthy
            print "-1"
            continue to next loop iteration
        end of the block
        if d is less than 0, set d to -d
        if p1 is equal to 0 or p2 is equal to 0
            print "-1"
            continue to next loop iteration
        end of the block
        if q2 is equal to 0 and q1 is equal to 0 and p1 is not equal to p2
            print "-1"
            continue to next loop iteration
        end of the block
        if q2 is equal to 0 and p2 - p1 is less than 0 or q1 is equal to 0 and p1 - p2 is less than 0
            print "-1"
            continue to next loop iteration
        end of the block
        create long long k = c / d
        if the return value of exgcd(q1, -q2) is less than 0, set x to -x and set y to -y
        set x to the result of x * k
        set y to the result of y * k
        if x is less than 0 or y is less than 0
            while 1 is truthy
                set x to the result of x + q2 / d
                set y to the result of y + 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 then 0
            while 1 is truthy
                set x to the result of x - q2 / d
                set y to the result of y - q1 / d
                if x is less than 0 or y is less than 0, break loop
            end of the block
            set x to the result of x + q2 / d
            set y to the result of y + q1 / d
        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 (d < 0) d = -d;
        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;
        if (exgcd(q1, -q2) < 0) x = -x, y = -y;
        x *= k;
        y *= k;
        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;
}