神仙构造题…没智商..

考虑构造出一棵树$T_0$，对于$T_0$中的任意一条边$(u,v)$，我们在第k$(0<k\leq \lfloor\frac n 2\rfloor)$棵树中添加边$((u+k)~mod~n,(v+k)~mod~n)$。

现在考虑什么样子的$T_0$能保证对于任意$k_1\neq k_2$，均满足$((u+k_1)~mod~n,(v+k_1)~mod~n)\neq ((u+k_2)~mod~n,(v+k_2)~mod~n)$。

首先答案一定有$\lfloor \frac n 2 \rfloor$棵生成树，那么我们可以考虑把点集分成两半，每个点集里面的边全都从某个点出发，这样我们只需要变化这个出发点，其他所有边也会跟着平移，就可以保证所有边不重复。

设$m=\lfloor \frac n 2\rfloor$，首先令点编号从0开始。

首先连边$(0,m)$，这条边显然在任何一棵树中都不会重复。

对于$1\leq i\leq m-1$,连边$(0,i)$.

对于$ m<i<n$,连边$(m,i)$。

这样在$0+k和m+k$不重复的情况下，任何生成树内一定不会出现重复边了。

#include <algorithm>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using int_t = long long int;
using pair_t = std::pair<int_t, int_t>;
using std::cin;
using std::cout;
using std::endl;
std::vector<pair_t> edges;
int main() {
    int_t n;
    cin >> n;
    int_t mid = n / 2;
    edges.push_back(pair_t(0, mid));
    for (int_t i = 1; i < mid; i++) {
        edges.push_back(pair_t(0, i));
    }
    for (int_t i = mid + 1; i < n; i++) {
        edges.push_back(pair_t(mid, i));
    }
    cout << n / 2 << endl;
    for (int_t i = 0; i < n / 2; i++) {
        for (const auto& edge : edges) {
            int_t a, b;
            std::tie(a, b) = edge;
            cout << (a + i) % n + 1 << " " << (b + i) % n + 1 << " ";
        }
        cout << endl;
    }
    return 0;
}

不会势能分析..

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#include <cmath>
#define debug(x) std::cout << #x << " = " << x << std::endl;

using int_t = long long int;

using std::cin;
using std::endl;
using std::cout;
const int_t INF = 0x7fffffff;

const int_t LARGE = 1e5;
void* allocate();
struct Node {
	Node* left = nullptr,*right = nullptr;
	int begin,end;
	int_t sum = 0;
	int minval = INF;
	int maxval = -INF;
	//±äÁ¿Î´³õʼ»¯
	int mark = 0;
	Node(int begin,int end) {
		this -> begin = begin;
		this -> end = end;
	}
	void maintain() {
		if(begin != end) {
			sum = left -> sum + right -> sum;
			minval = std::min(left->minval,right -> minval);
			maxval = std::max(left -> maxval ,right -> maxval);
		}
	}
	void add(int x) {
		mark += x;
		minval += x;
		maxval += x;
		sum += (int_t)(end - begin + 1) * x;
#ifdef DEBUG
		cout<<"adding "<<x<<" at node "<<this->begin<<" "<<this->end<<" "<<sum<<" "<<mark<<" "<<minval<<" "<<maxval<<endl;
#endif
	}
	void pushDown() {
		if(begin != end) {
			left -> add(mark);
			right -> add(mark);
			mark = 0;
		}
	}
	void add(int begin,int end,int val) {
		if(end < this -> begin || begin > this -> end) return;
#ifdef DEBUG
		cout<<"adding "<<val<<" for "<<begin<<" "<<end<<" at "<<this->begin<<" "<<this->end<<endl;
#endif
		if(this -> begin >= begin && this -> end <= end) {
#ifdef DEBUG
			cout<<"dir add at "<<this->begin<<" "<<this->end<<" "<<val<<endl;
#endif
			this -> add(val);
			return;
		}
		pushDown();
		left -> add(begin,end,val);
		right -> add(begin,end,val);
		maintain();
	}
	int_t querySum(int begin,int end) {
		if(end < this -> begin || begin > this -> end) return 0;
		if(this -> begin >= begin && this -> end <= end) {
			return this -> sum;
		}
		pushDown();
		return left -> querySum(begin,end) + right -> querySum(begin,end);
	}
	int queryMin(int begin,int end) {
		if(end < this -> begin || begin > this -> end ) return INF;
		if(this -> begin >= begin && this -> end <= end) return this -> minval;
		pushDown();
		return std::min(left -> queryMin(begin,end),right -> queryMin(begin,end));
	}
	void divide(int x) {
#ifdef DEBUG
		cout<<"div "<<x<<" at node "<<this->begin<<" "<<this->end<<endl;
#endif
		if(int_t(this -> maxval - floor((double)this -> maxval / x)) == int_t(this -> minval - floor((double)this -> minval / x))) {
			this -> add(-(this -> maxval - floor((double)this -> maxval / x)));
			return;
		}
		pushDown();
		left -> divide(x);
		right -> divide(x);
		maintain();
	}
	void divide(int begin,int end,int val) {
		if(end < this -> begin || begin > this -> end) return;
		if(this -> begin >= begin && this -> end <= end) {
			this -> divide(val);
			return;
		}
		pushDown();
		left -> divide(begin,end,val);
		right -> divide(begin,end,val);
		maintain();
	}
	static Node* build(int begin,int end,int* val) {
		Node* node = new (allocate()) Node(begin,end);
		if(begin != end) {
			int_t mid = (begin + end) / 2;
			node -> left = build(begin,mid,val);
			node -> right = build(mid + 1 ,end ,val);
			node -> maintain();
		} else {
			node -> sum = node -> minval = node -> maxval = val[begin];
		}
		return node;
	}
};
void* allocate(){
    const int_t SIZE = 3e5;
    static char buf[SIZE * sizeof(Node)];
    static int_t used = 0;
    return buf + (++used) * sizeof(Node);
}

