2019, XII Samara Regional Intercollegiate Programming Contest

solved	A	B	C	D	E	F	G	H	I	J	K	L	M
11 / 13	O	O	O	Ø	O	Ø	·	O	O	O	O	O	O

• O：比赛时通过
• Ø：赛后通过
• !：比赛时尝试了未通过
• ·：比赛时未尝试

比赛链接

A. Rooms and Passages

Solved by Sstee1XD. 0:34(+)

题意： 从点$i(0 \leq i \leq n)$到点$n+1$，一路上负数让你相应的通行证消失，正数需要相应通行证才可以通过，问你每次最长能走多少步。

思路： 搞个双指针搞一下。

AC代码

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 5e5 + 10;
 
int head, rear;
int good[N];
int cor[N];
int n;
 
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &cor[i]);
		good[i] = 1;
	}
	head = 0, rear = 0;
	for (int i = 0; i <= n - 1; ++i) {
		head = i;
		if (i > 0 && cor[i] < 0) good[ -cor[i] ]++;
		while (rear < n) {
			if (cor[rear + 1] < 0) {
				good[ -cor[rear + 1] ]--;
				rear++;
			} else {
				if (good[ cor[rear + 1] ] > 0) rear++;
				else break;
			}
		}
		printf("%d%c", rear - head, " \n"[i == n - 1]);
	}
	return 0;
}

B - Rearrange Columns

solved by Tryna & lllllan.0:16(+2)

题解： 交换一些列，使得 # 连通，签到题。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;
string s1, s2;
void run () {
	cin>>s1>>s2;
	int len = s1.size();
	int num1 = 0, num2 = 0, num3 = 0, num4 = 0;
	for(int i = 0; i < len; i++) {
		if(s1[i] == '#' && s2[i] == '.') num1++;
		if(s1[i] == '#' && s2[i] == '#') num2++;
		if(s1[i] == '.' && s2[i] == '#') num3++;
		if(s1[i] == '.' && s2[i] == '.') num4++;
	}
	if((num1 && num3 == 0) || (num3 && num1 == 0)) {
		puts("YES");
		for(int i = 1; i <= num1 + num2; i++) printf("#");
		for(int i = 1; i <= num3 + num4; i++) printf(".");
		puts("");
		for(int i = 1; i <= num1; i++) printf(".");
		for(int i = 1; i <= num2 + num3; i++) printf("#");
		for(int i = 1; i <= num4; i++) printf(".");
		puts("");		
		return ;		
	}
	if(num2 == 0) {
		puts("NO");
		return ;
	}
	puts("YES");
	for(int i = 1; i <= num1 + num2; i++) printf("#");
	for(int i = 1; i <= num3 + num4; i++) printf(".");
	puts("");
	for(int i = 1; i <= num1; i++) printf(".");
	for(int i = 1; i <= num2 + num3; i++) printf("#");
	for(int i = 1; i <= num4; i++) printf(".");
	puts("");
}

int main () {
	int t = 1;
//	scanf("%d", &t);
	while (t--) run();
	return 0;
}

C. Jumps on a Circle

Solved by Sstee1XD & Tryna. 0:49(+1)

题意： 圆上点编号$0$ ~ $p-1$，从点0开始，第$i$步跳$i$长，问跳$n$步能跳到几个不同的点。

思路： 步长以$1$为公差增长，很容易想到首尾相加，让它成为一个能被$p$整除的步长，最终就会回到原点，变成一个循环的过程。跳的次数要为偶数，所以最多跳$2p$步。

AC代码

#include<bits/stdc++.h>

using namespace std;
#define ll long long

const int maxn = 1e7 + 10;
ll n;
int p;
bool vis[maxn];
int main() {
	scanf("%d %lld", &p, &n);
    int ans = 1;
    int last = min((ll)p * 2 - 1, n);
    vis[0] = true;
    int to = 2;
    int now = 1 % p;
    while (last--) {
    	if (!vis[now]) {
    		vis[now] = true;
    		ans++;
		}
		now = (now + to);
		now %= p;
		to++;
	}
	printf("%d\n", ans);
	return 0;
}

