#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int testcases;
    cin >> testcases;
    for (int t = 1; t <= testcases; t++)
    {
        int n;
        cin >> n;
        vector<int> v(n);
        for (int j = 0; j < n; j++)
        {
            cin >> v[j];
        }
        sort(v.begin(), v.end());
        cout << 2 * (v[n - 1] - v[0]) + 2 * (v[n - 2] - v[1]) << endl;
    }
}

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)
    ans = 2 * (a[n - 1] - a[0] + a[n - 2] - a[1])
    print(ans)

After querying "$$$?$$$ $$$1$$$ $$$1$$$" What do we know about the location of mines?

To generate any possible $$$m$$$, it takes at most two operations.

Let's determine the achievable values of $$$m$$$ for a given $$$n$$$.

If $$$n$$$ is a perfect power of $$$2$$$, then it cannot be broken down further, and no $$$m \lt n$$$ is achievable. Otherwise, if $$$n$$$ has at least two set bits, let's denote the most significant bit as $$$a$$$ and the second most significant bit as $$$b$$$.

Fact 1: All $$$m$$$ values less than $$$n$$$ are achievable if their most significant bit does not lie between $$$b+1$$$ and $$$a-1$$$.

Reason: For instance, $$$1001????$$$ can be decomposed into $$$1000????$$$ and $$$0001????$$$, or $$$1001????$$$ and $$$0000????$$$. In either case, we can never flip the $$$6^{th}$$$ or $$$7^{th}$$$ bit.

Using the above fact, we can break the problem into two cases:

Case 1: If the most significant bit of $$$m$$$ is at position $$$\leq b$$$.

Perform the first operation as $$$2^{b+1} - 1$$$ and $$$n \oplus (2^{b+1} - 1)$$$ ($$$10001????$$$ -> $$$10000????$$$ and $$$000011111$$$ in binary form). Then, any submask of $$$2^{b+1} - 1$$$ can be created in the next operation.

Case 2: If the most significant bit of $$$m$$$ is at position $$$a$$$.

If the most significant bit of $$$m$$$ is at position $$$a$$$, then $$$m$$$ can be obtained in one operation as $$$m$$$ and $$$m \oplus n$$$, since $$$m \lt n$$$ as given in the question, and $$$n \oplus m$$$ has its most significant bit $$$ \lt a$$$.

#include<bits/stdc++.h>

using namespace std;
 