int val[LARGE + 1];
int n,m;
int main() {
	scanf("%d%d",&n,&m);
	for(int_t i = 1; i <= n; i ++) scanf("%d",&val[i]);
	Node* root = Node::build(1,n,val);
	for(int_t i = 1; i <= m; i ++) {
		int opt,left,right,val;
		scanf("%d%d%d",&opt,&left,&right);
		left += 1;
		right += 1;
		if(opt == 1) {
			scanf("%d",&val);
			root -> add(left,right,val);
		} else if(opt == 2) {
			scanf("%d",&val);
			root -> divide(left,right,val);
		} else if(opt == 3) {
			printf("%d\n",root->queryMin(left,right));
		} else if(opt == 4) {
			printf("%lld\n",root->querySum(left,right));
		}
	}
	return 0;
}

一个区间可以重排称为连续段，当且仅当

• 区间最大值-区间最小值=区间长度
• 区间内没有重复的数

对于第一个条件显然很好维护（线段树查询区间最值），对于第二个条件，我们给每个出现的数映射到一个随机的权值。

然后对于查询区间$[left,right]$，我们查询出这个区间内所有数的异或值，然后将其与从$MIN_{left\leq i\leq right}a_i$到$MAX_{left\leq i\leq right}a_i$的数的权值异或起来进行对比，如果相等则可以认为这个区间没有重复的数。

#include <assert.h>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iostream>
#include <random>
#include <tuple>
#include <utility>
using int_t = long long int;
using pair_t = std::pair<int_t, int_t>;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 1 << 20;
const int_t INF = 0x7fffffff;
std::mt19937 gen;
std::uniform_int_distribution<int_t> rand_int(0, INT64_MAX);
int_t xorVal[LARGE + 1];
int_t maxVal[LARGE + 1], minVal[LARGE + 1];
int_t offset;
void init(int_t n) {
    n += 2;
    offset = 1;
    while (offset < n) offset *= 2;
    memset(minVal, 0x3f, sizeof(minVal));
    // memcpy(xors,)
}

