// In the name of God
#include <bits/stdc++.h>
using namespace std;
int main() {
    int l, a, b, t;
    cin >> t;
    while(t--) {
        cin >> l >> a >> b;
        cout << l - __gcd(l, b) + a % __gcd(l, b) << '\n'; 
    }
    return 0;
}

• Step 1: It can be shown (for instance, via a contradiction argument) that, to obtain the lexicographically minimum final string $$$s$$$, we must ensure $$$s$$$ is lexicographically minimum at each intermediate step as well.

• Step 2: Therefore, at every step $$$i$$$, we choose the lexicographically smaller result between adding $$$a_i$$$ to the beginning or the end of our current string.

• Step 3: Initially, $$$s$$$ is the empty string. Suppose before step $$$i$$$, the current string is $$$s_i$$$. Then the best choice for the updated string is:

• Step 4: By applying this choice at each step, we can compute the final (minimum) string in $$$\mathcal{O}(nS)$$$ where $$$S$$$ is the sum of string lengths.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s[n], t;
        for(int i = 0; i < n; i++)
            cin >> s[i];
        for(int i = 0; i < n; i++)
            t = min(t+s[i], s[i]+t);
        cout << t << '\n';
    }
    return 0;
}

We build $$$a_1,\dots,a_k$$$ bit by bit from the highest bit to $$$0$$$.

Let

Maintain two sets of indices:

• $$$T$$$ (tight): current prefix of $$$a_i$$$ equals the prefix of $$$n$$$,

• $$$L$$$ (loose): current prefix of $$$a_i$$$ is already smaller than the prefix of $$$n$$$.

Initially, $$$T={1,\dots,k}$$$, $$$L=\emptyset$$$, and all $$$a_i=0$$$.

Greedy rule for each bit $$$b$$$ (from high to low).

• If the $$$b$$$-th bit of $$$n$$$ is $$$1$$$, then the number of $$$a_i$$$ having bit $$$b$$$ equal to $$$1$$$ must be odd. To maximize the sum we set as many ones as possible, i.e. exactly $$$o(k)$$$. So:

  • if $$$k$$$ is odd, set this bit in all $$$k$$$ numbers;
  • if $$$k$$$ is even, set it in all but one number. Prefer choosing that one from $$$T$$$ (if possible), because then it becomes loose ($$$T\to L$$$), which can help later.

• If the $$$b$$$-th bit of $$$n$$$ is $$$0$$$, then the number of ones in this bit must be even. Tight indices cannot put $$$1$$$ here (otherwise $$$a_i \gt n$$$), so only $$$L$$$ may receive ones. Thus we set this bit in exactly $$$e(|L|)$$$ loose numbers (all of them if $$$|L|$$$ is even, otherwise all but one).

Why it is optimal. At bit $$$b$$$, each extra chosen $$$1$$$ adds $$$2^b$$$ to the total sum, and this gain is larger than anything we can get from lower bits. Also, the XOR condition fixes the parity in every bit, so we can only change the number of $$$1$$$’s by removing them from an even number of elements. So, at every bit we should keep as many $$$1$$$’s as possible, as long as we do not violate $$$a_i\le n$$$. When the $$$b$$$-th bit of $$$n$$$ is $$$1$$$ and $$$k$$$ is even, we must place one $$$0$$$; choosing it from a tight index increases $$$|L|$$$, which can help us place more $$$1$$$’s later when $$$n$$$ has $$$0$$$-bits.

This directly gives a construction with $$$0\le a_i\le n$$$, XOR equal to $$$n$$$, and maximum possible sum in $$$\mathcal{O}(k \log n)$$$.

// In the name of god
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        int a[k]{}, p = 0;
        if(k&1)
            for(int i = 0; i < k; i++)
                a[i] = n;
        else {
            for(int i = 30; i >= 0; i--) {
                if(n >> i & 1) {
                    for(int j = 0; j < k; j++)
                        if(j != min(p, k-1))
                            a[j] += (1 << i);
                    if(p < k)
                        p++;
                } else
                    for(int j = 0; j < p/2*2; j++)
                        a[j] += (1 << i);
            }
        }
        for(int i = 0; i < k; i++)
            cout << a[i] << (i+1 == k? '\n':' ');
    }
    return 0;
}

