<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

119. Magic Pairs

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


“Prove that for any integer X and Y if 5X+4Y is divided by 23 than 3X+7Y is divided by 23 too.” The task is from city Olympiad in mathematics in Saratov, Russia for schoolchildren of 8-th form. 2001-2002 year.


For given N and pair (A0, B0) find all pairs (A, B) such that for any integer X and Y if A0X+B0Y is divided by N then AX+BY is divided by N too (0<=A,B<N).


Input

Each input consists of positive integer numbers N, A0 and B0 (N,A0,B0£ 10000) separated by whitespaces.


Output

Write number of pairs (A, B) to the first line of output. Write each pair on a single line in order of non-descreasing A (and B in case of equal A). Separate numbers by single space.


Sample Input

3
1 2
Sample Output

3
0 0
1 2
2 1
Author	: Michael R. Mirzayanov
Resource	: PhTL #1 Training Contests
Date	: Fall 2001

<|response|>
1. Abridged Problem Statement
Given integers N, A₀, B₀ with 0 ≤ A₀, B₀ < N, find all pairs (A, B) with 0 ≤ A, B < N such that for every pair of integers X, Y,
 if A₀·X + B₀·Y ≡ 0 (mod N)
 then A·X + B·Y ≡ 0 (mod N).
Output the total number of such pairs, then list them sorted by A (and by B when A’s are equal).

2. Key Observations
- The set of integer pairs (X,Y) satisfying A₀X + B₀Y ≡ 0 mod N is a cyclic subgroup (a one-dimensional sublattice) in (ℤ/Nℤ)².
- Any integer multiple k of the congruence A₀X + B₀Y ≡ 0 mod N still vanishes:
 k·A₀·X + k·B₀·Y ≡ 0 (mod N).
- Therefore every pair of the form (k·A₀ mod N,  k·B₀ mod N) satisfies the requirement.
- One can show no other pairs work: any linear form vanishing on that cyclic subgroup must be a scalar multiple (in ℤ/Nℤ) of the original form.

3. Full Solution Approach
1. Read N, A₀, B₀.
2. Use a set of pairs so duplicates are removed and the iteration order is sorted automatically.
3. For k from 0 to N−1:
   a. Compute A = (k·A₀) mod N.
   b. Compute B = (k·B₀) mod N.
   c. Insert (A,B) into the set.
4. Print the number of pairs, then each pair on its own line in the set's (sorted) order.

Time complexity: O(N log N) due to the set insertions. Memory: O(N).

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, a0, b0;

void read() { cin >> n >> a0 >> b0; }

void solve() {
    // The valid pairs (A, B) are exactly the integer multiples of (A0, B0)
    // taken modulo N: (k*A0 mod N, k*B0 mod N) for k = 0..N-1. Generate all of
    // them, deduplicate, and output sorted by A then B.

    set<pair<int, int>> pairs;
    for(int k = 0; k < n; k++) {
        pairs.insert({(int)((int64_t)k * a0 % n), (int)((int64_t)k * b0 % n)});
    }

    cout << pairs.size() << '\n';
    for(auto& p: pairs) {
        cout << p.first << ' ' << p.second << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
def main():
    # Read input values
    N = int(input().strip())
    A0, B0 = map(int, input().split())

    # Collect all k*(A0,B0) mod N
    pairs = []
    for k in range(N):
        A = (k * A0) % N
        B = (k * B0) % N
        pairs.append((A, B))

    # Remove duplicates by converting to a set, then back to a sorted list
    unique_pairs = sorted(set(pairs))

    # Print the number of valid pairs
    print(len(unique_pairs))
    # Print each pair on its own line
    for A, B in unique_pairs:
        print(A, B)

if __name__ == "__main__":
    main()
```