D - Country Division

solved by lllllan. (-)

题意： 给定一棵树，每次会给一些点染成蓝色和红色，询问是否能过通过割断一些边，使得蓝色和红色的点能够分别相互连通但红蓝之间却不连通。

题解： 其实大致的就是，给红蓝两色各自划分出一棵子树给他们。所有优先考虑分别对红色和蓝色的点集找出他们的最近公共祖先（指在红色点集找出所有点的lcaR、在蓝色点集找出所有点的lcaB）。

• 如果很明显的红色方的lcaR与蓝色方的lcaB相同，一定不能分割开了
• lcaR和lcaB不同的情况下，再对两者再求一次lca，如果与这两个点都不相同，就一定可以划分出两棵子树出来。
• 如果lcaR和lcaR的lca在这两个点之间，其实还可以判断一下【偷懒不写了，结合代码自行分析

AC代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

int cnt, head[maxn];
struct edge { int to, next; } e[maxn << 1];
void add (int u, int v) {
	e[++cnt] = {v, head[u]}; head[u] = cnt;
	e[++cnt] = {u, head[v]}; head[v] = cnt;
}

int n, q;
int dep[maxn];
int lg[maxn];
int fa[maxn][22];

void init () {
	for (int i = 1; i <= n; ++i){
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	}
}

void dfs (int now, int pre) {
	fa[now][0] = pre; dep[now] = dep[pre] + 1;
	for (int i = 1; i <= lg[dep[now]]; ++i)
		fa[now][i] = fa[fa[now][i - 1]][i - 1];
	for (int i = head[now]; i; i = e[i].next) 
		if (e[i].to != pre) dfs(e[i].to, now);
}

int lca (int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
	if (x == y) return x;
	for (int k = lg[dep[x]] - 1; k >= 0; --k) 
		if (fa[x][k] != fa[y][k])
			x = fa[x][k], y = fa[y][k];
	return fa[x][0];
}

int a[maxn];
int b[maxn];

void run () {
	scanf("%d%d", a, b);
	
	for (int i = 1; i <= a[0]; ++i) scanf("%d", a + i);
	for (int i = 1; i <= b[0]; ++i) scanf("%d", b + i);
	
	if (a[0] == 0 || b[0] == 0) return (void)( printf("YES\n") );
	
	int x = a[1], y = b[1];
	for (int i = 2; i <= a[0]; ++i) x = lca(x, a[i]);
	for (int i = 2; i <= b[0]; ++i) y = lca(y, b[i]);
	
	int Lca = lca(x, y);
	if (Lca == x) {
		for (int i = 1; i <= a[0]; ++i) {
			if (lca(a[i], y) == y) return (void)( printf("NO\n") );
		}
	} else if (Lca == y) {
		for (int i = 1; i <= b[0]; ++i) {
			if (lca(b[i], x) == x) return (void)( printf("NO\n") );
		}
	} 
	
	printf("YES\n");
}

int main () {
	scanf("%d", &n);
	init();
	
	for (int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	
	dfs(1, 0);
	
	scanf("%d", &q);
	while (q--) run();
	
	return 0;
}

E. Third-Party Software - 2

Solved by Sstee1XD & lllllan. 1:48(+1)

题意： 每个人三个权值$a_i, b_i, c_i$，两人对战，当一方至少有两个权值大于另一方时获胜。拥有黑暗力量的人可以在每次对战前在非负整数范围内更改自己的权值，但权值和不能变。问$n$个人分别拥有黑暗力量时，最多能战胜多少人。

思路： 贪心地让$0$去对应对方最大的权值，看剩下两个权值能否都大于。那么我们记录下权值和与最大权值，二分一下，即可得到答案。注意要忽略自己的影响。

AC代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 10;

int n;
ll a[N], b[N], c[N], maxx[N];
ll d[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i] >> c[i];
		maxx[i] = max({a[i], b[i], c[i]});
		d[i] = a[i] + b[i] + c[i] - maxx[i];
	}
	sort(d + 1, d + 1 + n);
	for (int i = 1; i <= n; ++i) {
		int pos = upper_bound(d + 1, d + 1 + n, a[i] + b[i] + c[i] - 2) - d;
		pos--;
		if (maxx[i] >= 2) pos--;
		if (i != 1) cout << " ";
		cout << pos;
	}
	cout << "\n";
	return 0;
}