Let $$$x_1, x_2, \ldots, x_n$$$ be the sorted list of points, and let $$$d_i \ (1 \le i \le n-1)$$$ be the distance between consecutive points, i.e.

We try to find the largest prefix of points that can be made connected.

Consider some valid choice of radii, and assume that the radius of the first disk is $$$r_1 = x$$$. In order for the second disk to be tangent to the first one, its radius must be

Continuing in this way, the third disk must have radius

In general, if we connect the first $$$k$$$ disks together, the radius of the $$$i$$$-th disk $$$(1 \le i \le k)$$$ must be

For this configuration to be valid, we must have

Substituting the expression for $$$r_i$$$, we obtain

For odd $$$i$$$, this inequality becomes

which is equivalent to

For even $$$i$$$, we obtain

which is equivalent to

Therefore, for each $$$i$$$ we obtain an interval of valid values for $$$x$$$. By iterating over $$$i$$$ and maintaining the intersection of all these intervals, we can determine the first index where the intersection becomes empty. This index gives the largest prefix of disks that can be made connected.

After removing these disks, we can repeat the same process on the remaining ones. It can be shown that this procedure finds the correct answer and runs in $$$O(n)$$$ time.

Why it is optimal.

For each index $$$i$$$, let $$$f_i$$$ be the rightmost position such that, for every $$$j$$$ with $$$i \le j \lt f_i$$$, we can simultaneously make the $$$j$$$-th disk tangent to the $$$(j+1)$$$-th disk. Thus, $$$f$$$ is increasing sequence.

With this notation, the problem becomes selecting indices $$$1=i_1 \lt i_2 \lt \cdots \lt i_k$$$ such that

By induction, we may assume $$$i_{t+1}=f_{i_t}+1$$$, because choosing any smaller $$$i_{t+1}\le f_{i_t}+1$$$ cannot extend the reachable prefix beyond $$$f_{i_t}$$$, while choosing exactly $$$f_{i_t}+1$$$ is the earliest index that can potentially increase the farthest reachable position. Hence this greedy choice is optimal. Also, note that once we set $$$i_{t+1}=f_{i_t}+1$$$, there are no additional constraints on the choice of $$$r_{i_{t+1}}$$$ coming from earlier indices. In particular, any restriction on $$$r_{i_{t+1}}$$$ can only be imposed by $$$i_{t+1}+1$$$ (otherwise $$$f_{i_t}$$$ would not have been maximal by definition).

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
    ios::sync_with_stdio(false) , cin.tie(0);
    int tt;
    cin >> tt;
    while(tt--){
        int n;
        cin >> n;
        int x[n];
        for(int i = 0 ; i < n ; i++) cin >> x[i];
        int ans = n-1;
        int l = 0 , r = +1e9+1;
        int cur = 0;
        int fst = 1;
        for(int i = 1 ; i < n ; i++){
            cur = (x[i] - x[i-1]) - cur;
            if(i % 2 == fst % 2){
                r = min(r , cur);
                if(i < n-1) l = max(l , cur - (x[i+1] - x[i]));
            }
            else{
                l = max(l , -cur);
                if(i < n-1) r = min(r , (x[i+1] - x[i]) - cur);
            }
            if(l >= r){
                ans--;
                l = 0 , r = +1e9+1;
                cur = 0;
                fst = i+1;
            }
        }
        cout << ans << endl;
    }
}

// In the name of god
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
inline ll maxPower2Multiple(const ll &a) {return a&-a;}
inline ll prefixAnswer(const ll &a) {return maxPower2Multiple(a);}
inline bool isPerfect(const ll &a) {return a == maxPower2Multiple(a);}
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        ll l, r;
        cin >> l >> r;
        ll both = 1LL<<60;
        while((both&l) == (both&r) && both > 0) {
            if(both&l) l -= both, r -= both;
            both >>= 1;
        }
        if(l and isPerfect(l+r+1))
            cout << 2LL*min(prefixAnswer(l), prefixAnswer(r+1LL))-1LL << '\n';
        else if(l)
            cout << min(prefixAnswer(l), prefixAnswer(r+1LL))-1LL << '\n';
        else
            cout << prefixAnswer(r+1LL)-1LL << '\n';
    }
    return 0;
}