using ll = long long;
 
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    ll t;
    cin >> t;
    
    while (t--) {
        ll n, m;
        cin >> n >> m;
        
        ll hi = 0, sec_hi = 0;
        for (ll p = (1LL<<62); p > 0; p >>= 1) {
            if (p & n) {
                if (!hi) hi = p;
                else if (!sec_hi) sec_hi = p;
            }
        }
        bool flag = (sec_hi && ((m & hi) || (m < sec_hi*2)));
        if (!flag) {
            cout << -1 << '\n';
            continue;
        }
        vector<ll> ans = {n, m};
        if (!(m & hi) && !(m & sec_hi)) ans = {n, m^sec_hi, m};
        
        cout << (ll)ans.size()-1 << '\n';
        for (auto &x: ans) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

If both $$$p_1$$$ and $$$p_2$$$ are perfect powers of $$$2$$$, it is a losing state since you cannot perform a break operation on either of those.

If either $$$p_1$$$ or $$$p_2$$$ has a bit count of $$$2$$$, then this is a winning state.

Fact 1: If $$$p_1$$$ has an odd bit count, then it can only be broken into two numbers such that one has an odd bit count and the other has an even bit count.

Fact 2: If either $$$p_1$$$ or $$$p_2$$$ has an even bit count, then this is a winning state.

Reason : If either $$$p_1$$$ or $$$p_2$$$ has an even bit count, without loss of generality, assume it's $$$p_1$$$. Then break it into $$$2^{msb \text{ of } p_1}$$$ and $$$p_1 \oplus 2^{msb \text{ of } p_1}$$$, where $$$msb$$$ is the most significant bit.

If the opponent chooses $$$2^{msb \text{ of } p_1}$$$, they instantly lose (using Hint $$$1$$$), so they are forced to choose the other number with an odd bit count. From Fact $$$1$$$, we can conclude that in the next turn, the state will remain conserved for the current player.

Because we eliminate the most significant bit in every query, this game will go on for at most $$$60$$$ turns for the player who reached this position first. At one point, the player who is at this state will have a number with two set bits.

Hence, from Hint $$$2$$$, we can say this player will win. So, as Alice, you will start first if $$$n$$$ has an even number of bits and start second if it has an odd number of bits. Proceed using the strategy discussed above. So as Alice you have will start first if $$$n$$$ has even number of bits and start second if it has odd number of bits. Any proceed using the strategy discussed above.

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int testcases;cin>>testcases;
 
    for(int testcase=1;testcase<=testcases;testcase++){
        long long n;cin>>n;
        long long curr=n;
        int parity=0;
        if(__builtin_popcountll(n)%2){
            cout<<"secoNd"<<endl;
        }else{
            cout<<"firSt"<<endl;
            parity=1;
        }
        int turn=0;
        while(1){
            if(turn%2==parity){
                long long p1,p2;cin>>p1>>p2;
                if (p1 == 0 && p2 == 0)
                    break;
                if(__builtin_popcountll(p1)%2==0){
                    curr=p1;
                }else{
                    curr=p2;
                }
            }else{
                int pos=0;
                for(int i=0;(1ll<<i)<curr;i++){
                    if(curr&(1ll<<i)){
                        pos=i;
                    }
                }
                long long p1=(1ll<<pos);
                long long p2=curr^p1;
                cout<<p1<<" "<<p2<<endl;
                curr = p1;
            }
            turn++;
        }
    }
}

Fact 1: If for $$$(x, y, z)$$$ their pairwise GCDs are equal to their common GCD (this means that $$$(x, y, z)$$$ = $$$(g * X, g * Y, g * Z)$$$ where $$$(X, Y, Z)$$$ are pairwise coprime), then making an operation on them (gives $$$(g * X * Y, g * X * Z,g * Y * Z)$$$) and looking at the subsequences of size EXACTLY 2, we find all three GCD: $$$x$$$, $$$y$$$, $$$z$$$. Let's call such tuple NICE.

Result: If we can split all values in the array into independent NICE tuples, then we can just perform an operation on each of them and the problem is solved.

