$$$101$$$

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin>>t;

    while(t--){
        int a, b, c;
        cin>>a>>b>>c;
        
        cout<<101<<"\n";
    }
}

Decompose $$$k$$$ into its prime factors, i.e. $$$k=p_1^{x_1}\cdot p_2^{x_2}\ldots p_r^{x_r}$$$. A subarray $$$a_l, a_{l+1},\ldots,a_r$$$ has $$$LCM$$$ equal to $$$k$$$ if and only if for each $$$i\in[1\ldots r]$$$, there exists $$$a_j, l\leq j\leq r$$$ such that $$$p_i^{x_i}$$$ divides $$$a_j$$$, and for no $$$j$$$ does $$$p_i^{x_i+1}$$$ divide $$$a_j$$$.

The answer is YES if any only if for the prime decomposition of $$$k=p_1^{x_1}\cdot p_2^{x_2}\ldots p_r^{x_r}$$$, we have $$$p_i^{x_i}\leq n$$$ for all $$$i\in [1\ldots r]$$$, otherwise it is NO. In case of YES, you can output the permutation where first $$$r$$$ elements are $$$p_i^{x_i}$$$ and the remaining elements are the remaining elements of the permutation of $$$n$$$ in any order.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<vector<ll>> vvint;
typedef vector<ll> vint;
#define endl '\n'
#define int ll
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll inf = 2e18;
const int M = 1e9 + 7, M2 = 998244353, N = 1e7 + 10, N2 = 2e5 + 10;

void solve() {
    int n, k;
    cin >> n >> k;
    map <int, int> mp;
    for (int i = 2; i * i <= k; i++) {
        while (k % i == 0) {
            mp[i]++;
            k /= i;
        }
    }
    if (k > 1) mp[k]++;
    vector <int> p, vis(n + 1);
    for (auto [x, y] : mp) {
        int val = 1;
        while (y--) val *= x;
        if (val > n) {
            cout << "NO" << endl;
            return;
        }
        p.push_back(val);
        vis[val] = 1;
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) p.push_back(i);
    }

    cout << "YES" << endl;
    for (int x : p) cout << x << ' ';
    cout << endl;
}

signed main() {
    FASTIO
    int t = 1;
    cin >> t;
    while (t--) solve();
}

Think of how you can change the value at index $$$x$$$ as $$$a_x := a_x \oplus a_y$$$ for some valid index $$$y \gt x + 1$$$.

What does $$$z \oplus z$$$ evaluate to for any non-negative integer $$$z$$$?

What happens if you perform the operations for $$$(i, j) = (x, y)$$$, then for $$$(i, j) = (x, y - 1)$$$, where $$$(i, j)$$$ are the operation parameters as described in the problem statement?

It can be easily seen that for doing $$$a_x := a_x \oplus a_y$$$ for the case when $$$y = x + 1$$$, it is sufficient to perform the allowed operation once by selecting $$$(i, j) = (x, y)$$$. We know that $$$z \oplus z = 0$$$ for any non-negative integer $$$z$$$ and also that $$$\oplus$$$ is both commutative and associative.

For the case when $$$y \gt x + 1$$$, applying operations as mentioned in the Hint 3:

• Let $$$b_x := a_x \oplus a_{x+1} \oplus \dots \oplus a_{y-1} \oplus a_y$$$. $$$b_x$$$ will be the new value of $$$a_x$$$ after the first operation. We denote the new value by $$$b_x$$$ and the initial value by $$$a_x$$$ for simplicity.

• Let $$$c_x := b_x \oplus a_{x+1} \oplus \dots \oplus a_{y-1} = a_x \oplus a_{x+1} \oplus \dots \oplus a_{y-1} \oplus a_y \oplus a_{x+1} \oplus \dots a_{y-1} = a_x \oplus a_y$$$, because all the other terms in the expression cancel out each other by the properties of $$$\oplus$$$ operator discussed above.

Hence, it can be seen that to do $$$a_x := a_x \oplus a_{y_1} \oplus a_{y_2} \oplus \dots \oplus a_{y_m}$$$ satisfying $$$1 \le x \lt y_1 \lt y_2 \lt \dots \lt y_m \le n$$$ for any $$$m \ge 0$$$, we can perform the operations in the following order for all $$$k := 1$$$ to $$$m$$$:

