// ================================================================
// yukicoder No.187 中華風 (Hard)
// (URL: https://yukicoder.me/problems/no/187)
// TypeScript (Node.js, using InputScanner) [Main] Submission
// ================================================================

function Main(inputText: string): void {
    const scanner = new InputScanner(inputText);
    // Add your code here
    const N = scanner.int()!;
    const [X, Y] = scanner.bigint(N, 2);
    const MOD = 1000000007n;
    // ANS ≡ X_i (mod Y_i)がたくさん与えられるので、CRTをぶん回す
    const [ans, lcm] = ExtendedMath.crt(X, Y);
    if (ans === 0n && lcm === 0n) {
        console.log(-1);
    } else if (ans === 0n) {
        console.log((lcm % MOD).toString());
    } else {
        console.log((ans % MOD).toString());
    }
}

/**
 * 入力をスキャンし、トークンを順に取得するためのクラスです。
 * - .str()で文字列、.num()で浮動小数点数、.int()で整数、.bigint()でBigIntとして取得できます。
 * - 引数なしだと1つ、引数1つ(n)だと最大長さnの配列、引数2つ(n, g)だと長さgの最大長さnの配列の配列として取得できます。
 */
class InputScanner {
    #str: string;
    #len: number;
    #idx: number;

    /** 新しい入力スキャナーインスタンスを生成します。 */
    constructor(str: string) {
        this.#str = str;
        this.#len = str.length;
        this.#idx = 0;
    }
    /** ある文字がトークンの区切りとみなせる文字(' '・'\n'・'\r'・'\t')であるかを判定します。 */
    #isSpace(c: number): boolean {
        return c === 32 || c === 10 || c === 13 || c === 9;
    }
    /** #idxをトークンの区切りとみなせる文字の直後まで進めます。 */
    #skipSpaces() {
        while (this.#idx < this.#len) {
            const c = this.#str.charCodeAt(this.#idx);
            if (!this.#isSpace(c)) break;
            this.#idx++;
        }
    }

    #read<T>(fn: (token: string) => T): T | undefined;
    #read<T>(fn: (token: string) => T, n: number): T[];
    #read<T>(fn: (token: string) => T, n: number, g: number): T[][];
    /**
     * @private
     * トークンを読んだうえで、そのトークンを渡された関数に通して変換して返します。
     * @param fn - トークンを変換する関数
     * @param n - 取得するトークンの最大数
     * @param g - トークンのグループ数(トークンいくつで1巡するか)
     */
    #read<T>(fn: (token: string) => T, n?: number, g?: number): T | T[] | T[][] | undefined {
        // nがない場合: 1トークン読む
        if (n == null) {
            this.#skipSpaces();
            if (this.#idx >= this.#len) return undefined;
            const startIdx = this.#idx;
            while (this.#idx < this.#len) {
                const c = this.#str.charCodeAt(this.#idx);
                if (this.#isSpace(c)) break;
                this.#idx++;
            }
            const token = this.#str.substring(startIdx, this.#idx);
            return fn(token);
        }
        // nだけある場合: nトークン読む
        else if (g == null) {
            const result: T[] = [];
            for (let i = 0; i < n; i++) {
                const token = this.#read(fn);
                if (token == null) break;
                result.push(token);
            }
            return result;
        }
        // nもgもある場合: n×gトークン読む
        else {
            const result: T[][] = Array.from({ length: g }, () => []);
            read: for (let i = 0; i < n; i++) {
                for (let j = 0; j < g; j++) {
                    const token = this.#read(fn);
                    if (token == null) break read;
                    result[j].push(token);
                }
            }
            return result;
        }
    }
    /**
     * トークンを1つ、stringとして取得します。
     * - もうトークンが存在しない場合、undefinedを返します。
     */
    str(): string | undefined;
    /**
     * トークンを(最大)n個、string[]として取得します。
     * - 残りトークンがn個に満たない場合、長さn未満のstring[]が返されます。
     * @param n 取得するトークンの最大数
     */
    str(n: number): string[];
    /**
     * トークンを(最大)n×g個、string[][]として取得します。
     * - 戻り値のi(0≦i<g)番目の配列は、残存トークンのうちi番目, g+i番目, 2g+i番目, ..., (n-1)g+i番目のトークンを順に取得したstring[]です。
     * - 戻り値の配列の長さは必ずg個ですが、残存トークンが不足している場合は長さnに満たない配列や空配列が含まれることがあります。
     * @param n 取得するトークンの最大数
     * @param g トークンのグループ数(トークンいくつで1巡するか)
     */
    str(n: number, g: number): string[][];
    str(n?: number, g?: number): string | string[] | string[][] | undefined {
        const mapFn = (token: string) => token;
        if (n == null) return this.#read(mapFn);
        else if (g == null) return this.#read(mapFn, n);
        else return this.#read(mapFn, n, g);
    }

    /**
     * トークンを1つ、number(64bit浮動小数点数)として取得します。小数を許容します。
     * - もうトークンが存在しない場合、undefinedを返します。
     */
    num(): number | undefined;
    /**
     * トークンを(最大)n個、number[]として取得します。各要素は小数を許容します。
     * - 残りトークンがn個に満たない場合、長さn未満のnumber[]が返されます。
     * @param n 取得するトークンの最大数
     */
    num(n: number): number[];
    /**
     * トークンを(最大)n×g個、number[][]として取得します。各要素は小数を許容します。
     * - 戻り値のi(0≦i<g)番目の配列は、残存トークンのうちi番目, g+i番目, 2g+i番目, ..., (n-1)g+i番目のトークンを順に取得したnumber[]です。
     * - 戻り値の配列の長さは必ずg個ですが、残存トークンが不足している場合は長さnに満たない配列や空配列が含まれることがあります。
     * @param n 取得するトークンの最大数
     * @param g トークンのグループ数(トークンいくつで1巡するか)
     */
    num(n: number, g: number): number[][];
    num(n?: number, g?: number): number | number[] | number[][] | undefined {
        const mapFn = (token: string) => Number.parseFloat(token);
        if (n == null) return this.#read(mapFn);
        else if (g == null) return this.#read(mapFn, n);
        else return this.#read(mapFn, n, g);
    }

    /**
     * トークンを1つ、整数値のnumberとして取得します。
     * - もうトークンが存在しない場合、undefinedを返します。
     */
    int(): number | undefined;
    /**
     * トークンを(最大)n個、number[]として取得します。
     * - 残りトークンがn個に満たない場合、長さn未満の整数値の配列(number[])が返されます。
     * @param n 取得するトークンの最大数
     */
    int(n: number): number[];
    /**
     * トークンを(最大)n×g個、整数値のnumber[][]として取得します。
     * - 戻り値のi(0≦i<g)番目の配列は、残存トークンのうちi番目, g+i番目, 2g+i番目, ..., (n-1)g+i番目のトークンを順に整数値として取得したnumber[]です。
     * - 戻り値の配列の長さは必ずg個ですが、残存トークンが不足している場合は長さnに満たない配列や空配列が含まれることがあります。
     * @param n 取得するトークンの最大数
     * @param g トークンのグループ数(トークンいくつで1巡するか)
     */
    int(n: number, g: number): number[][];
    int(n?: number, g?: number): number | number[] | number[][] | undefined {
        const mapFn = (token: string) => Number.parseInt(token);
        if (n == null) return this.#read(mapFn);
        else if (g == null) return this.#read(mapFn, n);
        else return this.#read(mapFn, n, g);
    }

    /**
     * トークンを1つ、BigIntとして取得します。
     * - もうトークンが存在しない場合、undefinedを返します。
     */
    bigint(): bigint | undefined;
    /**
     * トークンを(最大)n個、bigint[]として取得します。
     * - 残りトークンがn個に満たない場合、長さn未満のBigIntの配列(bigint[])が返されます。
     * @param n 取得するトークンの最大数
     */
    bigint(n: number): bigint[];
    /**
     * トークンを(最大)n×g個、bigint[][]として取得します。
     * - 戻り値のi(0≦i<g)番目の配列は、残存トークンのうちi番目, g+i番目, 2g+i番目, ..., (n-1)g+i番目のトークンを順に取得したbigint[]です。
     * - 戻り値の配列の長さは必ずg個ですが、残存トークンが不足している場合は長さnに満たない配列や空配列が含まれることがあります。
     * @param n 取得するトークンの最大数
     * @param g トークンのグループ数(トークンいくつで1巡するか)
     */
    bigint(n: number, g: number): bigint[][];
    bigint(n?: number, g?: number): bigint | bigint[] | bigint[][] | undefined {
        const mapFn = (token: string) => BigInt(token);
        if (n == null) return this.#read(mapFn);
        else if (g == null) return this.#read(mapFn, n);
        else return this.#read(mapFn, n, g);
    }
}

