#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int n, res, ta[2], tb[2];
string a, b, c, d;
void init_global()
{
}
void init_local()
{
    cin >> n >> a >> b >> c >> d;
    ta[0] = ta[1] = tb[0] = tb[1] = res = 0;
}
void run()
{
    for (int i = 0; i < n and c[i] == '1'; i++)
    {
        ta[a[i] - '0']++;
    }
    for (int i = 0; i < n and d[i] == '1'; i++)
    {
        tb[b[i] - '0']++;
    }
    for (int i = 0; i < n; i++)
    {
        if (!ta[0] and !ta[1])
        {
            if (c[i] == '1')
            {
                for (int j = i; j < n and c[j] == '1'; j++)
                {
                    ta[a[j] - '0']++;
                }
            }
            else
                ta[a[i] - '0']++;
        }
        if (!tb[0] and !tb[1])
        {
            if (d[i] == '1')
            {
                for (int j = i; j < n and d[j] == '1'; j++)
                {
                    tb[b[j] - '0']++;
                }
            }
            else
                tb[b[i] - '0']++;
        }
        if (ta[0] and tb[0])
        {
            res++, ta[0]--, tb[0]--;
            continue;
        }
        if (ta[1] and tb[1])
        {
            res++, ta[1]--, tb[1]--;
            continue;
        }
        if (ta[0])
        {
            ta[0]--, tb[1]--;
            continue;
        }
        ta[1]--, tb[0]--;
    }
    printf("%d\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    init_global();
    while (T--)
    {
        init_local();
        run();
    }
}

$$$x\oplus x=0$$$

$$$x\oplus x\oplus x=x$$$

The answer depends on parity.

If $$$m$$$ is even, then the result of the formula is always $$$0$$$. Otherwise, it can be any positive integer, because all the elements in the sequence $$$a$$$ is positive.

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
void run()
{
    scanf("%d%d", &n, &m);
    puts((m & 1) ^ (!n) ? "Yes" : "No");
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

Lexicographically smallest.

If you can keep the current character a, then do it.

Since a is the lexicographically smallest character, then it's always optimal to insert a instead of others.

Use # in the string $$$b$$$ greedily.

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int n, m, cts, idx;
string s, t;
int main()
{
    cin >> n >> m >> s >> t;
    for (int i = 0; i < n; i++)
    {
        cts += (t[i] == '#');
    }
    for (auto &i : s)
    {
        if (i != '#')
            continue;
        i = idx + 'a';
        if (cts >= 25 - idx)
        {
            cts -= 25 - idx;
            idx = 0;
            continue;
        }
        idx++;
        idx = (idx == 26 ? 0 : idx);
    }
    cout << s << '\n';
}

Denote $$$c_{i,x}$$$ as the total number moments when exactly $$$x$$$ roses are blooming when or before the moment $$$i$$$.

If we have a virtual rose which blooms in the range $$$[1,i]$$$, then how to denote the number the answer will increase when we move that flower's blooming time to an infinitely faraway place?

The answer of the question raised in hint $$$1$$$ is $$$\sum_{j=2}^\infty c_{i,j}+c_{i,2}$$$.

Prefix sum.

We can calculate the sequence $$$c$$$ at each turning point. We call a moment a turning point when a rose blooms or fades at this moment.

Then, calculate value in hint $$$2$$$ for each turning point.

It can be proved that moving $$$[x,y]$$$ away is equivalent to move $$$[1,y]$$$ away then move $$$[1,x-1]$$$ back.

So use prefix sum to calculate answer for each rose.

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
int n, m, x, idx, cur;
ll mx, res[4], p2[N];
using pii = pair<int, int>;
pii dst[N << 2];
bool mp[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        dst[++idx] = {x, i};
        dst[++idx] = {x + m, i};
    }
    sort(dst + 1, dst + idx + 1);
    for (int i = 1; i <= idx; i++)
    {
        auto &[a, b] = dst[i];
        res[min(cur, 3)] += a - dst[i - 1].first;
        if (!mp[b])
        {
            cur++;
            mp[b] = true;
            p2[b] = res[2] * 2 + res[3];
            continue;
        }
        mx = max(mx, res[2] * 2 + res[3] - p2[b]);
        cur--;
    }
    printf("%lld\n", res[1] + mx);
}

It's optimal to make adjacent characters different.

If two adjacent characters are same, then they only add the total time by $$$1$$$ seconds. If we insert a different character between them, the $$$1$$$ will turn into two $$$2$$$ s, which add the total time by $$$2$$$ seconds. Since you can only insert $$$1$$$ character in it, it's the optimal insertion method.

If that same adjacent pair doesn't exist, we can still add a different character between an arbitrary pair, then it will add the total time by $$$2$$$ seconds.

Time complexity: $$$O(n)$$$.

# include <iostream>
# include <string>
using namespace std;
const int N = 1e5 + 10;
string s;
int n, tp;
void run()
{
    cin >> s;
    n = s.size();
    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            tp = 0;
            while (s[i] == tp + 'a' or s[i + 1] == tp + 'a')
                tp++;
            s.insert(s.begin() + i + 1, tp + 'a');
            break;
        }
    }
    if (n == s.size())
    {
        if (s.back() == 'z')
            s.push_back('a');
        else
            s.push_back('z');
    }
    cout << s << '\n';
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