• Select $$$(i, j) = (x, y_k)$$$
• Select $$$(i, j) = (x, y_k - 1)$$$ if $$$x \lt y_k - 1$$$, otherwise skip this operation.

Here, the set $$${y_1, y_2, \dots, y_m}$$$ denotes a subset of the suffix of the array $$$a$$$ starting at $$$x+1$$$ (denote it by $$$suffix_{x+1}$$$ now onwards. Hence, we can set $$$a_x := a_x \oplus val$$$ where $$$val$$$ is the Bitwise XOR of any subset of $$$suffix_{x+1}$$$.

Thus, the problem boils down to checking what values $$$a_x$$$ can take for each $$$x := 1$$$ to $$$n$$$, and (if computing in reverse order from $$$n$$$ to $$$1$$$) maintaining a maximum value $$$mx_{x+1}$$$ which can be attained by $$$a_{x+1}$$$ for the $$$suffix_{x+1}$$$ being sorted in non-decreasing order and thus calculating $$$mx_x$$$ accordingly.

This can be done by Dynamic Programming. Let $$$dp_{i, j} = 1$$$ if there exists a subset of $$$suffix_i$$$ with its Bitwise XOR equal to $$$j$$$, and $$$0$$$ otherwise. Now,

Time Complexity = $$$O(n * max(a_i))$$$ or $$$O(n * 2048)$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<vector<ll>> vvint;
typedef vector<ll> vint;
#define endl '\n'
#define int ll
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll inf = 2e18;
const int M = 1e9 + 7, M2 = 998244353, N = 1e7 + 10, N2 = 2e5 + 10;
 
void solve() {
    int n;
    cin >> n;
    vector <int> a(n), mx(n + 1, -1);
    for (int i = 0; i < n; i++) cin >> a[i];
        
    mx[n] = inf;
    vector <vector <int>> dp(n + 1, vector <int> (2048, 0));
    dp[n][0] = 1;
 
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = dp[i + 1]; // do not select a[i]
        for (int j = 0; j < 2048; j++) {
            // select a[i] with some subset of suffix[i+1]
            int k = j ^ a[i];
            if (dp[i + 1][k]) {
                dp[i][j] = 1;
                // value j is attainable at index i
                // need to check mx[i+1] for sorting condition
                if (j <= mx[i + 1]) mx[i] = j;
            }
        }
    }
 
    if (*min_element(mx.begin(), mx.begin() + n) < 0) cout << -1 << endl;
    else {
        for (int i = 0; i < n; i++) cout << mx[i] << ' ';
        cout << endl;
    }
}
 
signed main() {
    FASTIO
    int t = 1;
    cin >> t;
    while (t--) solve();
}

Let $$$E_{in}$$$ be the expected position when the particle arrives at stage $$$i$$$. What is the expected position, $$$E_{out}$$$, after it leaves stage $$$i$$$? Try to write $$$E_{out}$$$ as a linear function of $$$E_{in}$$$.

From Hint 1, you should find a relationship of the form $$$E_{out} = A_i \cdot E_{in} + B_i$$$. Now, consider two consecutive stages, $$$i$$$ and $$$i+1$$$. If $$$E_i = A_i \cdot E_{in} + B_i$$$ and $$$E_{i+1} = A_{i+1} \cdot E_i + B_{i+1}$$$, can you find a new pair $$$(A', B')$$$ such that $$$E_{i+1} = A' \cdot E_{in} + B'$$$? How does this composition operation work?

This problem asks us to find the final expected position of a particle after a series of probabilistic transformations and to support updates to these transformations. The key insight comes from the linearity of expectation.

Step 1: The Transformation at a Single Stage
Let $$$E_{in}$$$ be the expected position of the particle when it arrives at stage $$$i$$$. We want to find $$$E_{out}$$$, the expected position when it leaves stage $$$i$$$.