F - Friendly Fire

solved by Tryna.(-)

题意： 选两只怪兽进行攻击，一只怪兽能打败另外一只怪兽当且仅当这只怪兽的$a$大于另外一只怪兽的$h$，求死去的怪兽的最大的攻击力。

题解： 我们先将所有怪兽从大到小排序。然后我们用双指针来记录这两只怪兽。当两只怪兽都死去我们就可以直接退出循环了，因为攻击力是从大到小排序的；当攻击力高的怪兽能打败攻击力低的怪兽，因为此时攻击力高的怪兽都能打败攻击力低的怪兽的后面的怪兽，所以我们将攻击力高的怪兽++；同理，当攻击力低的怪兽能打败攻击力高的怪兽，我们将攻击力低的怪兽++；如果两只怪兽都死不掉我们将攻击力低的怪兽++。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const double eps = 1e-8;
const int maxn = 3e5 + 10;
const int mod = 1e9 + 7;
int n;

struct node{
	int a, h, id;
	bool operator < (const node &r) {
		if(a == r.a) return h < r.h;
		return a > r.a;
	}
}p[maxn];

void solve(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &p[i].a, &p[i].h);
		p[i].id = i;
	}
	sort(p + 1, p + 1 + n);
	int now = 0, ch1 = 1, ch2 = 2;
	int i = 1, j = 2;
	while(i <= n && j <= n) {
		if(i == j) j++;
		else if(p[i].a >= p[j].h && p[j].a >= p[i].h) {
			if(p[i].a + p[j].a >= now) {
				now = p[i].a + p[j].a;
				ch1 = p[i].id;
				ch2 = p[j].id;				
			}
			break;
		}
		else if(p[i].a >= p[j].h) {
			if(now < p[j].a) {
				now = p[j].a;
				ch1 = p[i].id;
				ch2 = p[j].id;				
			}
			i++;
		}
		else if(p[j].a >= p[i].h) {
			if(now < p[i].a) {
				now = p[i].a;
				ch1 = p[i].id;
				ch2 = p[j].id;				
			}
			j++;
		}
		else j++;
	}
	printf("%d\n%d %d\n", now, ch1, ch2);
}
int main() {
	solve();
	return 0;
}

H. Missing Number

Solved by Sstee1XD & Tryna. 4:47(+3)

题意： 交互题。有一个长度为$n + 1$的序列，其由$0$ ~ $n$组成，现在里面缺少了一个数字，你每次可以询问某位置上数字的某个二进制位是多少，请在$2*n + 19$次询问内找到答案。

思路： 可以检查当前二进制位上的$0$, $1$数量确定剩下的位置，每次能消去一半。注意消去的时候，对应二进制位上应有的$0$, $1$数量也要跟着减少。

AC代码

#include<bits/stdc++.h>

using namespace std;

#define endl "\n"

const int maxn = 2e5 + 10;

int n;
int num[1003][1003];
vector<int> G[1003];
vector<int> o, e;

int ask(int id, int b) {
	int val;
	cout << "? " << id << " " << b << endl;
	cout.flush();
	cin >> val;
	return val;
}

void pt(int b) {
	cout << "! " << b << endl;
	cout.flush();
}

void gao(int v, int d) {
	int now = 0;
	while (now <= 10) {
		num[v & 1][now] += d;
		v >>= 1;
		now++;
	}
}