int_t queryXor(int_t left, int_t right) {
    left += offset - 1;
    right += offset + 1;
    int_t result = 0;
    while ((left ^ right) != 1) {
        if ((left & 1) == 0) result ^= xorVal[left ^ 1];
        if ((right & 1)) result ^= xorVal[right ^ 1];
        left /= 2;
        right /= 2;
    }
    return result;
}
pair_t queryMaxMin(int_t left, int_t right) {
    left += offset - 1;
    right += offset + 1;
    int_t max = 0, min = INF;
    while ((left ^ right) != 1) {
        if ((left & 1) == 0) {
            max = std::max(max, maxVal[left ^ 1]);
            min = std::min(min, minVal[left ^ 1]);
        };
        if ((right & 1)) {
            max = std::max(max, maxVal[right ^ 1]);
            min = std::min(min, minVal[right ^ 1]);
        }
        left /= 2;
        right /= 2;
    }
    return pair_t(max, min);
}
void modifyXor(int_t pos, int_t val) {
    pos += offset;
    xorVal[pos] = val;
    pos /= 2;
    while (pos) {
        xorVal[pos] = xorVal[pos * 2 + 1] ^ xorVal[pos * 2];
        pos /= 2;
    }
}
void modifyVal(int_t pos, int_t val) {
    pos += offset;
    minVal[pos] = maxVal[pos] = val;
    pos /= 2;
    while (pos) {
        minVal[pos] = std::min(minVal[pos * 2], minVal[pos * 2 + 1]);
        maxVal[pos] = std::max(maxVal[pos * 2], maxVal[pos * 2 + 1]);
        pos /= 2;
    }
}
struct Opt {
    int_t v1, v2;
    int_t type;
} opts[LARGE + 1];
int_t n, m;
std::vector<int_t> numbers;
int_t prefix[LARGE + 1];
int_t getRank(int_t x) {
    return std::lower_bound(numbers.begin(), numbers.end(), x) -
           numbers.begin() + 1;
}
int_t nums[LARGE + 1];
int main() {
    gen.seed(std::random_device()() + int_t(new char) + time(0));
    scanf("%lld%lld", &n, &m);
    init(n);
    for (int_t i = 1; i <= n; i++) {
        scanf("%lld", &nums[i]);
        numbers.push_back(nums[i]);
        numbers.push_back(nums[i] + 1);
    }
    for (int_t i = 1; i <= m; i++) {
        auto& opt = opts[i];
        scanf("%lld%lld%lld", &opt.type, &opt.v1, &opt.v2);
        if (opt.type == 1) {
            numbers.push_back(opt.v2);
            numbers.push_back(opt.v2 + 1);
        }
    }
    std::sort(numbers.begin(), numbers.end());
    numbers.resize(std::unique(numbers.begin(), numbers.end()) -
                   numbers.begin());
    for (int_t i = 1; i <= numbers.size(); i++) {
        int_t val = rand_int(gen);
        prefix[i] = prefix[i - 1] ^ val;
    }
    for (int_t i = 1; i <= n; i++) {
        int_t curr = getRank(nums[i]);
        modifyXor(i, prefix[curr] ^ prefix[curr - 1]);
        modifyVal(i, curr);
    }
    for (int_t i = 1; i <= m; i++) {
        const auto& opt = opts[i];
        if (opt.type == 1) {
            int_t numbers = getRank(opt.v2);
            modifyVal(opt.v1, numbers);
            //离散化和没离散化的搞混了
            modifyXor(opt.v1, prefix[numbers] ^ prefix[numbers - 1]);
        } else {
            int_t min, max;
            std::tie(max, min) = queryMaxMin(opt.v1, opt.v2);
            //区间长度必须要等于max-min+1!
            if (max - min == opt.v2 - opt.v1 &&
                (prefix[max] ^ prefix[min - 1]) == queryXor(opt.v1, opt.v2)) {
                printf("damushen\n");
            } else {
                printf("yuanxing\n");
            }
        }
    }
    return 0;
}