Fact 2: We don't touch any value $$$\leq$$$ $$$\frac{n}{2}$$$. If there is $$$x$$$ $$$\leq$$$ $$$\frac{n}{2}$$$, then $$$2 * x \leq n$$$. If we don't touch $$$x$$$, then we will always have another value that is divisible by $$$x$$$ (it's easy to see that performing an operation on a multiple of $$$x$$$ leaves us with another multiple of $$$x$$$), so we will always have GCD equal to $$$x$$$ taking a subsequence $$$(x, x * A)$$$.

Fact 3: A sequence of consecutive integers $$$(x, x+1, x+2, ..., x+11)$$$ can be partitioned into $$$4$$$ disjoint sets of size $$$3$$$, each forming a NICE tuple, if $$$(x+11) \% 4$$$ equals $$$2$$$ or $$$1$$$.

For $$$(x+11) \% 4 = 2$$$: The sets $$$(x, x+1, x+2)$$$, $$$(x+4, x+5, x+6)$$$ and $$$(x+8, x+9, x+10)$$$ are NICE because, the first and third terms are always odd, and the second term is always even. The set $$$(x+3, x+7, x+11)$$$ is NICE because it has the form of $$$2*(2*n-1)$$$, $$$2*(2*n)$$$, $$$2*(2*n+1)$$$, ensuring that the pairwise GCDs are equal to the common GCD.

For $$$(x+11) \% 4 = 1$$$: The sets $$$(x, x+4, x+8)$$$, $$$(x+1, x+2, x+3)$$$, $$$(x+5, x+6, x+7)$$$ and $$$(x+9, x+10, x+11)$$$ are NICE, the same logic like $$$(x+11) \% 4 = 2$$$ follows,

If $$$n \% 4 = 3$$$ we can do one operation as $$$(1, 2, n)$$$, and if $$$n \% 4 = 0$$$ we can do one operation as $$$(1, n-1, n)$$$. Let's group the remaining elements into the groups of size $$$12$$$, starting from the end, and continuing until we reach the number $$$\frac{n}{2}$$$.

Eventually, we can count that we used no more than $$$\lfloor \frac{n}{6} \rfloor + 5$$$ operations.

Solutions for $$$n \leq 13$$$ should be found manually.

#include<bits/stdc++.h>
 
using namespace std;
vector<vector<vector<int>>> pans(14);
int main(){
 
    ios::sync_with_stdio(false), cin.tie(nullptr);
 
    int t;cin>>t;
 
    pans[3]={{1,2,3}};
    pans[4]={{1,3,4}};
    pans[5]={{3,4,5}};
    pans[6]={{1,3,5},{2,4,6}};
    pans[7]={{2,4,6},{3,5,7}};
    pans[8]={{2,6,8},{3,5,7}};
    pans[9]={{1,3,5},{2,4,6},{7,8,9}};
    pans[10]={{3,4,5},{2,6,8},{7,9,10}};
    pans[11]={{2,6,8},{3,5,7},{9,10,11}};
    pans[12]={{1,11,12},{6,8,10},{5,7,9}};
    pans[13]={{1,12,13},{7,9,11},{6,8,10}};
    for(int tt=0;tt<t;tt++){
        int n;cin>>n;
        if(n<=2){
            cout<<-1<<endl;
        }else if(n<14){
            cout<<pans[n].size()<<endl;
            for(auto w: pans[n]){
                cout<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl;
            }
        }else{
            vector<int> v(n);
            for(int i=0;i<n;i++){
                v[i]=i+1;
            }
            vector<vector<int>> ans;
            while (2*v.size()>n){
                if(v.size()%4==2){
                    vector<int> buf;
                    for(int i=0;i<12;i++){
                        buf.push_back(v.back());
                        v.pop_back();
                    }
                    reverse(buf.begin(),buf.end());
                    ans.push_back({buf[0],buf[1],buf[2]});
                    ans.push_back({buf[4],buf[5],buf[6]});
                    ans.push_back({buf[8],buf[9],buf[10]});
                    ans.push_back({buf[3],buf[7],buf[11]});
                }else if(v.size()%4==1){
                    vector<int> buf;
                    for(int i=0;i<12;i++){
                        buf.push_back(v.back());
                        v.pop_back();
                    }
                    reverse(buf.begin(),buf.end());
                    ans.push_back({buf[1],buf[2],buf[3]});
                    ans.push_back({buf[5],buf[6],buf[7]});
                    ans.push_back({buf[9],buf[10],buf[11]});
                    ans.push_back({buf[0],buf[4],buf[8]});
                }else if(v.size()%4==3){
                    vector<int> buf;
                    buf.push_back(v.back());
                    v.pop_back();
                    buf.push_back(2);
                    buf.push_back(1);
                    reverse(buf.begin(),buf.end());
                    ans.push_back({buf[0],buf[1],buf[2]});
                }else{
                    vector<int> buf;
                    buf.push_back(v.back());
                    v.pop_back();
                    buf.push_back(v.back());
                    v.pop_back();
                    buf.push_back(1);
                    reverse(buf.begin(),buf.end());
                    ans.push_back({buf[0],buf[1],buf[2]});
                }
            }
            cout<<ans.size()<<endl;
            for(auto w: ans){
                cout<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl;
            }
        }
    }
}