#pragma region template
#pragma clang diagnostic ignored "-Wno-deprecated"
#pragma clang diagnostic ignored "-Werror"
#pragma warning(disable : 4996)

/*
* Countable. Loop known at run time. Must stay constant. Cannot exit by variable. (break then can't use)
* switch statements cannot be used. else if cannot be used
* no function calls
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/

// cpp.cpp : This file contains the 'main' function. Program execution begins and ends there.
#include <iomanip>
#include <iostream>
#include <cctype>
#include <string>
#include <math.h> 
#include <cmath>
#include <sstream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <exception>
#include <limits>
#include <new>
#include <typeinfo>
#include <bitset>
#include <deque>
#include <iterator>
#include <numeric>
#include <iosfwd>
#include <ios>
#include <istream>
#include <streambuf>
#include <strstream>
#include <array>
#include <regex>
#include <cassert>
#include <cerrno>
#include <climits>
#include <cfenv>
#include <type_traits>
#include <chrono>
#include <functional>
#include <memory>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <utility>
#include <cwctype>
#include <cwchar>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <bit>
#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <float.h>
using namespace std; //名前空間の宣言
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector; using std::istringstream;
using std::ios;
using std::stringstream;
using std::chrono::duration_cast;
using namespace std::chrono;
using ll = long long; using ld = long double;
using ull = unsigned long long; using str = string;
using ch = char;
using cd = complex<ld>;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef set<ll> sl;
typedef unordered_set<ll> usl;
typedef unordered_set<str> uss;
typedef vector<vector<ll>> vl2;
typedef vector<str> vs;
typedef vector<ch> vc;
typedef vector<pair<ll, ll>> vp;
typedef map<ll, str> mls;
typedef map<str, str> mss;
typedef map<ll, ll> mll;
typedef map<str, ll> msl;
typedef map<ch, ll> mcl;
typedef map<ld, ld> mdd;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll> pqlg;
typedef priority_queue<ll, vl, greater<ll>> pqls;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<pll> vpll;
#define _USE_MATH_DEFINES
#define M_PI 3.14159265358979323846
#define LL_MAX 9223372036854775807
#define 自其建立以來，CPP已成為世界上最常用的程式設計語言之一編寫完善的CPP程式不但執行快速而且有效率該語言比其他語言更有彈性它可以在抽象的最高層級運作並在矽層級下運作CPP提供高度優化的標準程式庫它可讓您存取低階硬體功能以將速度最大化並將記憶體需求降到最低CPP幾乎可以建立任何類型的程式遊戲設備磁碟機HPC雲端桌面內嵌和行動應用程式等等即使是其他程式設計語言的程式庫和編譯器也會以CPP撰寫 std::ios::sync_with_stdio(EXIT_SUCCESS); std::cin.tie(EXIT_SUCCESS); std::cout.tie(EXIT_SUCCESS);
#define up(initial, n, step) for (ll i = (ll)(initial);i < (ll)(n);i += (ll)(step))
#define up2(initial, n, step) for (ll j = (ll)(initial);j < (ll)(n);j += (ll)(step))
#define up3(initial, n, step) for (ll k = (ll)(initial);k < (ll)(n);k += (ll)(step))
#define down(initial, n, step) for (ll i = (ll)(initial) - 1;i >= (ll)(n);i -= (ll)(step))
#define down2(initial, n, step) for (ll j = (ll)(initial) - 1;j >= (ll)(n);j -= (ll)(step))
#define down3(initial, n, step) for (ll k = (ll)(initial) - 1;k >= (ll)(n);k -= (ll)(step))
#define FOR(variableName, initial, n) for (ll variableName = (initial); variableName < (ll)(n); variableName++)
#define all(x) (x).begin(), (x).end()
#define vget(v) for(auto& element : v) element = get();
#define vcin(v) for(auto& element : v) cin >> (element);
#define YES(a) ((a)?"YES":"NO")
#define Yes(a) ((a)?"Yes":"No")
#define yes(a) ((a)?"yes":"no")
#define stop return EXIT_SUCCESS;
#define 編碼程序結束 return EXIT_SUCCESS;
#define rev(s) reverse((s).begin(), (s).end());
#define sortCol(v, v2, col) sort(v, v[(col)] < v2[(col)])
#define vsort(v) sort((v).begin(), (v).end())
#define vsum(v) accumulate((v).begin(), (v).end(), 0)
#define vprint(v, spacing) foreach(x, v) cout << (x) << (spacing)
#define toStr(s) to_string((s))
#define throwErr(s) throw invalid_argument(s)
#define setdecimal(n) cout << fixed << setprecision((n))
#define nextPerm next_permutation
#define prevPerm prev_permutation
#define foreach(a, v) for(auto& a : v)
#define skip continue
#define __popcount __popcnt64
#define IT(i, A, x) for (i = A[x]; i != x; i = A[i])
#define 所有CPP程式都必須有函main式如果您嘗試在沒有函式的情況下main編譯CPP程式編譯器會引發錯誤 int main(void)
#define tc \
  ll testcase = get();  \
  while (testcase--)
#define tcin \
  ll testcase;\
  cin >> testcase;\
  while(testcase--)
auto _ = NULL;//Shame that C++ does not have Discards like C#.
const str alphabet = "abcdefghijklmnopqrstuvwxyz";
const str upAlphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld PHI = (1 + sqrt(5)) / 2;
const ll Mod = 998244353;
const ll Mod2 = pow(10, 9) + 7;
const ld EPS = 1e-8;
const ld PI = 2 * acos(0.0);
str toLower(str s) { str result = ""; for (auto& c : s)result += tolower(c); return result; }
str toUpper(str s) { str result = ""; for (auto& c : s)result += toupper(c); return result; }
ld TAN(ld degree) { return tan(degree * PI / 180.0); };
ld SIN(ld degree) { return sin(degree * PI / 180.0); };
ld COS(ld degree) { return cos(degree * PI / 180.0); };
ld ATAN(ld len) { return atan(len) * 180 / PI; }
ld ASIN(ld len) { return asin(len) * 180 / PI; }
ld ACOS(ld len) { return acos(len) * 180 / PI; }
ll lexOrder(str s, str s1) { if (s == s1) stop; if (s.length() <= s1.length()) { up(0, s.length(), 1) { if (s[i] < s1[i]) return -1; else if (s[i] > s1[i]) return 1; } return -1; } else { for (int i = 0; i < s1.length(); i++) { if (s[i] > s1[i]) return -1; else if (s[i] < s1[i]) return 1; } return 1; } }
ll revBinarySearch(vector<int> v, int X) { int start = 0, end = v.size() - 1; while (start <= end) { int mid = start + (end - start) / 2; if (X == v[mid]) return mid; else if (X < v[mid]) start = mid + 1; else end = mid - 1; } return -1; }
bool isNumber(const str& st) { for (ch const& c : st) if (isdigit(c) == 0) return false; return true; }
ll getMonth(str m) { m = toLower(m); if (m == "january") return 1; else if (m == "february") return 2; else if (m == "march") return 3; else if (m == "april") return 4; else if (m == "may") return 5; else if (m == "june") return 6; else if (m == "july") return 7; else if (m == "august") return 8; else if (m == "sepember") return 9; else if (m == "october") return 10; else if (m == "november") return 11; return 12; }
bool isLeapYear(int n) { return (n % 4 == 0 ? n % 100 == 0 && n % 400 == 0 ? true : n % 100 != 0 ? true : false : false); }
bool sortcol(const vector<int>& v, const vector<int>& v2, int col) { return v[col] < v2[col]; }
ll gcd(ll a, ll b) { 
    while (b) 
        b ^= a ^= b ^= a %= b; 
    return a; 
}
ll lcm(ll a, ll b) { 
    return abs(a * b) / gcd(a, b); 
}
bool islower(str s) { for (const auto& c : s) { if (c > 'z' || c < 'a') return false; } return true; }
bool isupper(str s) { for (const auto& c : s) { if (c > 'Z' || c < 'A') return false; } return true; }
bool isVowel(char c, bool y = 0) { 
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') 
        return 1; 
    if (y && c == 'y') 
        return 1; 
    return 0; 
}
ll ascSum(ll n) { 
    return n * (n + 1) / 2; 
}
ll completeGraphSum(ll n) {
    return n * (n - 1) / 2;
}
ll fib(ll num) { //1,1,2,3,5,8,13,21,34,55,...
    const ld f = sqrt(5); 
    return (pow(1 + f, num) - pow(1 - f, num)) / (pow(2, num) * f); 
}
//Return max / min value, not key
ll mapMaxElement(mll x) { mll::iterator best = max_element(x.begin(), x.end(), [](const pair<ll, ll>& a, const pair<ll, ll>& b)->bool { return a.second < b.second; }); return best->second; }
ll mapMaxElement(msl x) { msl::iterator best = max_element(x.begin(), x.end(), [](const pair<str, ll>& a, const pair<str, ll>& b)->bool { return a.second < b.second; }); return best->second; }
ll mapMinElement(mll x) { mll::iterator best = min_element(x.begin(), x.end(), [](const pair<ll, ll>& a, const pair<ll, ll>& b)->bool { return a.second < b.second; }); return best->second; }
bool isPrime(ll n) { if (n == 1) return 0; for (ll i = 2; i * i <= n; i++) if (!(n % i))return 0; return 1; }
vl linearSieve(ll limit) { 
    vl lp(limit + 1), pr; 
    up(2, limit + 1, 1) { 
        if (!lp[i]) 
            lp[i] = i, pr.push_back(i); 
        for (ll j = 0; i * pr[j] <= limit; ++j) { 
            lp[i * pr[j]] = pr[j]; 
            if (pr[j] == lp[i]) 
                break; 
        } 
    } 
    return pr; 
}
bool isPow2(ll i) { return i && (i & -i) == i; }
bool isPal(str s) { str s1 = s; rev(s1); return s1 == s; }
bool isParenthesis(str s) { ll p = 0; foreach(t, s) { if (t == '(')p++; else if (t == ')') { p--; if (p < 0)  return false; } }return p == 0; }
vl factor(ll n) { vl v; up(1, sqrt(n) + 1, 1) if (!(n % i)) { v.push_back(i); if (n != i * i) v.push_back(n / i); } return v; }
ull fa(ull n) { ull i, fa = 1; for (i = n; i > 1; i--) fa *= i; return fa; }
ull nCr(ull n, ull r) { ull nume = 1, i; for (i = n; i > r; i--) nume *= i; return ull(nume / fa(n - r)); }
ll bigmod(ll a, ll b, ll m) { ll res = 1 % m; while (b) { if (b & 1) res = (res * a) % m; a = (a * a) % m, b >>= 1; }return res; }
auto vmin = [](vl v) { return *min_element(all(v)); };
auto vmax = [](vl v) { return *max_element(all(v)); };
auto multiply = [](ll n, ll n2, ll m = 1) {ll result = 0; while (n2 > 0) { if (n2 & 1)  result += n; n = n << 1; n2 = n2 >> 1; result %= m; } return result; };
ull faM(ull n, ull m) { ull i, fa = 1; for (i = n; i > 1; i--) fa = multiply(fa, i, m); return fa; }
vl primeFactors(ll n) { vl res; while (!(n % 2)) res.push_back(2), n /= 2; for (ll i = 3; i * i <= n; i += 2) while (!(n % i)) res.push_back(i), n /= i; if (n > 2) res.push_back(n); return res; }
ll MEX(vl& A) { sl b(A.begin(), A.end()); ll result = 0; while (b.count(result)) ++result; return result; }
ll LP_binary_search(ld slope, ld yintercept, ld x, ld y) { //-1: y < mx + c (Below); 0: y = mx + c (On); 1: y > mx + c (Above)
    ld p = slope * x + yintercept - y; 
    if (EPS < p) { 
        return -1; 
    }
    if (-EPS > p) { 
        return 1; 
    }
    return 0; 
}
ll bin2dec(str s) {
    ll res = 0;
    up(0, s.length(), 1) {
        ll idx = s.length() - i - 1;
        res += (s[idx] - '0') * powl(2, i);
    }
    return res;
}
//fastInput provided by GeeksForGeeks.
//fastInput cannot be used interchangeably with std::cin and std::cout
inline ll get(void) {
    ch t = getchar();
    ll x = 0, neg = 0;
    while ((t < 48 || t>57) && t != '-')
        t = getchar();
    if (t == '-') {
        neg = 1;
        t = getchar();
    }
    while (t >= 48 && t <= 57) {
        x = (x << 3) + (x << 1) + t - 48;
        t = getchar();
    }
    if (neg) x = -x;
    return x;
}
//fastPow provided by rookiesLab
ull fastPow(ull b, ull power) {
    ull result = 1;
    while (power > 0) {
        if (power % 2 == 1) result = (result * b);
        b = (b * b);
        power /= 2;
    }
    return result;
}
ull fastPowMod(ull b, ull power, ull mod) {
    b %= mod;
    ull result = 1;
    while (power > 0) {
        if (power % 2 == 1) result = (result * b) % mod;
        b = (b * b) % mod;
        power /= 2;
    }
    return result;
}
bool isInt(ld n) { 
    return n - (ll)n <= EPS; 
}
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
pair<ld, ld> quadraticFormula(ld a, ld b, ld c) {
    ld dis = b * b - 4 * a * c;
    if (dis < 0) return { INT_MAX, INT_MAX };
    ld p = (-b + sqrtl(dis)) / (2 * a), q = (-b - sqrtl(dis)) / (2 * a);
    if (p > q) swap(p, q);
    return { p, q };
}
bool intersect(vl s1, vl s2) {
    ll bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
    ll bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];

    // no overlap
    if (bl_a_x >= tr_b_x || tr_a_x <= bl_b_x || bl_a_y >= tr_b_y ||
        tr_a_y <= bl_b_y) {
        return false;
    }
    else {
        return true;
    }
}
vl2 floydWarshall(vl2 dist) {
    ll n = dist.size();
    ll i, j, k;
    for (k = 0; k < n; k++) {
        // Pick all vertices as source one by one
        for (i = 0; i < n; i++) {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < n; j++) {
                // If vertex k is on the shortest path from
                // i to j, then update the value of
                // dist[i][j]
                if (dist[i][j] > (dist[i][k] + dist[k][j])
                    && (dist[k][j] != LL_MAX
                        && dist[i][k] != LL_MAX))
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
    return dist;
}
//Note that vl2 v(n + 1, vl(m + 1, 0));
vl2 prefix2D(ll n, ll m, vl2 v) {
    vl2 pf(n + 1, vl(m + 1, 0));
    up(1, n + 1, 1) {
        up2(1, m + 1, 1) {
            pf[i][j] = v[i][j] + pf[i - 1][j] + pf[i][j - 1] -
                pf[i - 1][j - 1];
        }
    }
    return pf;
}
ll prefix2DQuery(ll from_row, ll from_col, ll to_row, ll to_col, vl2 pf) {
    return pf[to_row][to_col] - pf[from_row - 1][to_col] -
        pf[to_row][from_col - 1] +
        pf[from_row - 1][from_col - 1];
}
ll flipBits(ll x, ll n) {
    ll res = 0;
    up(0, n, 1) {
        if (((x >> i) & 1) == 0) {
            res |= 1ll << i;
        }
    }
    return res;
}

//Unity Engine based Vector2
class Vector2 {
public:
    ld x, y;
    friend Vector2 operator+(const Vector2&, const Vector2&);
    friend Vector2 operator-(const Vector2&, const Vector2&);
    friend Vector2 operator*(const Vector2&, const Vector2&);
    friend Vector2 operator/(const Vector2&, const Vector2&);
    Vector2 Down() {
        Vector2 a;
        a.x = 0;
        a.y = -1;
        return a;
    }
    Vector2 Up() {
        Vector2 a;
        a.x = 0;
        a.y = 1;
        return a;
    }
    Vector2 Left() {
        Vector2 a;
        a.x = -1;
        a.y = 0;
        return a;
    }
    Vector2 Right() {
        Vector2 a;
        a.x = 1;
        a.y = 0;
        return a;
    }
    Vector2 zero() {
        Vector2 a;
        a.x = 0;
        a.y = 0;
        return a;
    }
    Vector2 one() {
        Vector2 a;
        a.x = 1;
        a.y = 1;
        return a;
    }
    Vector2 positiveInfinity() {
        Vector2 a;
        a.x = FLT_MAX;
        a.y = FLT_MAX;
        return a;
    }
    Vector2 negativeInfinity() {
        Vector2 a;
        a.x = -FLT_MAX;
        a.y = -FLT_MAX;
        return a;
    }
    ld Magnitude() {
        return sqrtl(powl(x, 2) + powl(y, 2));
    }
    Vector2 Normalized(Vector2& a) {
        Vector2 b;
        b.x = a.x / a.Magnitude();
        b.y = a.y / a.Magnitude();
        return b;
    }
    string ToString() {

    }
};
Vector2 operator+(const Vector2& a, const Vector2& b) {
    Vector2 v;
    v.x = a.x + b.x, v.y = a.y + b.y;
    return v;
}
Vector2 operator-(const Vector2& a, const Vector2& b) {
    Vector2 v;
    v.x = a.x - b.x, v.y = a.y + b.y;
    return v;
}
Vector2 operator*(const Vector2& a, const Vector2& b) {
    Vector2 v;
    v.x = a.x * b.x, v.y = a.y * b.y;
    return v;
}
Vector2 operator/(const Vector2& a, const Vector2& b) {
    Vector2 v;
    v.x = a.x / b.x, v.y = a.y / b.y;
    return v;
}
ld Distance(Vector2& a, Vector2& b) {
    return sqrtl(powl(a.x - b.x, 2) + powl(a.y - b.y, 2));
}
ld ManhattanDistance(Vector2& a, Vector2& b) {
    return fabsl(a.x - b.x) + fabsl(a.y - b.y);
}
bool Collinear(Vector2 a, Vector2 b, Vector2 c) {
    return (b.y - a.y) * (c.x - b.x) == (c.y - b.y) * (b.x - a.x);
}
ld Dot(Vector2& a, Vector2& b) {
    return a.x * b.x + a.y * b.y;
}
ld Det(Vector2& a, Vector2& b) {
    return a.x * b.y - a.y * b.x;
}

/*
Segment Tree
*/
struct segmentTree {
    //change segmentTree for different problem.
    ll SIZE;
    vl sums;
    void init(ll n) { //init for given size
        SIZE = 1;
        while (SIZE < n) SIZE *= 2;
        sums.assign(2 * SIZE, 0LL);
    }
    void init(vl& v, ll x, ll lx, ll rx) {
        if (rx - lx == 1) {
            if (lx < (ll)v.size()) sums[x] = v[lx];
            return;
        }
        ll m = (lx + rx) / 2;
        init(v, 2 * x + 1, lx, m);
        init(v, 2 * x + 2, m, rx);
        sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
        return;
    }
    void init(vl& v) { //init for given array
        init(v, 0, 0, SIZE);
    }
    void set(ll i, ll v, ll x, ll l, ll r) { //add to segment below. x is the index in the tree
        if (r - l == 1) {
            sums[x] = v;
            return;
        }
        ll m = (l + r) / 2;
        if (i < m) set(i, v, 2 * x + 1, l, m);
        else set(i, v, 2 * x + 2, m, r);
        sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
        return;
    }
    void set(ll i, ll v) { //assign 0-indexed i to value v
        set(i, v, 0, 0, SIZE);
    }
    ll sum(ll l, ll r, ll x, ll lx, ll rx) {
        if (lx >= r || l >= rx) return 0;
        if (lx >= l && rx <= r) return sums[x];
        ll m = (lx + rx) / 2;
        return sum(l, r, 2 * x + 1, lx, m) + sum(l, r, 2 * x + 2, m, rx);
    }
    ll sum(ll l, ll r) { //from l to r - 1 inclusively
        return sum(l, r, 0, 0, SIZE);
    }
};