// ======== Copied from AyaExpTech Arcane ========
// Using: AXT-AyaKoto/axt-arcane-bundler (https://github.com/AXT-AyaKoto/axt-arcane-bundler)
// Package: jsr:@ayaexptech/arcane@2.0.0-alpha.4
// Resolved version (sources): 2.0.0-alpha.4
// Selected exports: ExtendedMath

/**
 * 数学的な関数のうち、JavaScript標準の`Math`にないものを提供するユーティリティクラスです。
 * - number: 最大公約数・最小公倍数・約数列挙・popcount(下位32bit)
 * - bigint: 最大公約数・最小公倍数・拡張ユークリッドの互除法・min, max, abs, sign・整数平方根
 * - bigint: 冪乗mod・逆元・中国剰余定理(CRT)
 * - ミラー-ラビン素数判定法
 */
class ExtendedMath {
    /**
     * 2つの整数の最大公約数を求めます。
     * なお、gcd(0, 0) = 0、gcd(a, 0) = gcd(0, a) = |a| とします。
     *
     * 時間計算量: 最悪 O(log(min(|a|, |b|)))
     *
     * @example number型の場合
     * ```ts
     * ExtendedMath.gcd(48, 18) // => 6
     * ```
     *
     * @example bigint型の場合
     * ```ts
     * ExtendedMath.gcd(48n, 18n) // => 6n
     * ```
     *
     * @template T - 引数と返り値の型。numberまたはbigint。
     * @param a - 1つ目の整数。
     * @param b - 2つ目の整数。
     * @returns aとbの最大公約数。引数と同じ型で返されます。
     */
    static gcd<T extends number | bigint>(a: T, b: T): T {
        while (b) {
            [a, b] = [b, (a % b) as T];
        }
        return a < 0 ? (-a as T) : a;
    }