We solve the problem using dynamic programming.

A naive DP definition would be to let $$$dp[i][j]$$$ be the probability that a car, currently at cell $$$(i,j)$$$, eventually reaches the bottom-right corner of the grid. However, this state does not contain enough information to determine valid transitions, since the future movement of the car depends on the direction from which it entered the current cell and on the orientations of certain walls. Therefore, we need to add more information to our DP states.

We define the following DP states:

• $$$dp[i][j][0][0]$$$: the probability that the car reaches the bottom-right corner, given that it is currently at cell $$$(i,j)$$$, entered this cell from above, and the wall starting from the top-right corner of this cell is pointing downward.

• $$$dp[i][j][0][1]$$$: similar to $$$dp[i][j][0][0]$$$, but the wall starting from the top-right corner of the cell is \textbf{not} pointing downward.

• $$$dp[i][j][1][0]$$$: the probability that the car reaches the bottom-right corner, given that it is currently at cell $$$(i,j)$$$, entered this cell from the left, and the wall starting from the bottom-left corner of this cell is pointing to the right.

• $$$dp[i][j][1][1]$$$: similar to $$$dp[i][j][1][0]$$$, but the wall starting from the bottom-left corner of the cell is \textbf{not} pointing to the right.

We now describe how to compute the transitions.

Consider the state $$$dp[i][j][0][0]$$$. In this case, the car is at cell $$$(i,j)$$$, it entered from above, and the top-right wall is pointing downward. Therefore, the car cannot move to cell $$$(i,j+1)$$$ and must move to cell $$$(i+1,j)$$$.

After moving to $$$(i+1,j)$$$, there is a probability of $$$\frac{3}{16}$$$ that the top-right wall of the new cell is pointing downward, and a probability of $$$\frac{3}{8}$$$ that it is not. Thus, we obtain

Using similar arguments for the remaining states, we get the following transitions:

By computing these DP states in reverse order of $$$i$$$ and $$$j$$$, we can evaluate all states in $$$O(nm)$$$ time and obtain the final answer.

// In the name of god
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
constexpr int T = 10000; 
constexpr int N = 5000;
constexpr ll mod = 1000000007;
constexpr ll inv2 = (mod+1)>>1;
constexpr ll inv4 = inv2>>1;
constexpr ll inv8 = inv4>>1;
constexpr ll inv16 = (inv8+mod)>>1;
ll dp[2][N+1][2][2];
vector<pair<int, int>> query[N+1];
ll ans[T];
 
inline ll Pow(ll a, ll b) {
    ll res = 1LL;
    b %= mod-1;
    while(b) {
        if(b&1) res = (res*a)%mod;
        a = (a*a)%mod; 
        b >>= 1;
    }
    return res;
}
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    for(int n, m, i = 0; i < t; i++) {
        cin >> n >> m;
        query[n].push_back({m, i});
    }
	for(int i = 0; i <= N; i++)
		dp[N&1][i][0][0] = dp[N&1][i][0][1] = dp[N&1][i][1][0] = dp[N&1][i][1][1] = 1;
    for(int i = N-1; i >= 0; i--) {
        int q = i&1, p = 1-(i&1);
		dp[q][N][0][0] = dp[q][N][0][1] = dp[q][N][1][0] = dp[q][N][1][1] = 1;
        for(int j = N-1; j >= 0; j--) {
            dp[q][j][0][0] = (dp[p][j][0][0]*3LL*inv16+dp[p][j][0][1]*3LL*inv8)%mod;
            dp[q][j][0][1] = ((dp[p][j][0][0]*3LL*inv16+dp[p][j][0][1]*3LL*inv8)%mod+
                                dp[q][j+1][1][0]*inv16+dp[q][j+1][1][1]*5LL*inv16)%mod;
            dp[q][j][1][0] = (dp[q][j+1][1][0]*3LL*inv16+dp[q][j+1][1][1]*3LL*inv8)%mod;
            dp[q][j][1][1] = (dp[p][j][0][0]*inv4+dp[p][j][0][1]*inv2+dp[q][j+1][1][1]*3LL*inv16)%mod;
        }
        for(auto [m, qu]: query[N-i]) {
            ll P = (dp[q][N-m][0][0]*inv4+dp[q][N-m][0][1]*3LL*inv4)%mod;
            ans[qu] = (1LL-P+mod)*Pow(4LL, 1LL*(N-i+1)*(m+1))%mod;
        }
    }
    for(int i = 0; i < t; i++)
        cout << ans[i] << '\n';
    return 0;
}