According to the rules:
With probability $$$p_i$$$, the new position is $$$m_i \cdot E_{in}$$$.
With probability $$$(1 - p_i)$$$, the new position is $$$E_{in} + s_i$$$.
By the definition of expected value:
$$$E_{out} = p_i \cdot (m_i \cdot E_{in}) + (1 - p_i) \cdot (E_{in} + s_i)$$$
Let's expand and group the $$$E_{in}$$$ terms. All calculations must be modulo $$$M = 10^9 + 7$$$.
$$$E_{out} = (p_i \cdot m_i) \cdot E_{in} + (1 - p_i) \cdot E_{in} + (1 - p_i) \cdot s_i$$$
$$$E_{out} = (p_i \cdot m_i + 1 - p_i) \cdot E_{in} + (1 - p_i) \cdot s_i$$$
This is a linear transformation of the form $$$E_{out} = A_i \cdot E_{in} + B_i$$$, where: $$$p_i = u_i \cdot v_i^{-1} \pmod{M}$$$ (where $$$v_i^{-1}$$$ is the modular multiplicative inverse of $$$v_i$$$), with $$$A_i = (p_i \cdot m_i + 1 - p_i) \pmod{M}$$$ and $$$B_i = (1 - p_i) \cdot s_i \pmod{M}$$$. [ Note: A simpler way to calculate $$$1 - p_i$$$ is $$$(v_i - u_i) \cdot v_i^{-1} \pmod{M}$$$. ]

Step 2: Composing Transformations
Now, let's see what happens when we pass through two stages, $$$i$$$ and $$$j$$$, in sequence.
Let $$$f_i(x) = A_i \cdot x + B_i$$$ and $$$f_j(x) = A_j \cdot x + B_j$$$.
The combined transformation is $$$f_j(f_i(x))$$$:
$$$f_j(f_i(x)) = f_j(A_i \cdot x + B_i)$$$
$$$f_j(f_i(x)) = A_j \cdot (A_i \cdot x + B_i) + B_j$$$
$$$f_j(f_i(x)) = (A_j \cdot A_i) \cdot x + (A_j \cdot B_i + B_j)$$$
This resulting transformation is also a linear function! We have found a way to compose two transformations. If stage $$$i$$$ is represented by the pair $$$(A_i, B_i)$$$ and stage $$$j$$$ is represented by $$$(A_j, B_j)$$$, their composition (passing through $$$i$$$ then $$$j$$$) is a new pair $$$(A_{comp}, B_{comp})$$$, where $$$A_{comp} = A_j \cdot A_i \pmod{M}$$$ and $$$B_{comp} = (A_j \cdot B_i + B_j) \pmod{M}$$$. This composition operation is associative. This is crucial.

Step 3: Using a Segment Tree
The problem requires us to handle two operations:
RECONFIGURE $$$i$$$ ... : Update the parameters for stage $$$i$$$.
This means we just need to recalculate the pair $$$(A_i, B_i)$$$ for that single stage. This is a point update.
RUN $$$L$$$ $$$R$$$ $$$x_{start}$$$: Calculate the final expected position after passing through stages $$$L$$$ to $$$R$$$.
This is equivalent to finding the composition of all transformations $$$f_R \circ f_{R-1} \circ \dots \circ f_L$$$ and applying it to $$$x_{start}$$$. This is a range query.

A data structure that efficiently handles point updates and associative range queries is a Segment Tree. We will build a segment tree where each node stores a pair $$$(A, B)$$$ representing the composite transformation for its corresponding range.
Leaf Nodes (range $$$[i, i]$$$): A leaf node for stage $$$i$$$ will store the pair $$$(A_i, B_i)$$$ we calculated in Step 1.
Internal Nodes: An internal node representing the range $$$[l, r]$$$ will be formed by combining its left child (range $$$[l, mid]$$$) and right child (range $$$[mid+1, r]$$$). Let the left child store $$$(A_{left}, B_{left})$$$ and the right child store $$$(A_{right}, B_{right})$$$. Since the particle passes through the left range first, the parent node will store the composition $$$(A_{right}, B_{right}) \circ (A_{left}, B_{left})$$$:
$$$A_{parent} = A_{right} \cdot A_{left} \pmod{M}$$$$$$B_{parent} = (A_{right} \cdot B_{left} + B_{right}) \pmod{M}$$$

Identity Element: For the query operation, we need an identity transformation $$$f(x) = x$$$, which corresponds to the pair $$$(1, 0)$$$. This is the "empty" composition. With this structure:
RECONFIGURE (Type 1): Calculate the new $$$(A_i, B_i)$$$ for stage $$$i$$$. Update the leaf node for $$$i$$$ and propagate the changes up the tree by re-calculating the composition at each ancestor node. This takes $$$O(\log N)$$$ time.
RUN (Type 2): Perform a range query on the segment tree for $$$[L, R]$$$. This query will combine the pairs from the necessary nodes, returning a final composite pair $$$(A_{L \to R}, B_{L \to R})$$$. This also takes $$$O(\log N)$$$ time.
The final answer is then $$$(A_{L \to R} \cdot x_{start} + B_{L \to R}) \pmod{M}$$$.