    /**
     * 2つの整数の最小公倍数を求めます。
     * なお、lcm(0, 0) = 0、lcm(a, 0) = lcm(0, a) = 0 とします。
     *
     * 時間計算量: 最悪 O(log(min(|a|, |b|))) （gcdの計算に依存）
     *
     * @example number型の場合
     * ```ts
     * ExtendedMath.lcm(12, 18) // => 36
     * ```
     *
     * @example bigint型の場合
     * ```ts
     * ExtendedMath.lcm(12n, 18n) // => 36n
     * ```
     *
     * @template T - 引数と返り値の型。numberまたはbigint。
     * @param a - 1つ目の整数。
     * @param b - 2つ目の整数。
     * @returns aとbの最小公倍数。引数と同じ型で返されます。
     */
    static lcm<T extends number | bigint>(a: T, b: T): T {
        if (a === 0 || b === 0 || a === 0n || b === 0n) {
            return (typeof a === "bigint" ? 0n : 0) as T;
        }
        return ((a * b) / ExtendedMath.gcd(a, b)) as T;
    }

    /**
     * 非負整数a, bについて、ax + by = g を満たす整数x, yを求めます。
     * なお、ここで g = gcd(a, b) とし、a = b = 0 のときは g = 0 とします。
     *
     * 時間計算量: O(log(min(a, b)))
     *
     * @example
     * ```ts
     * const [g, x, y] = ExtendedMath.extendedGCD(30n, 21n);
     * console.log(g); // => 3n
     * console.log(x); // => -2n
     * console.log(y); // => 3n
     * // 確認: 30*(-2) + 21*3 === 3
     * console.log(30n * x + 21n * y === g); // => true
     * ```
     *
     * @param a - 非負整数a
     * @param b - 非負整数b
     * @returns [g, x, y] - gはaとbの最大公約数、xとyはax + by = gを満たす整数
     */
    static extendedGCD(a: bigint, b: bigint): [g: bigint, x: bigint, y: bigint] {
        let r0 = a;
        let r1 = b;
        let x0 = 1n;
        let x1 = 0n;
        let y0 = 0n;
        let y1 = 1n;

        while (r1 !== 0n) {
            const q = r0 / r1;
            const temp = r1;
            r1 = r0 % r1;
            r0 = temp;

            const tempX = x0;
            x0 = x1;
            x1 = tempX - q * x1;

            const tempY = y0;
            y0 = y1;
            y1 = tempY - q * y1;
        }

        return [r0, x0, y0];
    }