void dfs(int tmp, int b) {
	if (tmp > n) return;
	if (b > 10) {
		gao(tmp, -1);
		return;
	}
	if (tmp + (1 << b) <= n) dfs(tmp + (1 << b), b + 1);
	dfs(tmp, b + 1);
}

int main() {
	cin >> n;
	gao(0, 1);
	for (int i = 1; i <= n; ++i) {
		gao(i, 1);
		G[0].push_back(i);
	}
	int now = 0;
	int b = 0;
	int v;
	int tmp = 0;
	while (G[now].size() > 1) {
		for (auto t : G[now]) {
			v = ask(t, b);
			if (v & 1) o.push_back(t);
			else e.push_back(t);
		}
		if (o.size() < num[1][b]) {
			G[now ^ 1] = o;
			dfs(tmp, b + 1);
			tmp += 1 << b;
		} else if (e.size() < num[0][b]){
			G[now ^ 1] = e;
			dfs(tmp + (1 << b), b + 1);
		} else {
			pt(tmp);
			return 0;
		}
		o.clear();
		e.clear();
		G[now].clear();
		now ^= 1;
		b++;
	}
	if (G[now].size() < 1) {
		pt(tmp);
		return 0;
	}
	v = ask(G[now][0], b);
	if (v == 0) tmp += 1 << b;
	pt(tmp);
	return 0;
}

I - Painting a Square

solved by lllllan. 01:03(+1)

题意： 给定一个大正方形和小正方形，要求每次只能横竖移动一个单位，问最少需要移动小正方形几次，可以将大正方形覆盖。

AC代码

#include<bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
ll n, m;
void run () {
	scanf("%lld %lld", &n, &m);
//	ll ans = (n * n - m * m + m - 1) / m;
	ll ans = (n - m) * (n / m) + (n - n % m - m) + (n % m) * (n / m + (n % m != 0));
	printf("%lld\n", ans);
}

int main () {
	int t = 1;
//	scanf("%d", &t);
	while (t--) run();
	return 0;
}

J. The Power of the Dark Side - 2

Solved by Sstee1XD & lllllan. 2:03(+)

题意： $n$件物品，$m$个功能，每件物品能实现$a_i$~$b_i$的功能，选最少的物品实现所有功能。

思路： 把每件物品的功能区间存下来，排个序，遍历过去，中间贪心地让每次拼接的区间尽量长就行。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m;

struct Node {
	int l, r, id;
	bool operator < (const Node &a) {
		if (l == a.l) return r > a.r;
		return l < a.l;
	}
}node[N];


int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1, l, r; i <= n; ++i) {
		scanf("%d %d", &node[i].l, &node[i].r);
		node[i].id = i;
	}
	sort(node + 1, node + 1 + n);
	if (node[1].l > 1) {
		puts("NO");
		return 0;
	}
	int pre = 1;
	int last = 0;
	int maxx = 0;
	int maxi;
	vector<int> ans;
	for (int i = 1; i <= n; ++i) {
		maxx = 0;
		while (pre <= n && node[pre].l <= last + 1) {
			if (node[pre].r > maxx) {
				maxx = node[pre].r;
				maxi = node[pre].id;
			}
			pre++;
		}
		if (!maxx) {
			puts("NO");
			return 0;
		}
		ans.push_back(maxi);
		last = maxx;
		if (maxx >= m) {
			break;
		}
	}
	if (last < m) {
		puts("NO");
		return 0;
	}
	puts("YES");
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); ++i) {
		printf("%d%c", ans[i], " \n"[i == ans.size() - 1]);
	}
	return 0;
}

K. Deck Sorting

Solved by Sstee1XD & lllllan. 3:15(+5)

题意： 桌上有一堆RGB三种颜色的卡片，每次只能取出最上面的卡片。你现在有两个只入不出的栈，可以将卡片放进去，最后将其中一个栈堆在另一个栈上，问你能否使最终的颜色分好类，即相同颜色只在连续的一段区间内。