The given grid contains at most $$$1$$$ connected region.

There are only $$$2$$$ rows in this grid.

Imagine a trap.

Since there are only $$$2$$$ rows in the grid, so all the cell unblocked will have at most $$$3$$$ adjacent unblocked cells.

In order to make $$$3$$$ connected components, we should seperate these $$$3$$$ adjacent unblocked cells into different connected components. So how to do that?

Imagine a "trap" like this:

...
x.x

We can see that if we block the middle cell on the upper row, it will separate into $$$3$$$ connected components like this:

.x.
x.x

It's the only way to separate legally.

Time complexity: $$$O(n)$$$.

# include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, res;
char ch[2][N];
void run()
{
    cin >> n;
    cin >> ch[0];
    cin >> ch[1];
    res = 0;
    for (int j = 0; j < 2; j++)
    {
        for (int i = 1; i < n - 1; i++)
        {
            if (ch[j][i] == '.')
            {
                res += (ch[j ^ 1][i - 1] == 'x' and
                        ch[j ^ 1][i + 1] == 'x' and
                        ch[j ^ 1][i] == '.' and
                        ch[j][i - 1] == '.' and
                        ch[j][i + 1] == '.');
            }
        }
    }
    printf("%d\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

It's OK to construct it greedily.

For a RBS $$$s$$$, we define its layer value $$$l$$$ as this:

"Layer" stands for "the layer number of brackets pair".

And its prefix value $$$p$$$ is this:

Then, it's required to satisfy $$$p_n=0$$$ and $$$\min(p)=0$$$.

If $$$\min(p) \lt 0$$$, it'll no longer be a RBS.

Then, we define the require value $$$r$$$ as this:

Note that this $$$s$$$ may contains "_".

A legal construction of $$$s$$$ satisfies $$$p_i\ge r_i$$$.

Then, for each position $$$i$$$, if inserting an ")" may make $$$p_i \lt r_i$$$, then insert an "(" instead.

It can be proved that this is the optimal construction method.

Time complexity: $$$O(n)$$$.

Fun fact: I got $$$2$$$ runtime errors during the contest because I set the array size to $$$10^5$$$ while the problem requires $$$2\times 10^5$$$.

# include <iostream>
# include <string>
# include <stack>
using namespace std;
const int N = 2e5 + 10;
string s;
int n, ts[N];
stack<int> stk;
using ll = long long;
ll res;
void run()
{
    cin >> n >> s;
    ts[n] = res = 0;
    for (int i = n - 1; ~i; i--)
    {
        if (s[i] != ')')
        {
            ts[i] = max(0, ts[i + 1] - 1);
        }
        else
        {
            ts[i] = ts[i + 1] + 1;
        }
    }
    for (int i = 0, tmp = 0; i < n; i++)
    {
        if (s[i] == '(')
        {
            tmp++;
            stk.push(i);
            continue;
        }
        if (s[i] == ')')
        {
            tmp--;
            res += i - stk.top();
            stk.pop();
            continue;
        }
        if (tmp - 1 < ts[i + 1] or !stk.size())
        {
            tmp++;
            s[i] = '(';
            stk.push(i);
            continue;
        }
        s[i] = ')';
        tmp--;
        res += i - stk.top();
        stk.pop();
    }
    printf("%lld\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

After each operation, the values on all vertices should be non-negative.

Maximize the minimum.

With the formula in hint $$$3$$$, we can quickly realize that we should make $$$\min_{i=2}^n a_i$$$ as big as possible. So how to do that?

Well, the operation that the problem provides is able to add a vertex by subtracting the rest of its subtree. So, in order to maximize the minimum, we can simply make them closer.

If the value of a vertex is already higher than the minimum value of its subtree, we can't get them closer.

Apply a depth-first search to do that.

Time complexity: $$$O(n)$$$.

# include <iostream>
# include <vector>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], cont[N];
vector<int> road[N];
void dfs(int x, int f)
{
    cont[x] = 0x3f3f3f3f;
    for (auto &i : road[x])
    {
        if (i == f)
            continue;
        dfs(i, x);
        cont[x] = min(cont[x], cont[i]);
    }
    if (x == 1)
        return;
    if (cont[x] == 0x3f3f3f3f)
        cont[x] = a[x];
    else if (cont[x] > a[x])
    {
        cont[x] = (cont[x] + a[x]) / 2;
    }
}
void run()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
        road[i].clear();
    }
    for (int i = 2, x; i <= n; i++)
    {
        scanf("%d", &x);
        road[x].push_back(i);
    }
    dfs(1, 0);
    printf("%d\n", a[1] + cont[1]);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

What will happen when we increase $$$k$$$?

The number of the monsters fleeing won't be higher. Why?

Because, a higher $$$k$$$ means the lower expectation level.

Binary search.

With the conclusion in hint $$$2$$$, we can calculate the Firmness requirement $$$f$$$ which satisfies when $$$k\ge f_i$$$, the $$$i$$$-th monster always fights with Monocarp.

If $$$i$$$-th monster fight with Monocarp with a parameter of $$$k$$$, then it must satisfy that

Because when Monocarp already fought $$$a_ik$$$ or more monsters before, then his level will be higher than $$$a_i$$$, and the $$$i$$$-th monster will flee.

The formula above is easy to calculate with a BIT.

After calculating the sequence $$$f$$$, we can answer all the queries in a time complexity of $$$O(1)$$$.

Time complexity: $$$O(n\log n\log (\max a_i)+q)$$$.

Fun fact: I applied an unnecessary sort on the queries. However, it still has a good speed.

# include <iostream>
# include <vector>
# include <tuple>
# include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, q, tr[N], idx = 1, l, r, mid;
vector<int> dst[N];
inline void update(int x, int v)
{
    while (x < N)
    {
        tr[x] += v;
        x += (x & -x);
    }
}
inline int query(int x)
{
    int res = 0;
    while (x)
        res += tr[x], x -= (x & -x);
    return res;
}
inline bool check(int x, int v)
{
    return 1ll * a[x] * v <= query(v);
}
using t3i = tuple<int, int, int>;
t3i qry[N];
bool res[N];
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= q; i++)
    {
        auto &[x, k, id] = qry[i];
        scanf("%d%d", &x, &k);
        id = i;
    }
    sort(qry + 1, qry + q + 1);
    for (int i = 1; i <= q; i++)
    {
        auto &[x, k, id] = qry[i];
        while (idx < x)
        {
            l = 1, r = n;
            while (l < r)
            {
                mid = (l + r) >> 1;
                if (check(idx, mid))
                    l = mid + 1;
                else
                    r = mid;
            }
            update(l, 1);
            idx++;
        }
        res[id] = !check(x, k);
    }
    for (int i = 1; i <= q; i++)
    {
        puts(res[i] ? "YES" : "NO");
    }
}

#include <iostream>
#include <tuple>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, q, tr[N], idx = 1, l, r, mid, req[N];
inline void update(int x, int v)
{
    while (x < N)
    {
        tr[x] += v;
        x += (x & -x);
    }
}
inline int query(int x)
{
    int res = 0;
    while (x)
        res += tr[x], x -= (x & -x);
    return res;
}
inline bool check(int x, int v)
{
    return 1ll * a[x] * v <= query(v);
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= n; i++)
    {
        l = 1, r = n;
        while (l < r)
        {
            mid = (l + r) >> 1;
            if (check(i, mid))
                l = mid + 1;
            else
                r = mid;
        }
        update(l, 1);
        req[i] = l;
    }
    for (int i = 1, x, k; i <= q; i++)
    {
        scanf("%d%d", &x, &k);
        puts(k < req[x] ? "NO" : "YES");
    }
}

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], b[N];
void run()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        scanf("%d", b + i);
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = (b[i] | b[i - 1]);
    }
    for (int i = 1; i < n; i++)
    {
        // printf("%d %d\n", (a[i] & a[i + 1]), b[i]);
        if ((a[i] & a[i + 1]) != b[i])
            return puts("-1"), void();
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d%c", a[i], " \n"[i == n]);
    }
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