    /**
     * 整数`n`の正の約数を列挙します。
     * ただし、`n === 1`なら`[1]`、`n < 1`なら`[]`を返します。
     *
     * 時間計算量: O(√n)
     *
     * @example
     * ```ts
     * ExtendedMath.getDivisors(28) // => [1, 2, 4, 7, 14, 28]
     * ExtendedMath.getDivisors(1) // => [1]
     * ExtendedMath.getDivisors(0) // => []
     * ExtendedMath.getDivisors(-5) // => []
     * ```
     *
     * @param n - 対象の整数
     * @returns 正の約数を昇順で列挙した配列
     */
    static getDivisors(n: number): number[] {
        if (n < 1) return [];
        if (n === 1) return [1];
        /** @type {number[]} */
        const smallDivisors: number[] = [];
        /** @type {number[]} */
        const largeDivisors: number[] = [];
        const limit = Math.sqrt(n);
        // 1から√nまでの整数で割り切れるかを調べ、割り切れたらiをsmallDivisors、n/iをlargeDivisorsに追加する
        for (let i = 1; i <= limit; i++) {
            if (n % i === 0) {
                smallDivisors.push(i);
                if (i !== n / i) {
                    largeDivisors.push(n / i);
                }
            }
        }
        // smallDivisorsにlargeDivisorsの逆順を追加して返す。
        largeDivisors.reverse();
        smallDivisors.push(...largeDivisors);
        return smallDivisors;
    }

    /**
     * 整数`n`の整数平方根を求めます。すなわち、`x ** 2 <= n < (x + 1) ** 2`を満たす唯一の整数`x`を返します。
     *
     * 時間計算量: nが2^104未満の場合はO(1)、それ以上の場合はO(M(log_2(n)))
     * ここで M(k) はkビット整数の乗算の時間計算量で、これは実行エンジンに依存します。一般に M(k) は O(k^(log_2(3))) もしくは O(k log k log log k) となります。
     *
     * @example
     * ```ts
     * ExtendedMath.isqrt(10n) // => 3n
     * ExtendedMath.isqrt(15n) // => 3n
     * ExtendedMath.isqrt(16n) // => 4n
     * ```
     *
     * @param n - 対象の整数 (n >= 0)
     * @returns nの整数平方根
     * @throws {RangeError} nが負の数の場合
     */
    static isqrt(n: bigint): bigint {
        // nが負の数の場合はエラー
        if (n < 0n) {
            throw new RangeError("n must be non-negative");
        }
        // f64 で扱える範囲ならば、Math.sqrt + 1段階の補正を利用する
        // n <= 2^104 では floor(sqrt) が高々 +1 しかずれないことが示されている
        if (n < 20282409603651670423947251286016n /* 2n ** 104n */) {
            let s = BigInt(Math.floor(Math.sqrt(Number(n))));
            if (s * s > n) s--;
            return s;
        }
        // 漸化式の初期値
        // 効率的なビット長の近似計算: 16進数文字列長 * 4
        const bitLength = BigInt(n.toString(16).length * 4);
        let x0 = 1n << ((bitLength + 1n) / 2n);
        let x1 = (x0 + n / x0) / 2n; // 漸化式で次のステップの値を計算

        // x1 が x0 より小さい間 = まだ収束していない間
        while (x1 < x0) {
            x0 = x1; // 値を更新
            x1 = (x0 + n / x0) / 2n; // 再度、次のステップの値を計算
        }

        // ループを抜けた時点の x0 が求める答え
        return x0;
    }

    /**
     * 整数`a`, 非負整数`n`, 正整数`m`について、`a`の`n`乗を`m`で割った余り(`(a ** n) % m`)を求めます。
     *
     * 時間計算量: O(log n)
     * (ただし、剰余、余剰演算の時間計算量はO(1)と仮定)
     *
     * @example
     * ```ts
     * ExtendedMath.modPow(3n, 200n, 50n) // => 1n
     * ```
     *
     * @param a - 底 (整数)
     * @param n - 指数 (非負整数)
     * @param m - 法 (正整数)
     * @returns aのn乗をmで割った余り
     * @throws {RangeError} nが負の数である場合、またはmが正の整数でない場合
     */
    static modPow(a: bigint, n: bigint, m: bigint): bigint {
        // エラーハンドリング
        if (n < 0n) {
            throw new RangeError("exponent (n) must be non-negative integer");
        }
        if (m <= 0n) {
            throw new RangeError("modulus (m) must be a positive integer");
        }
        // m === 1のときは常に0を返す
        if (m === 1n) return 0n;
        // 繰り返し二乗法をやる
        let result = 1n;
        let base = ((a % m) + m) % m;
        let exponent = n;
        while (exponent > 0n) {
            if (exponent % 2n === 1n) {
                result = (((result * base) % m) + m) % m;
            }
            base = (((base * base) % m) + m) % m;
            exponent = exponent / 2n;
        }
        return ((result % m) + m) % m;
    }