思路： 颜色最多只有三种分布，在第一个栈底，在第一个栈顶和第二个栈底，在第二个栈底。颜色很少，枚举所有状态暴力即可。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 10;

char s[maxn];
int pos[maxn];
int id[maxn];
int tot = 0;

int sta[3];
int f[3];

bool check(char ch) {
	if (id[ch] == 1) {
		if (!f[1]) {
			f[1] = 1;
			sta[1] = ch;
			return true;
		}
		if (sta[1] == ch) return true;
		if (!f[2]) return false;
		sta[2] = ch;
		return true;
	}
	if (id[ch] == 2) {
		if (!f[1]) return false;
		sta[1] = ch;
		return true;
	}
	if (id[ch] == 3) {
		if (!f[2]) {
			f[2] = 1;
			sta[2] = ch;
			return true;
		}
		if (sta[2] == ch) return true;
		return false;
	}
}

int q[3] = {1, 2, 3};
void run () {
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	set<char> st;
	for (int i = 1; i <= len; ++i) {
		st.insert(s[i]);
	}
	if (st.size() <= 2) {
		puts("YES");
		return;
	}
	
	do {
		id['R'] = q[0];
		id['G'] = q[1];
		id['B'] = q[2];
		f[1] = f[2] = 0;
		for (int i = 1; i <= len; ++i) {
			if (!check(s[i])) break;
			if (i == len) {
				puts("YES");
				return;
			}
		}
	} while (next_permutation(q, q + 3));
	puts("NO");
}

int main () {
	int t = 1;
	while (t--) run();
	return 0;
}
/*
RGBGR

RGBGRGR

GRGRBGRGR
*/

L - Inscribed Circle

solved by Tryna.2:09(+)

题意： 求两个圆相交区域中最大的圆。

题解： 求两圆心的连线和圆的交点即可，一共有两对交点，找距离近的那对交点。好像用计算几何板子写得麻烦了，其实可以直接算的。新圆的半径就是两圆的半径减去两圆心距离除二，圆心就按两半径等比例计算即可。一看到这种题目都没思考了直接上板子了。

AC代码

#include<bits/stdc++.h>

using namespace std;
const double eps = 1e-10;

const int maxn = 2e5 + 10;

int sgn(double x) {
	if(fabs(x) < eps) return 0;
	if(x < 0) return -1;
	else return 1;
}

struct Point{
	double x, y;
	Point(){};
	Point(double _x, double _y) {
		x = _x;
		y = _y;
	}
	Point operator - (const Point &b)const{
		return Point(x - b.x, y - b.y);
	}
	Point operator + (const Point &b)const{
		return Point(x + b.x, y + b.y);
	}
	double operator ^ (const Point &b) const{
		return x * b.y - y * b.x;
	}
	double operator * (const Point &b)const{
		return x * b.x + y * b.y;
	}
	Point operator * (const double &k)const{
		return Point(x * k, y * k);
	}
	Point operator / (const double &k)const{
		return Point(x / k, y / k);
	}	
	double len() {
		return hypot(x, y);
	}
	double len2() {
		return x * x + y * y;
	}
	double distance(Point p) {
		return hypot(x - p.x, y - p.y);
	}
	Point trunc(double r) {
		double l = len();
		if(!sgn(l)) return *this;
		r /= l;
		return Point(x * r, y * r);
	}
	Point rotleft() {
		return Point(-y, x);
	}
	Point rotright() {
		return Point(y, -x);
	}
	
};

struct Line{
	Point s, e;
	Line(){}
	Line(Point _s, Point _e) {
		s = _s;
		e = _e;
	}
	double length() {
		return s.distance(e);
	}
	double dispointtoline(Point p) {
		return fabs((p - s) ^ (e - s)) / length();
	}
	Point lineprog(Point p) {
		return s + (((e - s) * ((e - s) * (p - s))) / ((e - s).len2()) );
	}
	Point crosspoint(Line v) {
		double a1 = (v.e - v.s) ^ (s - v.s);
		double a2 = (v.e - v.s) ^ (e - v.s);
		return Point((s.x * a2 - e.x* a1) / (a2 - a1), (s.y * a2 - e.y* a1) / (a2 - a1));
	}
};