In fact, we get $$$b_1$$$ to $$$b_{n-1}$$$ from input. However, the code above used $$$b_n$$$ to calculate $$$a_n$$$, and it's not given. If the former $$$n$$$ is bigger than the current $$$n$$$, the $$$b_n$$$ won't be zero, and the program will output a wrong $$$a_n$$$. To resolve this, just set $$$b_n$$$ to zero before the construction.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10, E = 1e9, idx = 48;
int prec[N], n, q, a[N], b[N], rs;
bool fl;
vector<int> vec;
bool check(int p, int x, int y, int z)
{
    vec.clear();
    for (int i = 0; i < 6; i++)
    {
        if (i != x and i != y and i != z)
            vec.push_back(p + i);
    }
    return b[p + x] + b[p + y] > b[p + z] and b[vec[0]] + b[vec[1]] > b[vec[2]];
}
void run()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
    }
    for (int t = 1, x, y; t <= q; t++)
    {
        scanf("%d%d", &x, &y);
        if (y - x + 1 >= idx)
        {
            puts("YES");
            continue;
        }
        for (int j = x; j <= y; j++)
        {
            b[j - x] = a[j];
        }
        sort(b, b + y - x + 1);
        fl = false;
        for (int i = 0; i < y - x - 4; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                for (int k = j + 1; k < 6; k++)
                {
                    for (int l = k + 1; l < 6; l++)
                    {
                        fl |= check(i, j, k, l);
                        if (fl or b[i + j] + b[i + k] <= b[i + l])
                            break;
                    }
                    if (fl)
                        break;
                }
                if (fl)
                    break;
            }
            if (fl)
                break;
        }
        if (fl)
        {
            puts("YES");
            continue;
        }
        rs = 0;
        for (int j = 2; j < y - x + 1; j++)
        {
            if (b[j] < b[j - 1] + b[j - 2])
                rs++, j += 2;
        }
        puts(rs > 1 ? "YES" : "NO");
    }
}
int main()
{
    int T = 1;
    // scanf("%d", &T);
    while (T--)
        run();
}