    /**
     * 法をmとする合同算術におけるaのモジュラ逆数(乗法の逆元)を返します。
     * すなわち、av ≡ 1 (mod m)となる0以上m未満の唯一の整数vを返します。
     * (ただし、gcd(a, m) ≠ 1のとき逆元は存在せず、このときは例外を発生させます。)
     *
     * 時間計算量: O(log m)
     *
     * @example
     * ```ts
     * console.log(ExtendedMath.modInv(3n, 7n)); // => 5n (3×5 = 15 ≡ 1 (mod 7))
     * console.log(ExtendedMath.modInv(0n, 1n)); // => 0n
     * console.log(ExtendedMath.modInv(-2n, 7n)); // => 3n
     * console.log(ExtendedMath.modInv(2n, 4n)); // => throw Error (gcd(2,4)=2(≠1))
     * ```
     *
     * @param a - 逆元を求めたい整数
     * @param m - 法 (1以上)
     * @returns 法をmとする合同算術におけるaのモジュラ逆数(乗法の逆元)。0以上m未満の整数
     * @throws {Error} - aとmが互いに素でない(つまり、逆元が存在しない)か、mが1未満である場合
     */
    static modInv(a: bigint, m: bigint): bigint {
        if (m < 1n) {
            throw new Error("The modulus `m` must be greater than or equal to 1.");
        }
        const a_mod_m = a % m;
        const a0 = a_mod_m + (a_mod_m < 0n ? m : 0n);
        const [g, x] = ExtendedMath.extendedGCD(a0, m);
        if (g !== 1n) {
            throw new Error(`Inverse does not exist for ${a} (mod ${m}) because gcd(${a0}, ${m}) = ${g} (is not 1).`);
        }
        const x_mod_m = x % m;
        const x0 = x_mod_m + (x_mod_m < 0n ? m : 0n);
        return x0;
    }

