#1188199 (JavaScript) No.3721 Absurd Basic Constructive

• 問題: No.3721 Absurd Basic Constructive
• ユーザー: occhan
• 提出日時: 2026-09-19 13:37:32
• 言語: JavaScript (node v26.7.0 + ACL)
• 結果: AC
• 実行時間: 140 ms / 2,000 ms
• コード長: 23,781 bytes
• コンパイル時間: 56 ms
• コンパイル使用メモリ: 6,528 KB
• 実行使用メモリ: 126,336 KB
• 最終ジャッジ日時: 2026-09-19 13:37:46
• 合計ジャッジ時間: 9,934 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 47

ソースコード

"use strict";
// start
var __createBinding = (this && this.__createBinding) || (Object.create ? (function(o, m, k, k2) {
    if (k2 === undefined) k2 = k;
    var desc = Object.getOwnPropertyDescriptor(m, k);
    if (!desc || ("get" in desc ? !m.__esModule : desc.writable || desc.configurable)) {
      desc = { enumerable: true, get: function() { return m[k]; } };
    }
    Object.defineProperty(o, k2, desc);
}) : (function(o, m, k, k2) {
    if (k2 === undefined) k2 = k;
    o[k2] = m[k];
}));
var __setModuleDefault = (this && this.__setModuleDefault) || (Object.create ? (function(o, v) {
    Object.defineProperty(o, "default", { enumerable: true, value: v });
}) : function(o, v) {
    o["default"] = v;
});
var __importStar = (this && this.__importStar) || (function () {
    var ownKeys = function(o) {
        ownKeys = Object.getOwnPropertyNames || function (o) {
            var ar = [];
            for (var k in o) if (Object.prototype.hasOwnProperty.call(o, k)) ar[ar.length] = k;
            return ar;
        };
        return ownKeys(o);
    };
    return function (mod) {
        if (mod && mod.__esModule) return mod;
        var result = {};
        if (mod != null) for (var k = ownKeys(mod), i = 0; i < k.length; i++) if (k[i] !== "default") __createBinding(result, mod, k[i]);
        __setModuleDefault(result, mod);
        return result;
    };
})();
Object.defineProperty(exports, "__esModule", { value: true });
const fs = __importStar(require("node:fs"));
function main() {
    // ここに処理を記述します
    let [N, K] = nextNums(2);
    if (K == 0) {
        print(-1);
        return;
    }
    let ans = [];
    let cnt = N * N;
    for (let i = 1; i <= N; i++) {
        ans.push([]);
        if ((cnt - K) >= N - 1) {
            ans[i - 1].push(i * N);
            for (let j = 1; j < N; j++) {
                ans[i - 1].push(i * N - j);
            }
            cnt -= N - 1;
        }
        else {
            if (cnt == K) {
                for (let j = 1; j <= N; j++) {
                    ans[i - 1].push((i - 1) * N + j);
                }
            }
            else {
                for (let j = cnt - K + 1; j <= N; j++) {
                    ans[i - 1].push((i - 1) * N + j);
                }
                for (let j = 1; j < cnt - K + 1; j++) {
                    ans[i - 1].push((i - 1) * N + j);
                }
                cnt = K;
            }
        }
    }
    if (cnt > K) {
        let k = 0;
        for (let i = cnt - K + 1; i <= N; i++) {
            ans[k++][0] = i * N;
        }
        for (let i = 1; i < cnt - K + 1; i++) {
            ans[k++][0] = i * N;
        }
    }
    for (let i = 0; i < N; i++) {
        if (i < N - 1)
            println(ans[i], " ");
        else
            print(ans[i], " ");
    }
    // 処理終了
}
const less = (a, b) => (a == b ? 0 : a < b ? -1 : 1);
const greater = (a, b) => (a == b ? 0 : a < b ? 1 : -1);
const bigIntMax = (...args) => args.reduce((m, e) => (e > m ? e : m));
const bigIntMin = (...args) => args.reduce((m, e) => (e < m ? e : m));
const bigIntAbs = (arg) => (arg < 0 ? -arg : arg);
/**
 * 説明: 非負 bigint n の床平方根 floor(sqrt(n)) を正確に返す。
 * 使い方: let x = bigIntSqrt(n)
 * 計算量: O(log bit長)
 */