$$ \text{由欧拉公式得}e^{i\theta}=\cos \left( \theta \right) +i\sin \left( \theta \right) \\ e^{-i\theta}=\cos \left( \theta \right) -i\sin \left( \theta \right) \\ \text{故}\sin \left( \theta \right) =\frac{e^{i\theta}-e^{-i\theta}}{2i} \\ \text{设}\sin \left( \theta \right) =x,\arcsin \left( x \right) =\theta \\ \text{设}y=e^{i\theta} \\ \text{则}x=\frac{y-\frac{1}{y}}{2i} \\ 2ix=y-\frac{1}{y} \\ y^2-2ixy-1=0 \\ y=\frac{2ix\pm \sqrt{-4x^2+4}}{2}=\frac{2ix\pm 2\sqrt{1-x^2}}{2}=ix\pm \sqrt{1-x^2} \\ \text{令}\theta =\text{0,可得}x=\text{0,}y=\text{1,故}y=ix+\sqrt{1-x^2} \\ \text{所以}e^{i\theta}=ix+\sqrt{1-x^2} \\ i\theta =\log \left( ix+\sqrt{1-x^2} \right) \\ \theta =\arcsin \left( x \right) =\frac{1}{i}\log \left( ix+\sqrt{1-x^2} \right) =-i\log \left( ix+\sqrt{1-x^2} \right) \\ \arcsin \left( F\left( x \right) \right) =-i\log \left( iF\left( x \right) +\sqrt{1-F\left( x \right) ^2} \right) \\ \cos \left( \theta \right) =\frac{e^{i\theta}+e^{-i\theta}}{2} \\ \text{同上可证}\arccos \left( x \right) =-i\log \left( x\pm \sqrt{x^2-1} \right) \\ \text{同上可证}\arctan \left( x \right) =\frac{i}{2}\log \left( \frac{1-iz}{1+iz} \right) $$

#include <assert.h>
#include <cmath>
#include <cstring>
#include <iostream>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

const int_t mod = 998244353;
const int_t g = 3;
const int_t LARGE = 1 << 19;
template <typename T>
T power(T base, int_t index);
void poly_inv(const struct complex* A, int_t n, struct complex* result);
int_t bitRev(int_t base, int_t size2);
int_t upper2n(int_t x);
void poly_log(const struct complex* A, int_t n, struct complex* result);
void transform(complex* A, int_t len, int_t arg);
void poly_exp(const struct complex* A, int_t n, struct complex* result);
void poly_sqrt(const struct complex* A, int_t n, struct complex* result);
struct complex {
    int_t real, imag;
    complex operator+(const complex& another) const {
        return complex{(real + another.real) % mod,
                       (imag + another.imag) % mod};
    }
    complex operator-(const complex& another) const {
        return complex{(real - another.real + mod) % mod,
                       (imag - another.imag + mod) % mod};
    }
    complex operator*(const complex& another) const {
        return complex{
            (real * another.real % mod - imag * another.imag % mod + mod) % mod,
            (real * another.imag % mod + imag * another.real % mod) % mod};
    }
    complex operator/(const complex& another) const {
        int_t a = real, b = imag, c = another.real, d = another.imag;
        int_t inv = power(c * c % mod + d * d % mod, -1);
        return complex{(a * c % mod + b * d % mod) % mod * inv % mod,
                       (b * c % mod - a * d % mod + mod) % mod * inv % mod};
    }
    complex operator%(const int_t& x) const {
        return complex{real % x, imag % x};
    }
    complex(int_t a = 0, int_t b = 0) {
        this->real = a;
        this->imag = b;
    }
    complex& operator=(const int_t& rhs) {
        this->real = rhs;
        this->imag = 0;
        return *this;
    }
};
std::ostream& operator<<(std::ostream& os, const complex& comp) {
    os << "complex{real=" << comp.real << ",imag=" << comp.imag << "}";
    return os;
}
int revs[20][LARGE + 1];

