#include <vector>
#include "Alice.h"

std::vector<std::pair<int, int> > Alice(){
    std::vector<std::pair<int, int> > vec;
    long long x = setN(5000);
    for (int i = 1; i < 5000; i++)
        vec.emplace_back(x % i + 1, i + 1);
    return vec;
}

#include <vector>
#include "Bob.h"
typedef long long Int;

// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().

inline Int exgcd(Int x, Int y, Int z, Int& p, Int& q) {
    // xp + yq = z
    if (y == 0) {
        p = z / x, q = 0;
        return x < 0 ? -x : x;
    }
    // yp' + (x - x / y * y)q' = z
    Int p0, q0;
    Int ret = exgcd(y, x % y, z, p0, q0);
    // x * q' + y * (-x / y * q' + p') = z
    // p = q', q = p' - x / y * q'
    p = q0, q = p0 - x / y * q0;
    return ret;
}

Int Bob(std::vector<std::pair<int,int> > V){
    Int a = 1, b = 0;
    // X = b (mod a)
    for (auto [A, B] : V) {
        A = A - 1, B = B - 1;
        if (A > B) std::swap(A, B);
        if (b % A == B) continue;
        // X = B (mod A)
        // X = b (mod a)
        // X = b + pa = B + qA
        // ap - Aq = B - b
        Int p, q;
        Int g = exgcd(a, -A, B - b, p, q);
        Int dlt = A / g;
        p = (p % dlt + dlt) % dlt;
        b = b + a * p;
        a = a / g * A;
        b %= a;
    }
    return b;
}