const bigIntSqrt = (n) => {
    if (n < 0n) {
        throw new RangeError("square root of negative bigint");
    }
    if (n < 2n)
        return n;
    let bitLength = n.toString(2).length;
    let x = 1n << BigInt((bitLength + 1) >> 1);
    while (true) {
        let next = (x + n / x) >> 1n;
        if (next >= x)
            return x;
        x = next;
    }
};
let inputs = "";
let inputArray;
let currentIndex = 0;
let outputBuffer = "";
let yes = "Yes";
let no = "No";
let MOD998244353 = 998244353;
let small_a_code = 97;
let big_A_code = 65;
let dxy4 = [[-1, 0], [0, 1], [1, 0], [0, -1]];
let dxy8 = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]];
let dir4 = ["U", "R", "D", "L"];
// // インタラクティブ用
// // お決まりのインプットはコメントアウト、main関数にasyncを忘れない
// // 詳しくは典型ABC305-Fをチェック
// const readline = require("readline");
// const rl = readline.createInterface({
//   input: process.stdin,
//   output: process.stdout,
// });
// const it = rl[Symbol.asyncIterator]();
// const nextAwait = async () => {
//   const { value } = await it.next();
//   return value.trim();
// };
function next() {
    return inputArray[currentIndex++];
}
function nextNum() {
    return +next();
}
function nextBigInt() {
    return BigInt(next());
}
function nexts(length) {
    const arr = [];
    for (let i = 0; i < length; ++i)
        arr[i] = next();
    return arr;
}
function nextNums(length) {
    const arr = [];
    for (let i = 0; i < length; ++i)
        arr[i] = nextNum();
    return arr;
}
function nextBigInts(length) {
    const arr = [];
    for (let i = 0; i < length; ++i)
        arr[i] = nextBigInt();
    return arr;
}
function print(out, separator) {
    if (Array.isArray(out)) {
        outputBuffer += out.join(separator);
    }
    else {
        outputBuffer += out;
    }
}
function println(out, separator) {
    if (Array.isArray(out)) {
        print(out, separator || "");
    }
    else {
        print(out);
    }
    print("\n");
}
function flush() {
    if (outputBuffer.length == 0)
        return;
    console.log(outputBuffer.endsWith("\n")
        ? outputBuffer.slice(0, -1)
        : outputBuffer);
}
function intDiv(a, b) {
    return Math.trunc(a / b);
}
function lowerBound(list, value, less = (l, r) => l < r) {
    let count = list.length;
    let first = 0;
    while (0 < count) {
        const count2 = count / 2 | 0;
        const mid = first + count2;
        if (less(list[mid], value)) {
            first = mid + 1;
            count -= count2 + 1;
        }
        else {
            count = count2;
        }
    }
    return first;
}
function upperBound(list, value, less = (l, r) => l < r) {
    return lowerBound(list, value, (l, r) => !less(r, l));
}
function nextPermutation(arr) {
    const len = arr.length;
    let left = len - 2;
    while (left >= 0 && arr[left] >= arr[left + 1]) {
        left--;
    }
    if (left < 0) {
        return false;
    }
    let right = len - 1;
    while (arr[left] >= arr[right]) {
        right--;
    }
    const t = arr[left];
    arr[left] = arr[right];
    arr[right] = t;
    left++;
    right = len - 1;
    while (left < right) {
        const t = arr[left];
        arr[left] = arr[right];
        arr[right] = t;
        left++;
        right--;
    }
    return true;
}
function gcd(a, b) {
    if (b == 0 || b == BigInt(0)) {
        return a;
    }
    if (typeof a === 'number' && typeof b === 'number') {
        const r = a % b;
        return gcd(b, r);
    }
    else if (typeof a === 'bigint' && typeof b === 'bigint') {
        const r = a % b;
        return gcd(b, r);
    }
    return 0;
}
function lcm(a, b) {
    if (a == 0n || b == 0n)
        return 0n;
    return a / gcd(a, b) * b;
}
/**
 * ax+by=gcd(|a|,|b|)
 * を満たす [g,x,y] を返す
 */