#include <iostream>
using namespace std;
const int N = 5e4 + 10;
int n, m;
void run()
{
    scanf("%d%d", &n, &m);
    if (n == 1 and m == 1)
    {
        scanf("%*d");
        puts("-1");
        return;
    }
    for (int i = 1, x; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &x);
            printf("%d%c", x % (n * m) + 1, " \n"[j == m]);
        }
    }
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int n;
string s, t;
void run()
{
    cin >> n >> s >> t;
    puts(s.find('1') <= t.find('1') ? "YES" : "NO");
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
int n, k, r;
ll a[N], dp[N], cur, res;
void run()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", a + i);
    }
    memset(dp + 2, 0, n << 3);
    cur = 0;
    r = 1;
    for (int i = 1; i <= n; i++)
    {
        cur -= a[i - 1];
        while (r <= n and cur <= k)
            cur += a[r], r++;
        if (cur <= k)
            continue;
        dp[r] += dp[i] + 1;
    }
    res = n;
    res *= n + 1;
    res /= 2;
    for (int i = 2; i <= n + 1; i++)
    {
        res -= dp[i];
    }
    printf("%lld\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

#include <iostream>
#include <list>
#include <cstring>
using namespace std;
const int N = 2e3 + 10;
int n, a[N], f[N], v[N], p;
bool fl;
using pii = pair<int, int>;
list<pii> ret;
inline int find(int x)
{
    return x == f[x] ? x : f[x] = find(f[x]);
}
inline void merge(int x, int y)
{
    f[find(y)] = find(x);
}
void run()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
        scanf("%d", a + i);
    }
    ret.clear();
    for (int i = n - 1; i; i--)
    {
        memset(v, 0, i << 2);
        fl = false;
        for (int j = 1; j <= n; j++)
        {
            p = a[j] % i;
            if (!v[p])
            {
                v[p] = j;
                continue;
            }
            if (find(j) == find(v[p]))
                continue;
            merge(j, v[p]);
            ret.push_front({j, v[p]});
            fl = true;
            break;
        }
        if (!fl)
            return puts("NO"), void();
    }
    puts("YES");
    for (auto &[tx, ty] : ret)
        printf("%d %d\n", tx, ty);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], t, res;