Note that the $$$j$$$-th layer of DP states (that is, $$$dp[i][j]$$$ for all valid $$$i$$$) depends only on the $$$(j-1)$$$-th layer and the $$$j$$$-th layer itself. Moreover, all layers are computed using identical transition rules.

Let $$$dp[j]$$$ denote the vector consisting of all states $$$dp[i][j]$$$ for a fixed $$$j$$$. Then there exists a constant transition matrix $$$M$$$ such that

By computing $$$M^{\,m-1}$$$ and multiplying it by the initial vector $$$dp[1]$$$, we obtain $$$dp[m]$$$, from which the final answer can be extracted.

This can be done in $$$O(n^3 \log m)$$$ time using binary exponentiation.

// In the name of god
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
constexpr ll N = 50 + 1;
constexpr ll M = 1000000000000000LL;
constexpr ll mod = 1000000007;
constexpr ll inv2 = (mod+1)>>1;
constexpr ll inv4 = inv2>>1;
constexpr ll inv8 = inv4>>1;
constexpr ll inv16 = (inv8+mod)>>1;
ll n, m;
 
struct DP {
    ll dp[N][2][2][N][2][2] = {};
};
 
inline DP upd(const DP& l, const DP& r) {
    DP lr;
    for(int li = 0; li <= n; li++)
        for(int lh = 0; lh < 2; lh++)
            for(int lk = 0; lk < 2; lk++)
                for(int ri = li; ri <= n; ri++)
                    for(int rh = 0; rh < 2; rh++)
                        for(int rk = 0; rk < 2; rk++) 
                            for(int mi = li; mi <= ri; mi++) {
                                for(int mh = 0; mh < 2; mh++)
                                    for(int mk = 0; mk < 2; mk++)
                                        lr.dp[li][lh][lk][ri][rh][rk] += l.dp[li][lh][lk][mi][mh][mk]*r.dp[mi][mh][mk][ri][rh][rk];
                                lr.dp[li][lh][lk][ri][rh][rk] %= mod;
                            }
    return lr;
}
 
inline DP Identical() {
    DP I;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                I.dp[i][j][k][i][j][k] = 1;
    return I;
}
 
inline DP Pow(DP a, ll b) {
    DP res = Identical();
    while(b) {
        if(b&1) res = upd(res, a);
        a = upd(a, a);
        b >>= 1;
    }
    return res;
}
 
inline ll Pow(ll a, ll b) {
    ll res = 1LL;
    while(b) {
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return res;
}
 
int main() 
{
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        DP col;
    	col.dp[n][0][0][n][0][0] = col.dp[n][0][1][n][0][1] = col.dp[n][1][0][n][1][0] = col.dp[n][1][1][n][1][1] = 1;
        for(int i = (int)n-1; i >= 0; i--) {
            for(int j = i+1; j <= n; j++)
                for(int k = 0; k < 2; k++)
                    for(int l = 0; l < 2; l++) {
                        col.dp[i][0][1][j][k][l] = col.dp[i][0][0][j][k][l] = (col.dp[i+1][0][0][j][k][l]*3LL*inv16+col.dp[i+1][0][1][j][k][l]*3LL*inv8)%mod;
                        col.dp[i][1][1][j][k][l] = (col.dp[i+1][0][0][j][k][l]*inv4+col.dp[i+1][0][1][j][k][l]*inv2)%mod;
                    }
            col.dp[i][0][1][i][1][0] = inv16;
            col.dp[i][0][1][i][1][1] = 5LL*inv16%mod;
            col.dp[i][1][0][i][1][0] = 3LL*inv16%mod;
            col.dp[i][1][0][i][1][1] = 3LL*inv8%mod;
            col.dp[i][1][1][i][1][1] = 3LL*inv16; 
        }
        DP dpnm = Pow(col, m);
        ll ans = 0;
        for(int i = 0; i <= n; i++)
            for(int j = 0; j < 2; j++)
                for(int k = 0; k < 2; k++)
                    ans = (ans+dpnm.dp[0][0][0][i][j][k]*inv4+dpnm.dp[0][0][1][i][j][k]*3LL*inv4)%mod;
        cout << (1LL-ans+mod)*Pow(4LL, 1LL*(n+1LL)*(m+1LL))%mod << '\n';
    }
    return 0;
}