struct circle{
	Point p;
	double r;
	circle(){}
	circle(Point _p, double _r) {
		p = _p;
		r = _r;
	}
	void pointcrosscircle(circle v, Point &p1, Point &p2) {
		double d = p.distance(v.p);
		double l = (d * d + r * r - v.r * v.r) / (2 * d);
		double h = sqrt(r * r - l * l);
		Point tmp = p + (v.p - p).trunc(l);
		p1 = tmp + ((v.p - p).rotleft().trunc(h));
		p2 = tmp + ((v.p - p).rotright().trunc(h));
	}
	void pointcrossline(Line v, Point &p1, Point &p2) {
		Point a = v.lineprog(p);
		double d = v.dispointtoline(p);
		d = sqrt(r * r - d * d);
		p1 = a + (v.e - v.s).trunc(d);
		p2 = a - (v.e - v.s).trunc(d); 
	}
}c1, c2;

void run () {
	double xx, yy, rr;
	scanf("%lf %lf %lf", &xx, &yy, &rr);
	c1 = circle(Point(xx, yy), rr);
	scanf("%lf %lf %lf", &xx, &yy, &rr);
	c2 = circle(Point(xx, yy), rr);	
	Point p1, p2;
	c1.pointcrosscircle(c2, p1, p2);
	Line l = Line(p1, p2);
	Line l1 = Line(c1.p, c2.p);
	Point P[10];
	c1.pointcrossline(l1, P[1], P[2]);
	c2.pointcrossline(l1, P[3], P[4]);
	Point pp1, pp2;
	pp1 = P[1];
	pp2 = P[4];
	if(P[1].distance(P[4]) > P[2].distance(P[3])) {
		pp1 = P[2];
		pp2 = P[4];
	}
	Point res = Point((pp1.x + pp2.x) / 2.0, (pp1.y + pp2.y) / 2.0);
//	printf("%f %f\n", res.x, res.y);
	double resr = res.distance(pp1);
	printf("%.15f %.15f %.15f\n", res.x, res.y, resr);
//	for(int i = 1; i <= 4; i++)
//		printf("%f %f\n", P[i].x, P[i].y);
}

int main () {
	int t = 1;
//	scanf("%d", &t);
	while (t--) run();
	return 0;
}

M - Shlakoblock is live!

solved by Tryna.2:36(+)

题意： 有$n$个游戏，每个游戏都有一个$p$值和$v$投票的人数，现在只剩下我需要对游戏进行投票，使得$p$最后的期望最高。

题解： 水题，结构体排个序即可。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 10;

int gcd(int a, int b) {
	return a == 0 ? b : gcd(b % a, a);
}

struct node{
	int v, p, id;
	bool operator < (const node &r) {
		return p > r.p;
	}
}a[maxn];

int n;

void run () {
	scanf("%d", &n);
	int fm = 0, fz = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &a[i].p, &a[i].v);
		fm += a[i].v;
		fz += a[i].p * a[i].v;
		a[i].id = i;
	}
	double res = (fz * 1.0) / (fm * 1.0);
	int k = 0;
	set<int>s;
	sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; i++) {
		fm += 1;
		fz += a[i].p;
		double now = (fz * 1.0) / (fm * 1.0);
		if(now <= res) {
			fm -= 1;
			fz -= a[i].p;
			break;
		}
		res = now;
		s.insert(a[i].id);
		k++;
	}
	int tmp = gcd(fz, fm);
	fz /= tmp;
	fm /= tmp;
	printf("%d/%d\n%d\n", fz, fm, k);
	for(auto g : s) {
		printf("%d ", g);
	}
	puts("");
}

int main () {
	int t = 1;
	scanf("%d", &t);
	while (t--) run();
	return 0;
}