void run()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
        for (int j = 1; j < a[i]; j++)
            scanf("%*d");
    }
    sort(a + 1, a + n + 1);
    t = 1;
    for (; t < a[n]; t = t * 2 + 1)
        ;
    res = 0;
    for (int i = n; i; i--)
    {
        while ((t > a[i]) or (t & res))
            t--;
        res |= t;
    }
    printf("%d\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

#include<tuple>
#include<iostream>
#include<climits>

namespace RedshiftShine{
    
    using ll=unsigned long long;
    const ll ulmx=ULLONG_MAX;
    const ll shift=64;

    ll min(ll x,ll y){
        return x<y?x:y;
    }

    ll max(ll x,ll y){
        return x>y?x:y;
    }

    bool detect_overflow_add(ll x,ll y){
        return x+y<min(x,y);
    }

    bool detect_overflow_minus(ll x,ll y){
        return x<y;
    }

    class Custom_Unsigned_int128{
        private:
        ll higherInt,lowerInt;
        public:
        Custom_Unsigned_int128(){}

        template<typename _Tp>
        Custom_Unsigned_int128(_Tp x):
        higherInt(0),
        lowerInt(x){}

        template<typename _Tp>
        Custom_Unsigned_int128(_Tp x,_Tp y):
        higherInt(x),
        lowerInt(y){}
        
        Custom_Unsigned_int128
        (const Custom_Unsigned_int128& ele):
        higherInt(ele.higherInt),
        lowerInt(ele.lowerInt){}

        std::pair<ll,ll>
        base_access(){
            return std::pair<ll,ll>{
                higherInt,
                lowerInt
            };
        }

        Custom_Unsigned_int128&
        operator=(const Custom_Unsigned_int128& x){
            higherInt=x.higherInt,
            lowerInt=x.lowerInt;
            return *this;
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator=(const _Tp& x){
            *this=Custom_Unsigned_int128
            (
                0,x
            );
            return *this;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator+(const _Tp& x){
            return Custom_Unsigned_int128
            (
                higherInt+
                detect_overflow_add(lowerInt,x),
                lowerInt+x
            );
        }

        template<typename _Tp>
        friend Custom_Unsigned_int128
        operator+(const _Tp& x,const Custom_Unsigned_int128& ele){
            return Custom_Unsigned_int128
            (
                ele.higherInt+
                detect_overflow_add(ele.lowerInt,x),
                ele.lowerInt+x
            );
        }

        Custom_Unsigned_int128
        operator+(const Custom_Unsigned_int128& x){
            return Custom_Unsigned_int128
            (
                higherInt+x.higherInt+
                detect_overflow_add(lowerInt,x.lowerInt),
                lowerInt+x.lowerInt
            );
        }

        template<typename _Tp>
        bool
        operator==(const _Tp& x)const{
            return 
            (
                !higherInt and 
                lowerInt==x
            );
        }

        template<typename _Tp>
        friend bool
        operator==(const _Tp& x,const Custom_Unsigned_int128& ele){
            return ele==x;
        }

        bool
        operator==(const Custom_Unsigned_int128& x)const{
            return 
            (
                higherInt==x.higherInt and 
                lowerInt==x.lowerInt
            );
        }

        template<typename _Tp>
        bool
        operator!=(const _Tp& x)const{
            return !(*this==x);
        }

        template<typename _Tp>
        friend bool
        operator!=(const _Tp& x,const Custom_Unsigned_int128& ele){
            return !(ele==x);
        }

        template<typename _Tp>
        bool
        operator<(const _Tp& x)const{
            return 
            (
                !higherInt and 
                lowerInt<x
            );
        }

        template<typename _Tp>
        friend bool
        operator<(const _Tp& x,const Custom_Unsigned_int128& ele){
            return 
            (
                ele.higherInt or 
                ele.lowerInt>x
            );
        }

        bool
        operator<(const Custom_Unsigned_int128& x)const{
            
            return 
            (
                higherInt<x.higherInt or 
                (
                    higherInt==x.higherInt and 
                    lowerInt<x.lowerInt
                )
            );
        }

        template<typename _Tp>
        bool
        operator<=(const _Tp& x)const{
            return 
            (
                *this<x or 
                *this==x
            );
        }

        template<typename _Tp>
        friend bool
        operator<=(const _Tp& x,const Custom_Unsigned_int128& ele){
            return ele<=x;
        }

        bool
        operator<=(const Custom_Unsigned_int128& x)const{
            return 
            (
                *this<x or 
                *this==x
            );
        }

        template<typename _Tp>
        bool
        operator>(const _Tp& x)const{
            return 
            !(
                *this<=x
            );
        }

        template<typename _Tp>
        friend bool
        operator>(const _Tp& x,const Custom_Unsigned_int128& ele){
            return !(ele<=x);
        }

        bool
        operator>(const Custom_Unsigned_int128& x)const{
            return 
            !(
                *this<=x
            );
        }

        template<typename _Tp>
        bool
        operator>=(const _Tp& x)const{
            return 
            !(
                *this<x
            );
        }

        template<typename _Tp>
        friend bool
        operator>=(const _Tp& x,const Custom_Unsigned_int128& ele){
            return !(ele<x);
        }

        bool
        operator>=(const Custom_Unsigned_int128& x)const{
            return 
            !(
                *this<x
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator+=(const _Tp& x){
            return *this=*this+x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator-(const _Tp& x)const{
            return Custom_Unsigned_int128
            (
                higherInt-
                detect_overflow_minus(lowerInt,x),
                lowerInt-x
            );
        }

        Custom_Unsigned_int128
        operator-(const Custom_Unsigned_int128& x)const{
            return Custom_Unsigned_int128
            (
                higherInt-x.higherInt-
                detect_overflow_minus(lowerInt,x.lowerInt),
                lowerInt-x.lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator-=(const _Tp& x){
            return *this=*this-x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator&(const _Tp& x){
            return Custom_Unsigned_int128
            (
                0ull,
                lowerInt&x
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        friend operator&(const _Tp& x,const Custom_Unsigned_int128& ele){
            return Custom_Unsigned_int128
            (
                ele.higherInt,
                ele.lowerInt&x
            );
        }

        Custom_Unsigned_int128
        operator&(const Custom_Unsigned_int128& x){
            return Custom_Unsigned_int128
            (
                higherInt&x.higherInt,
                lowerInt&x.lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator&=(const _Tp& x){
            return *this=*this&x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator|(const _Tp& x){
            return Custom_Unsigned_int128
            (
                higherInt,
                lowerInt|x
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        friend operator|(const _Tp& x,const Custom_Unsigned_int128& ele){
            return Custom_Unsigned_int128
            (
                ele.higherInt,
                ele.lowerInt|x
            );
        }

        Custom_Unsigned_int128
        operator|(const Custom_Unsigned_int128& x){
            return Custom_Unsigned_int128
            (
                higherInt|x.higherInt,
                lowerInt|x.lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator|=(const _Tp& x){
            return *this=*this|x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator^(const _Tp& x){
            return Custom_Unsigned_int128
            (
                higherInt,
                lowerInt^x
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        friend operator^(const _Tp& x,const Custom_Unsigned_int128& ele){
            return Custom_Unsigned_int128
            (
                ele.higherInt,
                ele.lowerInt^x
            );
        }

        Custom_Unsigned_int128
        operator^(const Custom_Unsigned_int128& x){
            return Custom_Unsigned_int128
            (
                higherInt^x.higherInt,
                lowerInt^x.lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator^=(const _Tp& x){
            return *this=*this^x;
        }

        Custom_Unsigned_int128
        operator~(){
            return Custom_Unsigned_int128(
                ~higherInt,
                ~lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator<<(const _Tp& x){
            return x<shift?
            Custom_Unsigned_int128(
                higherInt<<x|(lowerInt>>(shift-x)),
                lowerInt<<x
            ):
            Custom_Unsigned_int128(
                lowerInt<<(x-shift),
                0ull
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator<<=(const _Tp& x){
            return *this=*this<<x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator>>(const _Tp& x){
            return x<shift?
            Custom_Unsigned_int128(
                higherInt>>x,
                lowerInt>>x|(higherInt<<(shift-x))
            ):
            Custom_Unsigned_int128(
                0ull,
                higherInt>>(x-shift)
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator>>=(const _Tp& x){
            return *this=*this>>x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator*(const _Tp& x)const{
            Custom_Unsigned_int128 ret(0),pr(*this);
            _Tp tm(x);
            for(;tm;tm>>=1){
                if(tm&1)ret+=pr;
                pr<<=1;
            }
            return ret;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        friend operator*(const _Tp& x,const Custom_Unsigned_int128& ele){
            Custom_Unsigned_int128 ret(0),pr(ele);
            _Tp tm(x);
            for(;tm!=0;tm>>=1){
                if((tm&1)!=0)ret+=pr;
                pr+=pr;
            }
            return ret;
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator*=(const _Tp& x){
            return *this=*this*x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator/(const _Tp& x)const{
            Custom_Unsigned_int128 ret(0),pr(x),trm(1),ts(*this);
            while((!(pr.higherInt>>(shift-1))) and pr<=ts){
                
                pr<<=1,trm<<=1;
                
            }
            pr>>=1,trm>>=1;
            for(;;pr>>=1,trm>>=1){
                
                // if(ts<pr)continue;
                
                while(ts>=pr){
                    ts-=pr,ret+=trm;
                    
                }
                if((pr&1)!=0)break;
            }
            return ret;
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator/=(const _Tp& x){
            return *this=*this/x;
        }

        template<typename _Tp>
        _Tp
        operator%(const _Tp& x)const{
            return (*this-*this/x*x).lowerInt;
        }

        Custom_Unsigned_int128
        operator%(const Custom_Unsigned_int128& x)const{
            return *this-*this/x*x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator%=(const _Tp& x){
            return *this=*this%x;
        }

    };

}

void print(RedshiftShine::Custom_Unsigned_int128 v){
    if(v==0)return;
    print(v/10);
    putchar(v%10+'0');
}

void test(){
    RedshiftShine::Custom_Unsigned_int128 ci(0,1),cz(0,1);
    print(ci),putchar(' ');
    for(int i=128;i;i--){
        std::swap(ci,cz);
        cz+=ci;
        print(cz),putchar(' ');
    }
}

int main(){
    test();
}