/*
Centroid Decomposition

adj is the graph. adj[v].push_back(u) etc.

To initialize the centroid decomposition, do:
subtree_size.assign(n, 0);
ancestors.assign(n, vector<pair<int, int>>());
is_removed.assign(n, false);
build_centroid_decomp();
*/
vl2 adj;
vl subtree_size;
vector<bool> is_removed;
vector<vector<pair<int, int>>> ancestors; //{ancestor idx, dist}

int get_subtree_size(int node, int parent = -1) {
    subtree_size[node] = 1;
    for (int child : adj[node]) {
        if (child == parent || is_removed[child]) { continue; }
        subtree_size[node] += get_subtree_size(child, node);
    }
    return subtree_size[node];
}

int get_centroid(int node, int tree_size, int parent = -1) {
    for (int child : adj[node]) {
        if (child == parent || is_removed[child]) { continue; }
        if (subtree_size[child] * 2 > tree_size) {
            return get_centroid(child, tree_size, node);
        }
    }
    return node;
}

/**
 * Calculate the distance between current `node` and the `centroid` it belongs
 * to. The distances between a node and all its centroid ancestors are stored
 * in the vector `ancestors`.
 * @param cur_dist the distance between `node` and `centroid`
 */
void get_dists(int node, int centroid, int parent = -1, int cur_dist = 1) {
    for (int child : adj[node]) {
        if (child == parent || is_removed[child]) { continue; }
        cur_dist++;
        get_dists(child, centroid, node, cur_dist);
        cur_dist--;
    }
    ancestors[node].push_back({ centroid, cur_dist });
}