function extGcdBigInt(a, b) {
    let signA = a < 0n ? -1n : 1n;
    let signB = b < 0n ? -1n : 1n;
    a = bigIntAbs(a);
    b = bigIntAbs(b);
    let oldR = a;
    let r = b;
    let oldX = 1n;
    let x = 0n;
    let oldY = 0n;
    let y = 1n;
    while (r != 0n) {
        let q = oldR / r;
        [oldR, r] = [
            r,
            oldR - q * r
        ];
        [oldX, x] = [
            x,
            oldX - q * x
        ];
        [oldY, y] = [
            y,
            oldY - q * y
        ];
    }
    return [
        oldR,
        oldX * signA,
        oldY * signB
    ];
}
function eratosthenesPrime(N = 10 ** 6) {
    if (N < 2)
        return [];
    let b = Array(N + 1).fill(true);
    b[0] = false;
    b[1] = false;
    let prime = [2];
    for (let i = 4; i <= N; i += 2) {
        b[i] = false;
    }
    for (let i = 3; i <= N; i += 2) {
        if (b[i]) {
            prime.push(i);
            for (let j = i * i; j <= N; j += i * 2) {
                b[j] = false;
            }
        }
    }
    return prime;
}
// ソートなし約数列挙
function enumDiv(n) {
    const res = [];
    for (let i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push(i);
            if (i * i != n)
                res.push(intDiv(n, i));
        }
    }
    return res;
}
function useModint(M) {
    /*
     * 0 <= a,b < M, M < 2^30 のとき高速な mod 乗算。
     *
     * a*b 自体は MAX_SAFE_INTEGER を超えることがあるが、
     * q=floor(a*b/M) は誤差が高々ごく小さいため
     * 真の商との差は高々1。
     *
     * Math.imul で積の下位32bitを正確に求め、
     * 最後の差が (-M,2M) に収まることを利用して
     * 正確な余りを復元する。
     */
    let mulMod;
    if (M < (1 << 30)) {
        mulMod = (a, b) => {
            let q = Math.floor(a * b / M);
            let r = (Math.imul(a, b) - Math.imul(q, M)) | 0;
            if (r < 0)
                r += M;
            else if (r >= M)
                r -= M;
            return r;
        };
    }
    else {
        // 従来版
        mulMod = (a, b) => {
            let t = a * b;
            if (t <= Number.MAX_SAFE_INTEGER)
                return t % M;
            return ((((a >> 16) * b) % M) * 65536 + (a & 65535) * b) % M;
        };
    }
    /*
     * add/sub は通常、
     * 両方とも既に [0,M) に正規化されているため
     * % を使わず1回の補正で済む。
     *
     * 範囲外の値が渡された場合だけ % にフォールバックする。
     */
    Number.prototype.add = function (a) {
        let t = +this + a;
        if (0 <= t && t < M)
            return t;
        if (M <= t && t < 2 * M)
            return t - M;
        if (-M <= t && t < 0)
            return t + M;
        t %= M;
        return t < 0 ? t + M : t;
    };
    Number.prototype.sub = function (a) {
        let t = +this - a;
        if (0 <= t && t < M)
            return t;
        if (M <= t && t < 2 * M)
            return t - M;
        if (-M <= t && t < 0)
            return t + M;
        t %= M;
        return t < 0 ? t + M : t;
    };
    Number.prototype.mul = function (a) {
        return mulMod(+this, a);
    };
    /*
     * pow 内では x.mul(x) とせず、
     * mulMod を直接呼ぶ。
     *
     * public API は a.pow(n) のままだが、
     * 内部では Number.prototype 経由の呼び出しを避ける。
     */
    Number.prototype.pow = function (n) {
        let x = +this;
        x %= M;
        if (x < 0)
            x += M;
        let r = 1;
        if (typeof n == "number") {
            if (!Number.isSafeInteger(n) || n < 0) {
                throw new RangeError("exponent must be a non-negative safe integer");
            }
            while (n > 0) {
                if (n % 2 == 1)
                    r = mulMod(r, x);
                x = mulMod(x, x);
                n = Math.floor(n / 2);
            }
        }
        else {
            if (n < 0n) {
                throw new RangeError("exponent must be non-negative");
            }
            while (n > 0n) {
                if (n & 1n)
                    r = mulMod(r, x);
                x = mulMod(x, x);
                n >>= 1n;
            }
        }
        return r;
    };
    Number.prototype.div = function (a) {
        let x = a % M;
        if (x < 0)
            x += M;
        let n = M - 2;
        let r = 1;
        while (n > 0) {
            if (n % 2 == 1)
                r = mulMod(r, x);
            x = mulMod(x, x);
            n = Math.floor(n / 2);
        }
        return mulMod(+this, r);
    };
}
/**
 * 説明:
 *   Number.MAX_SAFE_INTEGER を超える可能性がある積を
 *   正確に MOD で割った余りにする。
 *   0 <= a < 2^31 を前提とする。
 *
 * 使い方:
 *   let x = modMul(a,b,MOD);
 *
 * 計算量:
 *   O(1)
 */