int main() {
    for (int i = 0; (1 << i) <= LARGE; i++) {
        for (int j = 0; j < LARGE; j++) {
            revs[i][j] = bitRev(j, i);
        }
    }
    static complex A[LARGE], Ax[LARGE], B[LARGE];
    int_t n, type;
    scanf("%lld%lld", &n, &type);
    if (type == 0) {
        for (int_t i = 0; i < n; i++) {
            scanf("%lld", &A[i].real);
            Ax[i] = A[i];
        }
        int_t size2 = upper2n(n + n);
        transform(A, size2, 1);
        for (int_t i = 0; i < size2; i++) A[i] = A[i] * A[i];
        transform(A, size2, -1);
        const auto inv = complex{1, 0} / complex{size2, 0};
        for (int_t i = 0; i < size2; i++) {
            if (i < n)
                A[i] = A[i] * inv;
            else
                A[i] = 0;
        }
        A[0].real = 1;
        for (int_t i = 1; i < n; i++) A[i] = A[i] * complex{mod - 1, 0};
        poly_sqrt(A, n, B);
        for (int_t i = 0; i < n; i++) B[i] = B[i] + Ax[i] * complex{0, 1};
        memset(A, 0, sizeof(A));
        poly_log(B, n, A);
        for (int_t i = 0; i < n; i++) {
            A[i] = A[i] * complex{0, mod - 1};
        }
        for (int_t i = 0; i < n; i++) {
            printf("%lld ", A[i].real);
        }
    } else {
        for (int_t i = 0; i < n; i++) {
            int_t x;
            scanf("%lld", &x);
            A[i].imag = (mod - x) % mod;
            Ax[i].imag = x % mod;
        }
        Ax[0].real = A[0].real = 1;
        poly_inv(Ax, n, B);
        int_t size2 = upper2n(2 * n);
        transform(B, size2, 1);
        transform(A, size2, 1);
        for (int_t i = 0; i < size2; i++) B[i] = A[i] * B[i];
        transform(B, size2, -1);
        for (int_t i = 0; i < size2; i++) {
            if (i < n)
                B[i] = B[i] / complex{size2, 0};
            else
                B[i] = 0;
        }
        memset(A, 0, sizeof(A));
        poly_log(B, n, A);
        for (int_t i = 0; i < n; i++) {
            A[i] = A[i] / complex{2, 0} * complex{0, 1};
            printf("%lld ", A[i].real);
        }
    }
    return 0;
}

void transform(complex* A, int_t len, int_t arg) {
    int_t size2 = log2(len);
    for (int_t i = 0; i < len; i++) {
        int_t x = revs[size2][i];
        if (x > i) std::swap(A[i], A[x]);
    }
    for (int_t i = 2; i <= len; i *= 2) {
        complex mr = power(complex{g, 0}, arg * (mod - 1) / i);
        for (int_t j = 0; j < len; j += i) {
            complex curr{1, 0};
            for (int_t k = 0; k < i / 2; k++) {
                complex u = A[j + k];
                complex t = A[j + k + i / 2] * curr;
                A[j + k] = (u + t);
                A[j + k + i / 2] = (u - t);
                curr = curr * mr;
            }
        }
    }
}
//计算多项式A在模x^n下的逆元
// C(x)<-2B(x)-A(x)B^2(x)
void poly_inv(const complex* A, int_t n, complex* result) {
    if (n == 1) {
        result[0] = power(A[0], -1);
        return;
    }
    poly_inv(A, n / 2 + n % 2, result);
    static complex temp[LARGE + 1];
    int_t size2 = upper2n(3 * n + 1);
    for (int_t i = 0; i < size2; i++) {
        if (i < n)
            temp[i] = A[i];
        else
            temp[i] = complex{0, 0};
    }
    transform(temp, size2, 1);
    transform(result, size2, 1);
    for (int_t i = 0; i < size2; i++) {
        result[i] =
            (complex{2, 0} * result[i] - temp[i] * result[i] * result[i]);
    }
    transform(result, size2, -1);
    int_t inv = power(size2, -1);
    for (int_t i = 0; i < size2; i++) {
        if (i < n) {
            result[i] = result[i] * complex{inv, 0};
        } else {
            result[i] = complex{0, 0};
        }
    }
}