The total complexity per test case will be $$$O((N+Q) \log N)$$$ to build the tree and process all queries.

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long

const ll mod=1000000007ll;

const ll N=1e6;

// Has time complexity O(N/2+N/3+N/5+...)=O(NloglogN) by Mertens' Third theorem
vector<bool>nums(N+1);
vector<int>primes;
void sieve(){
    nums[0]=true;
    nums[1]=true;
    for(int i=2;i<=N;i++)
    {
        if(nums[i]==false){
            primes.push_back(i);
            for(int j=i*i;j<=N;j+=i){
                nums[j]=true;
            }
        }
    }
}

// Has time complexity O(N/2+N/3+N/5+...)=O(NloglogN) by Mertens' Third theorem
vector<int>spf(N+1,1);
void smallestPrimeFactor(){
    spf[0]=0;
    for(int i=2;i<=N;i++){
        if(spf[i]==1){
            for(int j=i;j<=N;j+=i){
                if(spf[j]==1) spf[j]=i;
            }
        }
    }
}

// Has time complexity O(log2b)
long long binpow(int a,int b)
{
    if(b==0) return 1ll;
    int res=binpow(a,b/2);
    if(b%2) return res*res*a;
    else return res*res;
}

// Has time complexity O(n)
int mex(vector<int>& arr)
{
    int m=0;
    int n=arr.size();
    sort(arr.begin(),arr.end());
    for(int i=0;i<n;i++)
    {
        if(arr[i]==m) m++;
    }
    return m;
}

// Has time complexity O(1)
int mult(int a,int b,int m)
{
    return ((a%m)*(b%m))%m;
}

// Has time complexity O(log2y)
int power(int x,int y,int p)
{
    int res=1ll;
    x=x%p;
    while(y>0)
    {
        if(y&1) res=mult(res,x,p);
        y>>=1;
        x=mult(x,x,p);
    }
    return res;
}
// Has time complexity O(log2(p))
int modInverse(int n,int p)
{
    return power(n,p-2,p);
}
 
// Returns nCr % p using Fermat's little theorem.
long long nCrModPFermat(long long n,int r, int p,vector<int>& fac)
{
    if (n < r)
        return 0;
    if (r == 0)
        return 1;
    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}

void build(vector<int>& arr,vector<int>& brr,vector<pair<int,int>>& seg,int ind,int low,int high)
{
    if(low==high)
    {
        seg[ind]={arr[low],brr[low]};
        return;
    }
    int mid=(low+high)>>1;
    build(arr,brr,seg,2*ind+1,low,mid);
    build(arr,brr,seg,2*ind+2,mid+1,high);

    seg[ind].first=mult(seg[2*ind+1].first,seg[2*ind+2].first,mod);
    seg[ind].second=(mult(seg[2*ind+2].first,seg[2*ind+1].second,mod)+seg[2*ind+2].second%mod)%mod;
}

void update(vector<pair<int,int>>& seg, int ind,int low,int high,int pos,int valA,int valB)
{
    if(low==high) seg[ind]={valA,valB};
    else
    {
        int mid=(low+high)>>1;
        if(pos<=mid) update(seg,2*ind+1,low,mid,pos,valA,valB);
        else update(seg,2*ind+2,mid+1,high,pos,valA,valB);

        seg[ind].first=mult(seg[2*ind+1].first,seg[2*ind+2].first,mod);
        seg[ind].second=(mult(seg[2*ind+2].first,seg[2*ind+1].second,mod)+seg[2*ind+2].second%mod)%mod;
    }
}