function modMul(a, b, MOD) {
    let t = a * b;
    if (t <= Number.MAX_SAFE_INTEGER) {
        return t % MOD;
    }
    return ((((a >> 16) * b) % MOD) * 65536 + (a & 65535) * b) % MOD;
}
function bigint_mod_pow(x, n, p) {
    if (n < 0n) {
        throw new RangeError("exponent must be non-negative");
    }
    if (p <= 0n) {
        throw new RangeError("modulus must be positive");
    }
    x %= p;
    if (x < 0n)
        x += p;
    let r = 1n % p;
    for (; n; x = x * x % p, n >>= 1n) {
        if (n & 1n)
            r = r * x % p;
    }
    return r;
}
const U64_BASE = 4294967296;
const U64_MASK_BIGINT = 0xffffffffn;
const U64_LIMIT_BIGINT = 1n << 64n;
/**
 * bigint -> U64
 * 計算量 O(1)
 */
function u64FromBigInt(x) {
    if (x < 0n || x >= U64_LIMIT_BIGINT) {
        throw new RangeError("u64FromBigInt: out of uint64 range");
    }
    return [
        Number(x >> 32n),
        Number(x & U64_MASK_BIGINT)
    ];
}
/**
 * safe integer number -> U64
 * 計算量 O(1)
 */
function u64FromNumber(x) {
    if (!Number.isSafeInteger(x) || x < 0) {
        throw new RangeError("u64FromNumber: x must be a non-negative safe integer");
    }
    return [
        Math.floor(x / U64_BASE) >>> 0,
        x >>> 0
    ];
}
/**
 * U64 -> bigint
 *
 * 出力時など、低頻度で使うことを想定。
 * 計算量 O(1)
 *
 * 用例: ABC391-F
 */
function u64ToBigInt(hi, lo) {
    return ((BigInt(hi >>> 0) << 32n)
        + BigInt(lo >>> 0));
}
/**
 * U64 -> number
 *
 * Number.MAX_SAFE_INTEGER 以下でなければ例外。
 * 計算量 O(1)
 */