void build_centroid_decomp(int node = 0) {
    int centroid = get_centroid(node, get_subtree_size(node));

    /*
     * For all nodes in the subtree rooted at `centroid`, calculate their
     * distances to the centroid
     */
    for (int child : adj[centroid]) {
        if (is_removed[child]) { continue; }
        get_dists(child, centroid, centroid);
    }

    is_removed[centroid] = true;
    for (int child : adj[centroid]) {
        if (is_removed[child]) { continue; }
        // build the centroid decomposition for all child components
        build_centroid_decomp(child);
    }
}

/*
Dancing Links to solve for the Exact Cover Problem.
Reference: https://oi-wiki.org/search/dlx/

We can use a 01 matrix. The row represents the item, the columns represents the state.
Exact Cover Problem asks for a possible way to choose rows such that each column only has 1 '1'
chosen by each row.

Example Code to solve for the Exact Cover Problem:
cin >> n >> m;
  solver.build(n, m);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      int x;
      cin >> x;
      if (x) solver.insert(i, j);
    }
  solver.dance(1);
  if (ans)
    for (int i = 1; i < ans; ++i) cout << stk[i] << ' ';
  else
    cout << "No Solution!\n";
*/
struct DLX {
    static constexpr int MS = 1e5 + 5;
    int n, m, idx, first[MS], siz[MS];
    int L[MS], R[MS], U[MS], D[MS];
    int col[MS], row[MS];