pair<int,int> query(vector<pair<int,int>>& seg,int ind,int low,int high,int l,int r)
{
    if(low>=l && high<=r) return seg[ind];
    if(low>r || high<l) return {1ll,0ll};
    int mid=(low+high)>>1;

    pair<int,int> left=query(seg,2*ind+1,low,mid,l,r);
    pair<int,int> right=query(seg,2*ind+2,mid+1,high,l,r);

    pair<int,int> res;
    res.first=mult(left.first,right.first,mod);
    res.second=(mult(right.first,left.second,mod)+right.second%mod)%mod;
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int t;
    cin>>t;
    while(t--)
    {
        int n,q;
        cin>>n>>q;

        vector<int> u(n),v(n),m(n),s(n);
        for(int i=0;i<n;i++) cin>>u[i]>>v[i]>>m[i]>>s[i];

        vector<int> a(n),b(n);
        for(int i=0;i<n;i++)
        {
            a[i]=(mult(u[i],m[i],mod)+v[i]-u[i]+mod)%mod;
            a[i]=(a[i]+mod)%mod;
            a[i]=mult(a[i],modInverse(v[i],mod),mod);

            b[i]=(v[i]-u[i]+mod)%mod;
            b[i]=(b[i]+mod)%mod;
            b[i]=mult(b[i],s[i],mod);
            b[i]=mult(b[i],modInverse(v[i],mod),mod);
        }

        vector<pair<int,int>> seg(4*n);
        build(a,b,seg,0,0,n-1);

        while(q--)
        {
            int f;
            cin>>f;
            if(f==1)
            {
                int i,u,v,m,s;
                cin>>i>>u>>v>>m>>s;
                a[i]=(mult(u,m,mod)+v-u+mod)%mod;
                a[i]=(a[i]+mod)%mod;
                a[i]=mult(a[i],modInverse(v,mod),mod);

                b[i]=(v-u+mod)%mod;
                b[i]=(b[i]+mod)%mod;
                b[i]=mult(b[i],s,mod);
                b[i]=mult(b[i],modInverse(v,mod),mod);

                update(seg,0,0,n-1,i,a[i],b[i]);
            }
            else
            {
                int l,r,x;
                cin>>l>>r>>x;
                pair<int,int> q=query(seg,0,0,n-1,l,r);
                int res1=mult(q.first,x,mod);
                int res2=q.second;
                cout<<(res1+res2)%mod<<"\n";
            }
        }
    }
}

If the leaf node is not removed after each query, would there be a fixed leaf node where the ball always ends up for every node? If so, how would you find that node?

Think of a data structure that can add connections after a leaf node is removed but still point to the node which can be removed in next iteration.

If we never removed leaves, every node has a fixed destination leaf obtained by repeatedly moving to the smallest-$$$a$$$ child. Call this destination $$$dp_v$$$. We can compute dp for all $$$v$$$ by a single tree traversal once the children of every node are ordered by their $$$a-array$$$ values.

When a leaf $$$x$$$ is removed, some nodes that originally had $$$dp[...] = x$$$ should now end up at the next valid leaf they would reach if $$$x$$$ were absent. Instead of updating many dp values explicitly, we maintain a redirected chain of successors so that each removed node points to the next candidate that could be removed later.

Imagine a directed chain that links every removed leaf to the next candidate leaf. To answer a query, we want the first non-removed leaf on the $$$dp_b$$$ chain. Traversing this chain naïvely can be linear in the number of removals, but if we compress paths (i.e., jump over removed nodes and remember the jump), repeated queries become fast.

For the implementation of redirected chain of successors and path compression, one way is to use Disjoint Set Union data structure, thus resulting in the final complexity $$$ O(n\log n + q \alpha(n))$$$

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define s(x) sort(x.begin(), x.end())
#define sg(x) sort(x.begin(), x.end(),greater<int>())
#define vint vector<int>
#define MOD ((int)1e9+7)

class dsu {
public:
    vector<int> parents;
    vector<int> rank;

    dsu(int size) : parents(size), rank(size, 1) {
        for (int i = 0; i < size; i++) {
            parents[i] = i;
        }
    }

    /** @return the "representative" node in x's component */
    int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

    /** @return whether the merge changed connectivity */
    bool unite(int x, int y) {
        int x_root = find(x);
        int y_root = find(y);
        if (x_root == y_root) {
            return false;
        }

        if (rank[x_root] < rank[y_root]) {
            swap(x_root, y_root);
        }

        if (rank[x_root] == rank[y_root])
            rank[x_root]++;
        parents[y_root] = x_root;
        return true;
    }
    /** @return whether x and y are in the same connected component */
    bool connected(int x, int y) { return find(x) == find(y); }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<vint> adj(n);
    vint v(n);
    vint dp(n);
    dsu d(n);
    vector<bool> rem(n);

    for (auto& x : v)
        cin >> x;

    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    if (n == 1) {
        for (int i = 0; i < q; i++)
        {
            int a;
            cin >> a;
            if (i == 0)
                cout << 1 << endl;
            else cout << -1 << endl;
        }
        return;
    }