function u64ToNumber(hi, lo) {
    let x = (hi >>> 0) * U64_BASE + (lo >>> 0);
    if (!Number.isSafeInteger(x)) {
        throw new RangeError("u64ToNumber: value exceeds safe integer range");
    }
    return x;
}
/**
 * unsigned 64bit 比較
 *
 * 戻り値:
 *   a < b : -1
 *   a = b :  0
 *   a > b :  1
 *
 * 計算量 O(1)
 *
 * 用例: ABC391-F
 */
function u64Cmp(ah, al, bh, bl) {
    ah >>>= 0;
    al >>>= 0;
    bh >>>= 0;
    bl >>>= 0;
    if (ah != bh)
        return ah < bh ? -1 : 1;
    if (al != bl)
        return al < bl ? -1 : 1;
    return 0;
}
/**
 * unsigned 64bit 等値判定
 */
function u64Eq(ah, al, bh, bl) {
    return ((ah >>> 0) == (bh >>> 0)
        &&
            (al >>> 0) == (bl >>> 0));
}
/**
 * unsigned 64bit 加算
 *
 * 2^64 を超えた分は捨てる。
 * 計算量 O(1)
 */
function u64Add(ah, al, bh, bl) {
    ah >>>= 0;
    al >>>= 0;
    bh >>>= 0;
    bl >>>= 0;
    let sumLo = al + bl;
    let lo = sumLo >>> 0;
    let hi = (ah
        + bh
        + (sumLo >= U64_BASE ? 1 : 0)) >>> 0;
    return [hi, lo];
}
/**
 * unsigned 64bit 減算
 *
 * a >= b を想定。
 * a < b の場合は 2^64 を法としてwrapする。
 * 計算量 O(1)
 */
function u64Sub(ah, al, bh, bl) {
    ah >>>= 0;
    al >>>= 0;
    bh >>>= 0;
    bl >>>= 0;
    let borrow = al < bl ? 1 : 0;
    let lo = (al - bl) >>> 0;
    let hi = (ah - bh - borrow) >>> 0;
    return [hi, lo];
}
/**
 * unsigned 64bit XOR
 * 計算量 O(1)
 */
function u64Xor(ah, al, bh, bl) {
    return [
        (ah ^ bh) >>> 0,
        (al ^ bl) >>> 0
    ];
}
/**
 * uint32 * uint32 を正確な uint64 にする。
 *
 * a,b は 0 <= a,b < 2^32。
 *
 * JavaScript number で a*b を直接計算すると
 * 2^53 を超えて整数精度を失う可能性があるため、
 * 16bit ずつに分割して計算する。
 *
 * 計算量 O(1)
 *
 * 用例: ABC391-F
 */
function u64MulU32(a, b) {
    a >>>= 0;
    b >>>= 0;
    let a0 = a & 0xffff;
    let a1 = a >>> 16;
    let b0 = b & 0xffff;
    let b1 = b >>> 16;
    let mid = a1 * b0 + a0 * b1;
    let t = a0 * b0
        + (mid & 0xffff) * 65536;
    let lo = t >>> 0;
    let hi = (a1 * b1
        + Math.floor(mid / 65536)
        + Math.floor(t / U64_BASE)) >>> 0;
    return [hi, lo];
}
/**
 * U64 + uint32*uint32
 *
 * 積を別途BigIntにせず加算する。
 * 計算量 O(1)
 */
