[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]:
x, y = long long integers
declare exgcd that takes two arguments, long long integers a and b
    if b is 0
        set x to 1
        set y to 0
        return a
    end of the block
    d = long long integer set to exgcd of b and a modulo b
    t = long long integer set to x
    set x to y
    set y to t - a / b * y
    return d
end of the block
define the main function
    m, h1, a1, x1, y1, h2, a2, x2, y2 = long long integers
    p1, p2, q1, q2 = long long integers
    while reading m, h1, a1, x1, y1, h2, a2, x2, and y2
        set p1, p2, q1, q2 to 0
        for i = 1 to 2 * m inclusive
            set h1 to h1 * x1 + y1 modulo m
            if h1 is a1
                if p1 is 0
                    set p1 to i
                else if q1 is 0
                    set q1 to i - p1
                    break
                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 modulo m
            if h2 is a2
                if p2 is 0
                    set p2 to i
                else if q2 is 0
                    set q2 to i - p2
                    break
                end of the block
            end of the block
        end of the block
        d = long long integer set to exgcd of q1 and -q2
        c = long long integer set to p2 - p1
        if d is 0
            puts "-1"
            continue
        end of the block
        if c modulo d
            puts "-1"
            continue
        end of the block
        if p1 is 0 or p2 is 0
            puts "-1"
            continue
        end of the block
        if q2 is 0 and q1 is 0 and p1 != p2
            puts "-1"
            continue
        end of the block
        if q2 is 0 and p2 - p1 < 0 or q1 is 0 and p1 - p2 < 0
            puts "-1"
            continue
        end of the block
        k = long long integer set to c / d
        multiply x by k
        multiply y by k
        if d < 0, set d to -d
        if x < 0 or y < 0
            while 1 exists
                add q2 / d to x
                add q1 / d to y
                if x >= 0 and y >= 0, break
            end of the block
        end of the block
        if x > 0 and y > 0
            while 1 exists
                subtract q2 / d from x
                subtract q1 / d from y
                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
        ans = long long integer set to 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;
}