    for (int i = 0; i < n; i++)
    {
        auto& x = adj[i];
        sort(x.begin(), x.end(), [&](auto a, auto b) {
            return v[a] < v[b];
            });
    }

    int rank = 0;
    vint m(n + 1);
    vint idxtorank(n + 1);

    auto dfs = [&](auto dfs, int s, int p)->int {
        if (p != -1 && adj[s].size() == 1) {

            idxtorank[s] = d.rank[s] = rank;
            m[rank++] = s;
            return dp[s] = s;
        }

        for (auto v : adj[s])
            if (v != p)
                dfs(dfs, v, s);

        if (p == adj[s][0]) {
            dp[s] = dp[adj[s][1]];
        }
        else
            dp[s] = dp[adj[s][0]];

        idxtorank[s] = d.rank[s] = rank;
        m[rank++] = s;

        return dp[s];
        };

    dfs(dfs, 0, -1);
    for (int i = 0; i < q; i++)
    {
        int a;
        cin >> a;
        a--;
        if (rem[a])
        {
            cout << -1 << endl;
            continue;
        }

        int plc = d.find(dp[a]);
        int idx = m[idxtorank[plc] + 1];
        cout << plc + 1 << endl;
        d.unite(idx, dp[a]);
        rem[plc] = true;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

For case of $$$d=1$$$, $$$n$$$ should be equal to $$$k+2$$$, otherwise no such graph exists. For case of $$$d=2$$$, $$$n$$$ should be atleaast $$$3$$$ otherwie no such graph exists.

For a graph $$$G$$$, if for some $$$r\geq 0$$$, we have that $$$L^r(G)$$$ contains a cycle(not necessarily induced) with degree of each vertex of cycle equal to maximum degree of $$$L^r(G)$$$(i.e. $$$\Delta(L^r(G))$$$), then $$$\Delta(L^x(G))=(\Delta(L^r(G))-2)\cdot 2^{x-r}+2$$$ for $$$x\geq r$$$.

The possible values of $$$d$$$ under the constraint $$$k\geq 8$$$ and $$$1\leq d\leq 90\cdot 2^{k-8}$$$ are:

• $$$1$$$
• $$$2$$$
• $$$6\cdot 2^{k-5}+2$$$
• $$$8\cdot 2^{k-5}+2$$$
• $$$11\cdot 2^{k-5}+2$$$

We say a graph $$$G$$$ has $$$\Delta$$$-cycle if there exists a cycle in $$$G$$$(not necessarily induced) with degree of all vertices of cycle equal to $$$\Delta(G)$$$.

• $$$d=1$$$: $$$G$$$ is a path graph with $$$k+2$$$ vertices.

• $$$d=2$$$: $$$G$$$ is either a cycle with $$$\geq 3$$$ vertices or a path graph with $$$\geq k+3$$$ vertices.

• $$$d=6\cdot 2^{k-5}+2$$$

The graph above has $$$\Delta(L^4(G))=5$$$ and $$$L^4(G)$$$ has a $$$\Delta$$$-cycle of size $$$3$$$. So, $$$\Delta(L^r(G))=3*2^{r-4}+2=6*2^{r-5}+2$$$ for $$$r\geq 4$$$. So, for this case, $$$n=5$$$

• $$$d=8\cdot 2^{k-5}+2$$$

Dotted edge represents a path of length $$$\geq 1$$$ in terms of number of edges. The two cases of graphs above have $$$\Delta(L^2(G))=3$$$ and $$$L^2(G)$$$ has a $$$\Delta$$$-cycle of size $$$3$$$. So, $$$\Delta(L^r(G))=2^{r-2}+2=8*2^{r-5}+2$$$ for $$$r\geq 2$$$. So, for this case, $$$n\geq 6$$$.

• $$$d=11\cdot 2^{k-5}+2$$$

The graph above has $$$\Delta(L^5(G))=13$$$ and $$$L^5(G)$$$ has a $$$\Delta$$$-cycle of size $$$3$$$. So, $$$\Delta(L^r(G))=11*2^{r-5}+2$$$ for $$$r\geq 5$$$. So, for this case, $$$n=6$$$.

It can be proven that for every other simple connected graph $$$G$$$, $$$\Delta(L^r(G)) \gt 90\cdot 2^{r-8}$$$ for $$$r\geq 8$$$.

//Written By Aryan Sanghi

#include<bits/stdc++.h>

using namespace std;

#define ll long long int
#define rep(i, n) for(ll i = 0; i < n;i++)
#define repi(i, a, n) for(ll i = a;i < n;i++)

void solve(){
    ll n, k, d;
    cin>>n>>k>>d;

    if(d==1){
        if(n==k+2){
            cout<<n-1<<"\n";
            rep(i, n-1) cout<<i+1<<" "<<i+2<<"\n";
        }
        else{
            cout<<-1<<"\n";
        }
        return;
    }
    if(d==2){
        if(n>=3){
            cout<<n<<"\n";
            rep(i, n) cout<<i+1<<" "<<(i+1)%n+1<<"\n";
        }
        else{
            cout<<-1<<"\n";
        }
        return;
    }
    if(k<=log2((2e18-2)/3)+4 && d==3*((long long)1<<(k-4))+2){
        if(n==5){
            cout<<"4\n1 2\n1 3\n1 4\n4 5\n";
        }
        else{
            cout<<"-1\n";
        }
        return;
    }
    if(k<=log2((2e18-2)/4)+4 && d==4*((long long)1<<(k-4))+2){
        if(n>=6){
            cout<<n-1<<"\n1 2\n1 3\n1 4\n";
            repi(i, 3, n-1) cout<<i+1<<" "<<i+2<<"\n";
        }
        else{
            cout<<-1<<"\n";
        }
        return;
    }
    if(k<=log2((2e18-2)/11)+5 && d==11*((long long)1<<(k-5))+2){
        if(n==6){
            cout<<"5\n1 2\n1 3\n1 4\n3 5\n4 6\n";
        }
        else{
            cout<<-1<<"\n";
        }
        return;
    }
    cout<<-1<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll t=1;
    cin>>t;
    
    while(t--)
    {
        solve();
    }
}

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <climits>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define mp make_pair
#define all(x) (x).begin(),(x).end()

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

ll floor_div(ll x, ll y) {
	assert(y != 0);
	if (y < 0) {
		y = -y;
		x = -x;
	}
	if (x >= 0) return x / y;
	return (x + 1) / y - 1;
}
ll ceil_div(ll x, ll y) {
	assert(y != 0);
	if (y < 0) {
		y = -y;
		x = -x;
	}
	if (x <= 0) return x / y;
	return (x - 1) / y + 1;
}
template<typename T>
T sqr(T x) {
	return x * x;
}

void solve() {
	ll n, k, d;
	scanf("%lld%lld%lld", &n, &k, &d);
	if (d == 1) {
		if (n == k + 2) {
			printf("%lld\n", n - 1);
			for (int i = 1; i < n; i++)
				printf("%d %d\n", i, i + 1);
		} else {
			printf("-1\n");
		}
		return;
	}
	if (d == 2) {
		if (n < 3) {
			printf("-1\n");
		} else {
			printf("%lld\n", n);
			for (int i = 1; i < n; i++)
				printf("%d %d\n", i, i + 1);
			printf("1 %lld\n", n);
		}
		return;
	}
	if (k > 64) {
		printf("-1\n");
		return;
	}
	d -= 2;
	ll e = d >> (k - 5);
	if (d != (e << (k - 5))) {
		printf("-1\n");
		return;
	}
	if (e == 6) {
		if (n == 5) {
			printf("4\n1 2\n1 3\n1 4\n4 5\n");
		} else {
			printf("-1\n");
		}
	} else if (e == 8) {
		if (n >= 6) {
			printf("%lld\n1 2\n1 3\n1 4\n", n - 1);
			for (int i = 4; i < n; i++)
				printf("%d %d\n", i, i + 1);
		} else {
			printf("-1\n");
		}
	} else if (e == 11) {
		//printf("-1\n");
		//return;
		if (n == 6) {
			printf("5\n1 2\n1 3\n3 4\n1 5\n5 6\n");
		} else {
			printf("-1\n");
		}
	} else {
		printf("-1\n");
	}
}

int main() {
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);


	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++) {
		eprintf("--- Case #%d start ---\n", i);
		//printf("Case #%d: ", i);

		solve();

		//printf("%lld\n", (ll)solve());

		/*
		if (solve()) {
			printf("Yes\n");
		} else {
			printf("No\n");
		}
		*/

		eprintf("--- Case #%d end ---\n", i);
		eprintf("time = %.5lf\n", getCurrentTime());
		eprintf("++++++++++++++++++++\n");
	}


	return 0;
}