function u64AddMulU32(hi, lo, a, b) {
    a >>>= 0;
    b >>>= 0;
    let a0 = a & 0xffff;
    let a1 = a >>> 16;
    let b0 = b & 0xffff;
    let b1 = b >>> 16;
    let mid = a1 * b0 + a0 * b1;
    let t = a0 * b0
        + (mid & 0xffff) * 65536;
    let mlo = t >>> 0;
    let mhi = (a1 * b1
        + Math.floor(mid / 65536)
        + Math.floor(t / U64_BASE)) >>> 0;
    let sumLo = (lo >>> 0) + mlo;
    return [
        ((hi >>> 0)
            + mhi
            + (sumLo >= U64_BASE ? 1 : 0)) >>> 0,
        sumLo >>> 0
    ];
}
// ========================================
// U64 Hash Set
// ========================================
// 説明:
//   Set<bigint> が重い場合に使う。
//   open addressing + linear probing。
//
//   hi,lo を Uint32Array に保存し、
//   used を Uint8Array で管理する。
//
// 使い方:
//   let set = new U64HashSet(4_300_000);
//   set.add(hi,lo);
//   set.has(hi,lo);
//   set.size;
//
// 計算量:
//   平均 add/has O(1)
//
// 注意:
//   expectedSize を大きく超えて追加しないこと。
class U64HashSet {
    cap;
    mask;
    hi;
    lo;
    used;
    _size = 0;
    constructor(expectedSize = 16) {
        let cap = 1;
        // load factor をおよそ 0.7 以下にする
        while (cap * 0.7 < expectedSize) {
            cap *= 2;
        }
        this.cap = cap;
        this.mask = cap - 1;
        this.hi = new Uint32Array(cap);
        this.lo = new Uint32Array(cap);
        this.used = new Uint8Array(cap);
    }
    get size() {
        return this._size;
    }
    hash(h, l) {
        h >>>= 0;
        l >>>= 0;
        let x = (Math.imul((l ^ (l >>> 16)) >>> 0, 0x85ebca6b)
            ^
                Math.imul((h ^ (h >>> 16)) >>> 0, 0xc2b2ae35)) >>> 0;
        x ^= x >>> 16;
        return x >>> 0;
    }
    has(h, l) {
        h >>>= 0;
        l >>>= 0;
        let p = this.hash(h, l) & this.mask;
        while (this.used[p]) {
            if (this.hi[p] == h
                &&
                    this.lo[p] == l) {
                return true;
            }
            p = (p + 1) & this.mask;
        }
        return false;
    }
    /**
     * 新しく追加されたならtrue、
     * すでに存在していたならfalse。
     */
    add(h, l) {
        h >>>= 0;
        l >>>= 0;
        let p = this.hash(h, l) & this.mask;
        while (this.used[p]) {
            if (this.hi[p] == h
                &&
                    this.lo[p] == l) {
                return false;
            }
            p = (p + 1) & this.mask;
        }
        this.used[p] = 1;
        this.hi[p] = h;
        this.lo[p] = l;
        this._size++;
        return true;
    }
}
// ========================================
// Large Exact Sum
// ========================================
// 説明:
//   1回ごとの加算値は safe integer だが、
//   累積結果だけ Number.MAX_SAFE_INTEGER を超える場合に使う。
//
//   例:
//     ABC384-G の答え累積など。
//
//   内部表現:
//     value = hi * 1e9 + lo
//
//   add() 内ではBigIntを使わず、
//   最後に toBigInt() したときだけBigIntを使う。
//
// 注意:
//   hi 自体が safe integer を超えない範囲を想定。
//   通常のAtCoder 1e18〜1e21程度なら十分。
class LargeIntSum {
    static BASE = 1e9;
    hi = 0;
    lo = 0;
    constructor(initial = 0) {
        this.add(initial);
    }
    /**
     * safe integer を加算する。
     * 負数も可。
     */
    add(x) {
        if (!Number.isSafeInteger(x)) {
            throw new RangeError("LargeIntSum.add: x must be a safe integer");
        }
        this.lo += x;
        let q = Math.trunc(this.lo / LargeIntSum.BASE);
        this.hi += q;
        this.lo -= q * LargeIntSum.BASE;
    }
    sub(x) {
        this.add(-x);
    }
    /**
     * 最後の出力時などに使用。
     */
    toBigInt() {
        return (BigInt(this.hi)
            * 1000000000n
            + BigInt(this.lo));
    }
    /**
     * safe integer 範囲なら number を返す。
     */
    toNumber() {
        let x = this.hi * LargeIntSum.BASE
            + this.lo;
        if (!Number.isSafeInteger(x)) {
            throw new RangeError("LargeIntSum.toNumber: value exceeds safe integer range");
        }
        return x;
    }
}
/**
 * 説明: 階乗と逆階乗を前計算し、nCr/nPr/nHr を高速に計算する。useModint(MOD) 後に使う。
 * 使い方: let comb = new CombMod(MAX); comb.nCr(n,r)
 * 計算量: 前計算 O(MAX)、各クエリ O(1)
 */