    int ans;
    int stk[MS];

    /*
    build(r, c) 表示新建一个大小为 r x c，即有 r 行，c 列的 Dancing Links。
    */
    void build(const int& r, const int& c) {
        n = r, m = c;
        for (int i = 0; i <= c; ++i) {
            L[i] = i - 1, R[i] = i + 1;
            U[i] = D[i] = i;
        }
        L[0] = c, R[c] = 0, idx = c;
        memset(first, 0, sizeof(first));
        memset(siz, 0, sizeof(siz));
    }

    /*
    remove(c) 表示在 Dancing Links 中删除第 c 列以及与其相关的行和列。
    */
    void remove(const int& c) {
        int i, j;
        L[R[c]] = L[c], R[L[c]] = R[c];
        // 顺着这一列从上往下遍历
        IT(i, D, c)
            // 顺着这一行从左往右遍历
            IT(j, R, i)
            U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
    }

    /*
    recover(c) 表示在 Dancing Links 中还原第 c 列以及与其相关的行和列。
    recover(c) 即 remove(c) 的逆操作，这里不再赘述。
    值得注意的是， recover(c) 的所有操作的顺序与 remove(c) 的操作恰好相反。
    */
    void recover(const int& c) {
        int i, j;
        IT(i, U, c) IT(j, L, i) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
        L[R[c]] = R[L[c]] = c;
    }