First, note that due to the structure of the queries, the array $$$a$$$ is always a palindrome.

Let $$$n$$$ be the current length of the array. Define $$$c_{i,m,k}$$$ as the number of subsequences of $$$a$$$ of length $$$m$$$ in which $$$a_i$$$ appears as the $$$k$$$-th element. Then the total sum of balances over all non-empty subsequences is equal to

By symmetry of the palindrome, we have

Using this symmetry, we can write

After rearranging terms, this implies that the total balance can be decomposed into two parts:

• the sum of all elements over all non-empty subsequences,
• plus the sum of averages of all non-empty subsequences.

The first part is straightforward. Each element $$$a_i$$$ appears in exactly $$$2^{n-1}$$$ non-empty subsequences, hence

For the second part, note that $$$a_i$$$ contributes to subsequences of length $$$k$$$ exactly $$$\binom{n-1}{k-1}$$$ times, and in such subsequences its coefficient in the average is $$$\frac{1}{k}$$$. Therefore,

It is easy to verify that

Hence the second part equals

Combining both parts, if we denote

the answer to a type $$$3$$$ query is

Thus, it is sufficient to maintain the values of $$$n$$$ and $$$S$$$. Since all computations are done modulo $$$10^9+7$$$, we maintain:

• $$$S \bmod (10^9+7)$$$,
• $$$n \bmod (10^9+7)$$$,
• $$$n \bmod (10^9+6)$$$ (for computing powers of $$$2$$$).

Updating $$$S$$$ and $$$n$$$ for queries of type $$$2$$$ is trivial. Updating $$$n$$$ for queries of type $$$1$$$ is also straightforward. The only non-trivial part is determining which element is removed in a type $$$1$$$ query in order to update $$$S$$$.

To handle this, consider a type $$$2$$$ query inserting a value $$$x$$$. There are two cases.

• If the current length of $$$a$$$ is odd ($$$2n+1$$$), after insertion the array becomes

The first time the middle element is removed, it is the original middle element of $$$a$$$. The next two times, the removed element is $$$x$$$. After that, the situation is equivalent to applying the same process to the array obtained by removing the middle element of $$$a$$$.

• If the current length of $$$a$$$ is even ($$$2n$$$), after insertion the array becomes

The first removed middle element is $$$x$$$, the second one is the original middle element of $$$a$$$ (namely $$$a_{n+1}$$$), and afterwards the situation again reduces to the same process on the array with its middle element removed.

Using this observation, we maintain a list of all values added by type $$$2$$$ queries, in order. For each such value we store an integer state in $$${0,1,2,3}$$$. When a new value $$$x$$$ is inserted:

• if the current length is odd, we assign it state $$$3$$$,
• otherwise, we assign it state $$$1$$$.

When processing a type $$$1$$$ query, we traverse this list from the end. For each element:

• if its state is $$$0$$$ or $$$1$$$, this element is the current middle element; we update its state to $$$(\text{state}+1)\bmod 4$$$ and return its value,
• otherwise, we only update its state to $$$(\text{state}+1)\bmod 4$$$ and continue.

This procedure finds the middle element in $$$O(1)$$$ amortized time per query.

Therefore, the overall time complexity of the solution is $$$O(q \log M)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
long long pw(long long a , long long b , long long mod){
  long long ret = 1;
  long long mul = a;
  while(b > 0){
	if(b&1)
	  ret = (ret * mul) % mod;
	mul = (mul * mul) % mod;
	b >>= 1;
  }
  return ret;
}
 
const int mod = 1e9 + 7;
 
int q;
 
int sum = 0 , lenm = 0 , lenm1 = 0 , len2 = 0;
 