    /**
     * `n`が素数であるかを、ミラー・ラビン素数判定法により判定します。
     *
     * > [!IMPORTANT]
     * > このメソッドは確率的アルゴリズムです。
     * > - `false`が返された場合`n`は確実に合成数です。
     * > - `true`が返された場合`n`は素数である可能性がありますが、確実ではありません。
     * >     - ただし、`n < 2^64`の範囲で、かつ`bases`を省略した場合において、`true`が返されたときは`n`は確実に素数です。
     *
     * 時間計算量: O(b * log(n) * M(log_2(n)))
     * ここで、bは`bases`の長さ、M(k)はkビット整数の乗算の時間計算量です。
     * bは`bases`を省略した場合固定で7で、この場合時間計算量はO(log(n) * M(log_2(n)))となります。
     * M(k)は実行エンジンに依存しますが、一般にO(k^(log_2(3)))もしくはO(k log k log log k)となります。
     *
     * @example basesを省略した場合（n < 2^64なら決定的）
     * ```ts
     * ExtendedMath.isProbablyPrime(17n) // => true
     * ExtendedMath.isProbablyPrime(18n) // => false
     * ```
     *
     * @example basesを指定した場合（n < 2^64であっても、basesに不適切な値を入れると誤判定する可能性がある）
     * ```ts
     * ExtendedMath.isProbablyPrime(17n, [2n]) // => true
     * ExtendedMath.isProbablyPrime(25326001n, [2n, 3n, 5n]) // => true (※25326001は、bases={2,3,5}に対して通過する最小の合成数(Strong pseudoprime)として知られています)
     * ```
     *
     * @param n - 判定する整数 (2以上)
     * @param [bases] - 判定に使用する基数の配列 (省略時は2^64未満で決定的になるよう選定)
     * @returns  - 素数でなければfalse、素数かもしれなければtrue (bases省略時、n<2^64なら決定的)
     */
    static isProbablyPrime(n: bigint, bases?: bigint[]): boolean {
        // エラーハンドリング
        if (n <= 1n) return false;
        if (n === 2n) return true;
        if (n % 2n === 0n) return false;
        // 基数のリストを先に作っておく
        const BASES = bases ?? [2n, 325n, 9375n, 28178n, 450775n, 9780504n, 1795265022n];
        // n - 1 = 2^s * d の形に変形 (dが奇数になるまで2で割る)
        let d = n - 1n;
        let s = 0n;
        while ((d & 1n) === 0n) {
            d >>= 1n;
            s += 1n;
        }
        // 各基数についてテストを行う
        for (const a of BASES) {
            // 底が n と等しい場合は素数
            if (a === n) return true;
            // 底が n の倍数 (a % n === 0) の場合は skip（mod n が 0 になり x=0 となって誤判定するため）
            if (a % n === 0n) continue;
            // (効率化) n が底の倍数なら合成数 (例: n=9, a=3)
            if (n % a === 0n) return false;
            // x = a^d mod n
            let x = ExtendedMath.modPow(a, d, n);
            // x = 1 または x = n - 1 なら「素数っぽい」ので次の底へ
            if (x === 1n || x === n - 1n) continue;
            // xを2乗していき、n - 1 になるかチェック (s-1回繰り返す)
            let isProbablyPrime = false;
            for (let r = 1n; r < s; r++) {
                x = (x * x) % n;
                if (x === n - 1n) {
                    isProbablyPrime = true;
                    break;
                }
            }
            // n - 1 にならなかった場合は合成数
            if (!isProbablyPrime) {
                return false;
            }
        }
        // すべての基数で「素数っぽい」場合は素数かもしれない
        return true;
    }