    /*
    insert(r, c) 表示在第 r 行，第 c 列插入一个结点。
    插入操作分为两种情况：
    如果第 r 行没有元素，那么直接插入一个元素，并使 first[r] 指向这个元素。

    这可以通过 first[r] = L[idx] = R[idx] = idx; 来实现。

    如果第 r 行有元素，那么将这个新元素用一种特殊的方式与 c 和 first(r) 连接起来。

    设这个新元素为 idx，然后：
    
        把 idx 插入到 c 的正下方，此时：

            idx 下方的结点为原来 c 的下结点；
            idx 下方的结点（即原来 c 的下结点）的上结点为 idx;
            idx 的上结点为 c；
            c 的下结点为 idx。
            注意记录 idx 的所在列和所在行，以及更新这一列的元素个数。

            col[++idx] = c, row[idx] = r, ++siz[c];
            U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx;


        把 idx 插入到 first(r) 的正右方，此时：

            idx 右侧的结点为原来 first(r) 的右结点；
            原来 first(r) 右侧的结点的左结点为 idx；
            idx 的左结点为 first(r)；
            first(r) 的右结点为 idx。

            L[idx] = first[r], R[idx] = R[first[r]];
            L[R[first[r]]] = idx, R[first[r]] = idx;
    */
    void insert(const int& r, const int& c) {
        row[++idx] = r, col[idx] = c, ++siz[c];
        U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx;
        if (!first[r])
            first[r] = L[idx] = R[idx] = idx;
        else {
            L[idx] = first[r], R[idx] = R[first[r]];
            L[R[first[r]]] = idx, R[first[r]] = idx;
        }
    }