vector<pair<int,int>> adds; // stay stay pass pass
 
int get(int id , int del = 1){
    assert(id >= 0);
    if(adds[id].second < 2){
        if(del) adds[id].second = (adds[id].second + 1) & 3;
        return adds[id].first;
    }
    else{
        if(del) adds[id].second = (adds[id].second + 1) & 3;
        return get(id-1 , del);
    }
}
 
int main() 
{
    ios::sync_with_stdio(false) , cin.tie(0);
    int tt;
    cin >> tt;
    while(tt--){
        cin >> q;
        sum = 0 , lenm = 0 , lenm1 = 0 , len2 = 0;
        adds.clear();
        while(q--){
            int tp;
            cin >> tp;
            if(tp == 1){
                sum = (sum - get(adds.size()-1 , 1) + mod) % mod;
                lenm = (lenm - 1 + mod) % mod;
                lenm1 = (lenm1 - 1 + (mod-1)) % (mod-1);
                len2 ^= 1;
            }
            else if(tp == 2){
                int x;
                cin >> x;
                if(len2 == 1) adds.push_back({x , 3});
                else adds.push_back({x , 1});
                sum = (sum + 1ll * (lenm + 1) * x) % mod;
                lenm = (2 * lenm + 1) % mod;
                lenm1 = (2 * lenm1 + 1) % (mod-1);
                len2 = 1;
            }
            else if(tp == 3){
                int ans = (pw(2 , (lenm1 - 1 + (mod-1)) % (mod-1) , mod) + 1ll * (pw(2 , lenm1 , mod) - 1) * pw(lenm , mod-2 , mod)) % mod;
                ans = (1ll * ans * sum) % mod;
                ans = (1ll * ans * pw(2 , mod-2 , mod)) % mod;
                cout << ans << endl;
            }
        }
    }
    return 0;
}

Step 1: reduce to independent series.

First, we can split the whole match into independent series $$$(a_i,b_i,c_i,[l_i,r_i])$$$. Since moves never mix two different games, by the Sprague-Grundy theorem we can compute the Grundy number contributed by each series and then solve the question.

Step 2: normalize one game.

Fix one game with upper bound $$$x$$$. Shift everything by $$$a$$$:

Because $$$a,b,c$$$ are an arithmetic progression, we have $$$c-a=2(b-a)$$$. Put $$$d=b-a$$$ and $$$y=x-a$$$, so the state starts as

Any move keeps the three numbers in an arithmetic progression (after reordering). In this normalized form, every legal move transforms $$$(0,\ d,\ 2d,\ y)$$$ into exactly one of the following forms: - $$$(d,\ 2d,\ 3d,\ y)$$$, - $$$(0,\ 2d,\ 4d,\ y)$$$, - $$$(d,\ \tfrac{3d}{2},\ 2d,\ y)$$$ when $$$d$$$ is even.

Step 3: parameters $$$(t,d)$$$ and then $$$(q,k)$$$.

It is convenient to measure the remaining room under $$$y$$$:

Then the game state is represented by $$$(t,d)$$$.

Write

and define

After this, the game depends only on $$$(q,k)$$$. We denote its Grundy number by $$$g(q,k)$$$.

Step 4: large ranges collapse to a few ranges of $$$q$$$.

In a fixed series, $$$d$$$ is fixed, hence $$$k$$$ and $$$D$$$ are fixed. As $$$x$$$ runs through $$$[l_i,r_i]$$$, the value $$$t=x-c_i$$$ runs through an interval $$$[L,R]$$$ where $$$L=l_i-c_i$$$ and $$$R=r_i-c_i$$$, and we look at

This $$$q$$$ stays constant on blocks of consecutive $$$D$$$ values, and the full blocks have length $$$D$$$. Since $$$D$$$ is odd, the contribution of the whole interval $$$t\in[L,R]$$$ can be reduced to:

• one consecutive interval of $$$q$$$ values corresponding to full blocks,

• at most two boundary blocks (the beginning and the end), treated separately.

Step 5: recursion for $$$g(q,k)$$$.

From the move description on $$$(q,k)$$$, we can write

Two facts make it easy to work with:

• the third term is never needed, so $$$g(q,k)=\mathrm{mex}\Big(g(q-2^k,k),\ g(q,k-1)\Big)$$$.

• for fixed $$$k$$$, the sequence $$$g(0,k),g(1,k),\ldots$$$ is periodic with period $$$2^{k+1}$$$.

Using the first fact, we get a simple split:

• if $$$q \lt 2^k$$$, then $$$g(q-2^k,k)$$$ does not exist, so $$$g(q,k)=\mathrm{mex}\Big({g(q,k-1)}\Big)$$$.
• if $$$q\ge 2^k$$$, then $$$g(q,k)=\mathrm{mex}\Big({g(q,k-1),\ g(q-2^k,k)}\Big)$$$.

Step 6: reduce interval XOR to prefix XOR.

In each series we need

Define the prefix XOR

Then

Step 7: compute $$$f(u,k)$$$ as a small tuple.

We save $$$f(u,k)$$$ as a tuple

where $$$p_i=1$$$ means the value $$$i$$$ has an odd contribution in

In other words, $$$p_i$$$ tells whether $$$i$$$ appears an odd number of times among $$$g(0,k),\ldots,g(u,k)$$$.

We first precompute the XOR over one full period

Since the period is $$$2^{k+1}$$$, two full consecutive periods cancel in XOR, so the XOR over length $$$2^{k+2}$$$ becomes $$$(0,0,0)$$$. Therefore, for a general $$$u$$$ we reduce it to the remainder inside a single period, and then compute it by recursion on $$$k$$$ from the formulas in Step 5. This makes computing $$$f(u,k)$$$ fast, in $$$O(k)=O(\log u)$$$ time.

// In the name of God
#include <iostream>
using namespace std;
#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
 
inline ll lg2(ll x){return 63 - __builtin_clzll(x);}
constexpr inline ll period(ll k) {return 1LL<<(k+1);}
constexpr inline ll half_period(ll k) {return 1LL<<k;}
inline ll equivalent(ll x, ll k) {return x & (period(k)-1);}
inline bool count_period_parity(ll x, ll k) {return (x >> (k+1)) & 1;}
 
struct node {
    int u;
    node(bool zero, bool one, bool two) {
        u = ((int) zero << 0) + ((int) one << 1) + ((int) two << 2);
    }
    node(int x) {
        u = x;
    }
    bool has(int i) const {return u & (1<<i);}
    node Mex() const {
        return node(has(1) ^ has(2), has(0), false);
    }
    node MexMex() const {
        return node(false, has(2), has(0) ^ has(1));
    }
    node operator^(const node other) const {
        return node(u ^ other.u);
    }
    void operator^=(const node other) {
        u ^= other.u;
    }
    int get() const {
        return (u >> 1);
    }
};
 
const node full_period(true, true, false);
const node full_period_mex = full_period.Mex();
const node zero_node(false, false, false);
const node zero(true, false, false), one(false, true, false), two(false, false, true);
 
node grundy(ll x, ll k) {
    if(k)
        return equivalent(x, k) < half_period(k)? grundy(x, k-1).Mex() : grundy(x, k-1).MexMex();
    return x&1? one : zero;
}
 
node prefix_grundy(ll r, ll k) {
    node period_effect = (count_period_parity(r, k)? full_period : zero_node);
    r = equivalent(r, k);
    if(k == 0)
        return (r? full_period : zero) ^ period_effect;
    if(r < half_period(k))
        return prefix_grundy(r, k-1).Mex() ^ period_effect;
    return prefix_grundy(r - half_period(k), k-1).MexMex() ^ full_period_mex ^ period_effect;
}
 
inline node grundy(ll l, ll r, ll k) {
    return (l? prefix_grundy(l-1, k) : zero_node) ^ prefix_grundy(r, k);
}
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        node ans(0);
        for(ll a, b, c, l, r, lp, rp, d, k, i = 0; i < n; i++) {
            cin >> a >> b >> c >> l >> r;
            b -= a, c -= a, l -= a, r -= a, a = 0;
            l -= c, r -= c;
            k = lg2(b & -b), d = b >> k;
            if(l / d == r / d) {
                if((r - l + 1) & 1)
                    ans ^= grundy(l / d, k);
            } else {
                lp = (l+d-1) / d, rp = r / d;
                if(lp < rp) ans ^= grundy(lp, rp-1, k);
                if((lp*d-l)&1) ans ^= grundy(l / d, k);
                if((r-rp*d+1)&1) ans ^= grundy(r / d, k);
            }
        }
        cout << (ans.get()? "Bug" : "Feature") << '\n';
    }
    return 0;
}
// Thank God