void poly_log(const complex* A, int_t n, complex* result) {
    int_t size2 = upper2n(2 * n);
    static complex Ad[LARGE + 1];
    for (int_t i = 0; i < size2; i++) {
        if (i < n) {
            Ad[i] = complex{(i + 1), 0} * A[i + 1];

        } else {
            Ad[i] = complex{0, 0};
        }
        result[i] = complex{0, 0};
    }
    transform(Ad, size2, 1);
    poly_inv(A, n, result);
    transform(result, size2, 1);
    for (int_t i = 0; i < size2; i++) {
        result[i] = result[i] * Ad[i];
    }
    transform(result, size2, -1);
    int_t inv = power(size2, -1);
    for (int_t i = 0; i < size2; i++)
        if (i < n)
            result[i] = result[i] * complex{inv, 0};
        else
            result[i] = complex{0, 0};
    for (int_t i = n - 1; i >= 1; i--) {
        result[i] = result[i - 1] / complex{i, 0};
    }
    result[0] = complex{0, 0};
}
void poly_exp(const complex* A, int_t n, complex* result) {
    if (n == 1) {
        // assert(A[0] == 0);
        result[0] = complex{1, 0};
        return;
    }
    poly_exp(A, n / 2 + n % 2, result);
    static complex G0[LARGE + 1], Ax[LARGE + 1];
    int_t size2 = upper2n(2 * n);
    poly_log(result, n, G0);
    for (int_t i = 0; i < size2; i++) {
        if (i < n)
            Ax[i] = A[i];
        else
            Ax[i] = complex{0, 0};
    }
    transform(Ax, size2, 1);
    transform(G0, size2, 1);
    transform(result, size2, 1);
    for (int_t i = 0; i < size2; i++)
        result[i] = (result[i] - result[i] * (G0[i] - Ax[i]));
    transform(result, size2, -1);
    int_t inv = power(size2, -1);
    for (int_t i = 0; i < size2; i++)
        if (i < n)
            result[i] = result[i] * complex{inv, 0};
        else
            result[i] = complex{0, 0};
}
void poly_sqrt(const complex* A, int_t n, complex* result) {
    if (n == 1) {
        assert(A[0].real <= 1);
        result[0] = A[0];
        return;
    }
    poly_sqrt(A, n / 2 + n % 2, result);
    int_t size2 = upper2n(3 * n);
    static complex Ax[LARGE + 1], pInv[LARGE];
    for (int_t i = 0; i < size2; i++) {
        if (i < n) {
            Ax[i] = A[i];
        } else {
            Ax[i] = 0;
        }
        pInv[i] = 0;
    }
    poly_inv(result, n, pInv);
    transform(Ax, size2, 1);
    transform(result, size2, 1);
    transform(pInv, size2, 1);
    const int_t inv2 = power(2ll, -1);
    for (int_t i = 0; i < size2; i++) {
        result[i] = (result[i] -
                     (result[i] * result[i] % mod - Ax[i] + mod) % mod * inv2 %
                         mod * pInv[i] % mod +
                     mod) %
                    mod;
    }
    transform(result, size2, -1);
    for (int_t i = 0; i < size2; i++) {
        if (i < n)
            result[i] = result[i] * power(size2, -1) % mod;
        else
            result[i] = 0;
    }
}
template <typename T>
T power(T base, int_t index) {
    const int_t phi = mod - 1;
    index = (index % phi + phi) % phi;
    T result = 1;
    while (index) {
        if (index & 1) result = result * base % mod;
        base = base * base % mod;
        index >>= 1;
    }
    return result;
}
int_t bitRev(int_t base, int_t size2) {
    int_t result = 0;
    for (int_t i = 1; i < size2; i++) {
        result |= (base & 1);
        base >>= 1;
        result <<= 1;
    }
    result |= (base & 1);
    return result;
}
int_t upper2n(int_t x) {
    int_t result = 1;
    while (result < x) result *= 2;
    return result;
}

很毒瘤。

考虑递归构造。

首先k=1的时候，答案为a。

增加k时，将现有字符串中的字符全部顺移一位(aabaa变成bbcbb)

然后新字符串先放两个a，然后遍历旧字符串，每次遇到一个b就放ba，直到放完，然后再放一个a。

最后把不到n的部分拿a补上。

#include <assert.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <vector>
using int_t = long long int;
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 1e5;

void process() {
    int_t n, k;
    cin >> n >> k;
    std::vector<char> buf;
    buf.push_back('a');
    for (int_t i = 1; i <= k - 1; i++) {
        std::vector<char> next{'a', 'a'};
        for (char chr : buf) {
            next.push_back(chr + 1);
            if (chr == 'a') {
                next.push_back('a');
            }
        }
        next.push_back('a');
        buf = next;
    }
#ifdef DEBUG
    for (char chr : buf) cout << chr << " ";
    cout << endl;
#endif
    if (n < buf.size()) {
        printf("CiYe\n");
        return;
    }
    for (int_t i = 1; i <= n - buf.size(); i++) {
        printf("a");
    }
    for (char chr : buf) printf("%c", chr);
    cout << endl;
}

int main() {
    int_t T;
    cin >> T;
    while (T--) {
        process();
    }

    return 0;
}