class CombMod {
    fac;
    finv;
    /**
     * @param max_n 求める最大の N を指定
     */
    /**
     * 説明: 階乗・逆階乗を max_n まで前計算する
     * 使い方: new CombMod(max_n)
     * 計算量: O(max_n)
     */
    constructor(max_n) {
        // max_n が 0 や 1 の場合でもエラーにならないよう、最低サイズ2を確保
        let size = Math.max(2, max_n + 1);
        this.fac = new Float64Array(size);
        this.finv = new Float64Array(size);
        this.fac[0] = 1;
        this.fac[1] = 1;
        this.finv[0] = 1;
        this.finv[1] = 1;
        // 階乗の計算
        for (let i = 2; i <= max_n; i++) {
            this.fac[i] = this.fac[i - 1].mul(i);
        }
        // 逆元の計算 (一番大きいところだけ .div() を使い、あとは掛け算で降下する最速手法)
        if (max_n >= 2) {
            this.finv[max_n] = (1).div(this.fac[max_n]);
            for (let i = max_n - 1; i >= 2; i--) {
                this.finv[i] = this.finv[i + 1].mul(i + 1);
            }
        }
    }
    /**
     * 説明: 組み合わせ nCr を返す
     * 使い方: comb.nCr(n,r)
     * 計算量: O(1)
     */
    nCr(n, r) {
        if (n < r || n < 0 || r < 0)
            return 0;
        return this.fac[n].mul(this.finv[r]).mul(this.finv[n - r]);
    }
    /**
     * 説明: 順列 nPr を返す
     * 使い方: comb.nPr(n,r)
     * 計算量: O(1)
     */
    nPr(n, r) {
        if (n < r || n < 0 || r < 0)
            return 0;
        return this.fac[n].mul(this.finv[n - r]);
    }
    /**
     * 説明: 重複組合せ nHr を返す
     * 使い方: comb.nHr(n,r)
     * 計算量: O(1)
     */
    nHr(n, r) {
        if (n < 0 || r < 0)
            return 0;
        if (n == 0 && r == 0)
            return 1;
        return this.nCr(n + r - 1, r);
    }
}
/**
 * 説明: 最長増加部分列の長さを返す。狭義増加
 * 使い方: let len = LIS(A)
 * 計算量: O(N log N)
 */
function LIS(arr) {
    let dp = [];
    for (let num of arr) {
        let lb = lowerBound(dp, num);
        if (lb == dp.length) {
            dp.push(num);
        }
        else {
            dp[lb] = num;
        }
    }
    return dp.length;
}
// end
function readInput() {
    const g = globalThis;
    // Deno
    if (typeof g.Deno !== "undefined") {
        const chunks = [];
        const buf = new Uint8Array(1 << 16);
        while (true) {
            const n = g.Deno.stdin.readSync(buf);
            if (n === null)
                break;
            if (n > 0)
                chunks.push(buf.slice(0, n));
        }
        const length = chunks.reduce((s, c) => s + c.length, 0);
        const bytes = new Uint8Array(length);
        let offset = 0;
        for (const c of chunks) {
            bytes.set(c, offset);
            offset += c.length;
        }
        return new TextDecoder().decode(bytes);
    }
    // Node.js / Bun
    return fs.readFileSync(0, "utf8");
}
inputs = readInput();
inputArray = inputs.trim().split(/\s+/);
main();
flush();
/**
 * https://github.com/occhanCode/atcoder-templates/blob/main/src/main.ts
 */ 
//# sourceMappingURL=main.js.map