Step 1: Game Transformation.

Convert each game with $$$a_i \lt b_i \lt c_i \le x$$$ to analyze $$$0 \lt 1 \lt 2 \le x'$$$ where:

The interval $$$[l_i, r_i]$$$ transforms to

Note that each $$$x' \in [L_i, R_i]$$$ corresponds to multiple original $$$x$$$ values (the number of originals can change near the interval endpoints). From state $$$x'$$$, a player can move either to $$$x'-1$$$ or to $$$\left\lfloor \frac{x'}{2} \right\rfloor$$$. The game ends when $$$x'=2$$$, and the player who makes the last move wins.

Step 2: Grundy Numbers.

Define $$$g(x)$$$ for state $$$0 \lt 1 \lt 2 \le x$$$:

• Base cases:

• Recursive rule ($$$x \ge 4$$$):

• Key properties (proven by induction):

  • $$$g(x) = 0$$$ $$$\iff$$$ $$$x$$$ has odd trailing zeros in binary
  • Non-zero $$$g(x)$$$ alternate $$$1 \leftrightarrow 2$$$ sequentially

Step 3: Counting Grundy Values.

For any interval $$$[l, r]$$$:

• Count numbers with $$$g(x) = 0$$$:

  • Define $$$C(y) =$$$ count of $$${x \le y \mid g(x) = 0}$$$
  • Loop through bits to compute $$$C(y)$$$ in $$$O(\log y)$$$
  • Zeros in $$$[l, r]$$$: $$$C(r) - C(l-1)$$$

• Count $$$1$$$'s and $$$2$$$'s similarly using $$$C(y)$$$ and alternation of $$$1$$$ and $$$2$$$.

Step 4: Final Computation.

For each transformed interval $$$[L_i, R_i]$$$:

• Compute XOR of all $$$g(x)$$$ in $$$[L_i, R_i]$$$
• Aggregate XOR across all $$$n$$$ queries
• Total XOR $$$\neq 0 \implies$$$ Bug wins; else Feature wins

// In the name of God
#include <iostream>
using namespace std;
typedef long long ll;
 
inline ll count_zeros(ll x) {
    int u = (x&2)>>1;
    ll cnt = u;
    while (x>>=2) {
        u = (x&2)>>1;
        cnt += x+u;
    }
    return cnt;
}
 
// normal grundy function
/*
inline int grundy(ll x) {
    if((__builtin_ctzll(x)&1) == 1) return 0;
    return 1+((x-count_zeros(x))&1);
}
*/
 
// magical function
inline int grundy(ll x) {
    if((__builtin_ctzll(x)&1) == 1) return 0;
    return 1+(__builtin_popcountll(x)&1);
}
 
inline int grundy(ll l, ll r) {
    ll zel = count_zeros(l-1), zer = count_zeros(r);
    ll onl = (l-1-zel)/2, onr = (r-zer)/2;
    ll twl = (l-2-zel)/2, twr = (r-1-zer)/2;
    return ((onr-onl)&1)^(((twr-twl)&1)<<1);
}
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n, ans;
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        ans = 0;
        for(ll a, b, c, l, r, lp, rp, i = 0; i < n; i++) {
            cin >> a >> b >> c >> l >> r;
            b -= a, c -= a, l -= a, r -= a, a = 0;
            if(l / b == r / b) {
                if((r - l + 1)&1)
                    ans ^= grundy(l / b);
            } else {
                lp = (l+b-1)/b, rp = r/b;
                if(b&1) ans ^= grundy(lp, rp-1);
                if((lp*b-l)&1)ans ^= grundy(l/b);
                if((r-rp*b+1)&1)ans ^= grundy(rp);
            }
        }
        cout << (ans?"Bug":"Feature") << '\n';
    }
    return 0;
}