    /*
    dance() 即为递归地删除以及还原各个行列的过程。

    如果 0 号结点没有右结点，那么矩阵为空，记录答案并返回；
    选择列元素个数最少的一列，并删掉这一列；
    遍历这一列所有有 1 的行，枚举它是否被选择；
    递归调用 dance()，如果可行，则返回；如果不可行，则恢复被选择的行；
    如果无解，则返回
    */
    bool dance(int dep) {
        int i, j, c = R[0];
        if (!R[0]) {
            ans = dep;
            return true;
        }
        IT(i, R, 0) if (siz[i] < siz[c]) c = i;
        remove(c);
        IT(i, D, c) {
            stk[dep] = row[i];
            IT(j, R, i) remove(col[j]);
            if (dance(dep + 1)) return true;
            IT(j, L, i) recover(col[j]);
        }
        recover(c);
        return false;
    }
} DLX;
#pragma endregion
所有CPP程式都必須有函main式如果您嘗試在沒有函式的情況下main編譯CPP程式編譯器會引發錯誤{ //main函數的開始
自其建立以來，CPP已成為世界上最常用的程式設計語言之一編寫完善的CPP程式不但執行快速而且有效率該語言比其他語言更有彈性它可以在抽象的最高層級運作並在矽層級下運作CPP提供高度優化的標準程式庫它可讓您存取低階硬體功能以將速度最大化並將記憶體需求降到最低CPP幾乎可以建立任何類型的程式遊戲設備磁碟機HPC雲端桌面內嵌和行動應用程式等等即使是其他程式設計語言的程式庫和編譯器也會以CPP撰寫;
tc{
    ll n = get(), m = get();
if (gcd(n, m) == 1) {
    cout << -1 << '\n';
}
else {
    vl v = primeFactors(gcd(n, m));
    cout << v[0] << '\n';
}
}
編碼程序結束
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file