    /**
     * 符号なし32bit整数`n`における立っているビットの数(popcount)を返します。
     * なお、nが整数でない場合、`0`未満の場合、`2**32`以上の場合の動作は未定義です。
     * (エラーを吐かず、多くの場合で誤った値を返します。この関数を使用する際は入力値が`0`以上`2**32`未満の整数であることを確認してください。)
     *
     * 時間計算量: O(1)
     *
     * @example
     * ```ts
     * ExtendedMath.popcount32(0b10101010) // => 4
     * ExtendedMath.popcount32(0b11111111) // => 8
     * ```
     *
     * @param n - 対象の整数 (`0`以上`2**32`未満)
     * @returns nにおける立っているビットの数
     */
    static popcount32(n: number): number {
        n = n - ((n >>> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
        return (((n + (n >>> 4)) & 0x0f0f0f0f) * 0x01010101) >>> 24;
    }

    /**
     * 1つ以上のbigintを受け取り、そのうち最大のものを返します。
     *
     * 時間計算量: O(n) (nは引数の個数)
     *
     * @example
     * ```ts
     * ExtendedMath.maxBigint(1n, 2n, 3n) // => 3n
     * ```
     *
     * @param first - 1つ目のbigint
     * @param rest - 2つ目以降のbigint
     * @returns 最大のbigint
     */
    static maxBigint(first: bigint, ...rest: bigint[]): bigint {
        let max = first;
        for (const value of rest) {
            if (value > max) {
                max = value;
            }
        }
        return max;
    }

    /**
     * 1つ以上のbigintを受け取り、そのうち最小のものを返します。
     *
     * 時間計算量: O(n) (nは引数の個数)
     *
     * @example
     * ```ts
     * ExtendedMath.minBigint(1n, 2n, 3n) // => 1n
     * ```
     * @param first - 1つ目のbigint
     * @param rest - 2つ目以降のbigint
     * @returns 最小のbigint
     */
    static minBigint(first: bigint, ...rest: bigint[]): bigint {
        let min = first;
        for (const value of rest) {
            if (value < min) {
                min = value;
            }
        }
        return min;
    }

    /**
     * bigintを受け取り、その絶対値を返します。
     *
     * 時間計算量: O(1)
     *
     * @example
     * ```ts
     * ExtendedMath.absBigint(1n) // => 1n
     * ExtendedMath.absBigint(-7n) // => 7n
     * ```
     * @param n - 対象のbigint
     * @returns nの絶対値
     */
    static absBigint(n: bigint): bigint {
        return n < 0n ? -n : n;
    }

    /**
     * bigintを受け取り、その符号を返します。
     *
     * 時間計算量: O(1)
     *
     * @example
     * ```ts
     * ExtendedMath.signBigint(1n) // => 1n
     * ExtendedMath.signBigint(-7n) // => -1n
     * ```
     * @param n - 対象のbigint
     * @returns nの符号
     */
    static signBigint(n: bigint): 0n | 1n | -1n {
        return n === 0n ? 0n : n < 0n ? -1n : 1n;
    }

    /**
     * ソート済みの数列に対して、中央値を返します。
     * 空配列に対してはNaNを返します。
     *
     * 時間計算量: O(1)
     *
     * @example
     * ```ts
     * ExtendedMath.medianOfSorted([1, 2, 3]) // => 2
     * ExtendedMath.medianOfSorted([1, 2, 3, 4]) // => 2.5
     * ExtendedMath.medianOfSorted([1, 3, 3, 6]) // => 3
     * ExtendedMath.medianOfSorted([]) // => NaN
     * ```
     *
     * @param sequence - ソート済みの数列
     * @returns 中央値
     */
    static medianOfSorted(sequence: Readonly<ArrayLike<number>>): number {
        if (sequence.length <= 0 || !Number.isSafeInteger(sequence.length)) {
            return NaN;
        }
        if (sequence.length % 2 === 1) {
            return sequence[(sequence.length - 1) / 2];
        } else {
            const a = sequence[sequence.length / 2 - 1];
            const b = sequence[sequence.length / 2];
            return (a + b) / 2;
        }
    }

    /**
     * 中国剰余定理を用いて、連立合同式を合体します。
     * k元連立合同式x≡a_i(mod n_i) (0≦i<k)を満たすxは0以上lcm(n_0, n_1, ...)未満の範囲にただ一つ存在します。
     * (ただし、"法が同じでa_iが異なる"のような自明な例外を除きます。)
     * それを踏まえて、k元連立合同式のaとmをすべて受け取り、xとlcm(n_0, n_1, ...)を返します。
     *
     * 時間計算量: O(|n| log lcm(n))
     *
     * @example
     * ```ts
     * console.log(ExtendedMath.crt([10n], [7n])); // => [3n, 7n]
     * console.log(ExtendedMath.crt([-1n, 3n], [4n, 6n])); // => [3n, 12n]
     * console.log(ExtendedMath.crt([1n, 3n], [4n, 6n])); // => [9n, 12n]
     * console.log(ExtendedMath.crt([0n, 1n], [2n, 2n])); // => [0n, 0n]
     * console.log(ExtendedMath.crt([0n], [1n])); // => [0n, 1n]
     * ```
     *
     * @param a - a[i]は、条件として与えるk元連立合同式x≡a_i(mod n_i)のa_i
     * @param n - n[i]は、条件として与えるk元連立合同式x≡a_i(mod n_i)のn_i
     * @returns [x, l]で、x+lt(tは整数)がすべての合同式を満たすとを示す。解なしの場合は[0n, 0n]。
     * @throws {Error} - aとnの長さが一致しないか、nに1未満の値が含まれている場合
     */
    static crt(a: readonly bigint[], n: readonly bigint[]): [x: bigint, l: bigint] {
        if (a.length !== n.length) {
            throw Error("The lengths of arrays `a` and `n` must match.");
        }
        if (n.some((ni) => ni < 1n)) {
            throw Error("Array `n` must not contain any values less than 1.");
        }
        let a1 = 0n;
        let n1 = 1n;
        for (let i = 0; i < a.length; i++) {
            const a2 = a[i];
            const n2 = n[i];
            const g = ExtendedMath.gcd(n1, n2);
            if ((a2 - a1) % g !== 0n) return [0n, 0n];
            const n2g = n2 / g;
            const u = ExtendedMath.modInv(n1 / g, n2g);
            const t = (u * (a2 - a1)) / g;
            const t_mod_n2g = t % n2g;
            const t0 = t_mod_n2g + (t_mod_n2g < 0n ? n2g : 0n);
            a1 = a1 + n1 * t0;
            n1 = n1 * n2g;
        }
        return [a1, n1];
    }
}

// ======== Copied from AyaExpTech Arcane (End) ========

// Please do not change the following code.
Main(require("fs").readFileSync("/dev/stdin", "utf8"));