Znzryb's Blog

CF-1029-F. Wildflower

Posted on 2025-06-09 Edited on 2026-04-06

思路讲解

注意到，根据题设条件，树必须为严格的“Y”||”1”。

AC代码

源代码

// Problem: F. Wildflower  F. 野花
// Contest: Codeforces - Codeforces Round 1029 (Div. 3)Codeforces 第 1029 轮（第 3 组）
// URL: https://codeforces.com/contest/2117/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
/*

*/
vector<ll> g[MAXN];		// 记得要清空
ll vis[MAXN],dp[MAXN];
inline void init(){
	FOR(i,0,N+5){
		g[i].clear();
	}
	FOR(i,0,N+5){
		vis[i]=false;
	}
}
ll tNode=0,ls=0,rs=0;
ll dfs(ll node){
	ll ret=0;
	vis[node]=true;
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i];
		if(vis[lnode]) continue;
		ret+=dfs(lnode);
	}
	if(ret==0) ret=1;
	return ret;
}
ll sdfs(ll node){
	ll ret=1,up=0;
	vis[node]=true;
	ll cnt=0;
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i];
		if(vis[lnode]) continue;
		up=ret;
		ret+=sdfs(lnode);
		++cnt;
	}
	if(cnt==2){
		tNode=node;
		ls=up-1;
		rs=ret-up;
	}
	return ret;
}
ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N-1){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);g[v].pb(u);
	}
	ll ret=dfs(1);
	FOR(i,0,N+5){
		vis[i]=false;
	}
	if(ret==1){
		cout<<binpow(2,N,mod)<<"\n";
	}else if(ret==2){
		sdfs(1);
		ll line=N-ls-rs;
		ll mx=max(ls,rs),mn=min(ls,rs);
		ll ans=binpow(2,line,mod)*binpow(2,mx-mn,mod);
		ans+=binpow(2,line,mod)*binpow(2,mx-mn-1,mod);
		// if(mx-mn-1>=0){ans+=binpow(2,line,mod)*binpow(2,mx-mn-1,mod);}
		ans%=mod;
		cout<<ans<<"\n";
#ifdef LOCAL
    debug(line);
    debug(ls);
    debug(rs);
#endif
	}else{
		cout<<0<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2117/submission/323644092
*/

心路历程（WA，TLE，MLE……）

注意，写两种dfs记得要清空vis数组。

CF-1027-F. Small Operations（通过选择1-K内的整数*和/使X==Y）

Posted on 2025-06-07 Edited on 2026-04-06

思路讲解

首先，遇到数论问题不要怕，我们人类其实对许多数论问题其实都束手无策，就靠计算机枚举。

那么，通过素因数分解，不难发现，我们可以把问题转化为这个。

💡 Note: 给你一个序列，比如说1，2，2，3，5，你要将这个序列删空，你一次可以选择任意多的数，只要这些数的乘积小于K。要求你找到一个方式，使用最少删除次数，告诉我这个次数。

那么其实经过素因数分解得出的序列是不会有 1 的。

把xrem除掉，再乘上yrem，就相等了。

记忆化搜索的时间复杂度那基本上等于 $状态数\times入口数量$ ，这里的状态数量其实就是因数的数量，入口数量也是因数数量，所以最坏情况下时间复杂度为 $O(n^{\frac{2}{3}})$ 。

这个super composite number 就是因数数量特别多的数，比比他小的所有数的因数都多，那么这样的数大概因数数量也就是 $\sqrt[3]{n}$ 。

A highly composite number is a positive integer that has more divisors than all smaller positive integers. If d(n) denotes the number of divisors of a positive integer n, then a positive integer N is highly composite if d(N) > d(n) for all n < N. For example, 6 is highly composite because d(6)=4, and for n=1,2,3,4,5, you get d(n)=1,2,2,3,2, respectively, which are all less than 4.

ll dfs(ll val){
	if(dp[val]!=INF) return dp[val]+1;
	if(val==1) return 1;
	FOR(i,0,SZ(facs)-1){
		ll fac=facs[i];
		if(fac==1) continue;
		if(fac>K) break;
		if(val%fac==0) dp[val]=min(dp[val],dfs(val/fac));
	}
	return dp[val]+1;
}

那么问题的关键就在于减少入口，注意到只有因数是合法的。

AC代码

https://codeforces.com/contest/2114/submission/323597405

源代码

// Problem: F. Small Operations
// Contest: Codeforces - Codeforces Round 1027 (Div. 3)
// URL: https://codeforces.com/contest/2114/problem/F
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,Y,K,lT,A[MAXN];
/*

*/
inline ll gcd(ll a,ll b){
	if(a<b) swap(a,b);
	while(b){
		a%=b;
		swap(a,b);
	}
	return a;
}
namespace F{
	inline vector<ll> de(ll n){
		vector<ll> ret;
		for(ll i=1;i*i<=n;++i){
			if(n%i==0){
// #ifdef LOCAL
    // debug(i);
    // debug(n/i);
// #endif
				if(i!=1) ret.pb(i);
				if(i*i!=n) ret.pb(n/i);
// #ifdef LOCAL
    // FOR(i,0,SZ(ret)-1) debug(ret[i]);
// #endif
			}
		}
		sort(all(ret));
		return ret;
	}
};
namespace P{		// 质因数分解   时间复杂度sqrt(n)
	// AC https://www.luogu.com.cn/record/219974780
	typedef array<ll,2> arr2;
	
	inline vector<arr2>  de(ll n){		// 主函数
		if(n==1) return {{1,1}};	// 确保无论什么输入都不会返回空值
		vector<arr2> prime;
		ll opN=n;
		for(ll i=2;i*i<=n;++i){
			if(opN==1) break;
			ll cnt=0;
			while(opN%i==0 && opN!=1){
				opN/=i;
				++cnt;
			}
			if(cnt==0) continue;
			prime.pb({i,cnt});
		}
		if(opN!=1) prime.pb({opN,1});	// 素因子可能大于sqrt(n)，比如23，包括20的5
		return prime;
	}
	inline void print(const vector<arr2> &prime){	// 20 -> 2^2 * 5
		FOR(i,0,SZ(prime)-1){
			if(i==0){
				if(prime[i][1]==1) cout<<prime[i][0]<<" ";
				else cout<<prime[i][0]<<"^"<<prime[i][1]<<" ";
			}else{
				if(prime[i][1]==1) cout<<"* "<<prime[i][0]<<" ";
				else cout<<"* "<<prime[i][0]<<"^"<<prime[i][1]<<" ";
			}
		}
	}
}
ll dp[MAXN];
vector<ll> facs;
vector<arr2> primes;
ll dfs(ll val){
	if(dp[val]!=INF) return dp[val]+1;
	if(val==1) return 1;
	FOR(i,0,SZ(facs)-1){
		ll fac=facs[i];
		if(fac==1) continue;
		if(fac>K) break;
		if(val%fac==0) dp[val]=min(dp[val],dfs(val/fac));
	}
	return dp[val]+1;
}

inline void init(ll n){
	FOR(i,0,SZ(facs)-1){dp[facs[i]]=INF;}
	dp[1]=0;
}
inline void solve(){
	cin>>X>>Y>>K;
	ll gxy=gcd(X,Y);
	ll xrem=X/gxy,yrem=Y/gxy;
	
	facs=F::de(xrem);
	init(xrem);
	primes=P::de(xrem);
	if(primes.back()[0]>K){
		cout<<-1<<"\n";
		return;
	}
// #ifdef LOCAL
    // cerr << "OK:"<<lT << '\n';
    // debug(xrem);
    // debug(K);
    // FOR(i,0,SZ(facs)-1) debug(facs[i]);
// #endif
	dfs(xrem);
// #ifdef LOCAL
    // cerr << "OK1:"<<lT << '\n';
// #endif
	ll ans=dp[xrem];
	
#ifdef LOCAL
	cerr<<"init:\n";
     FOR(i,0,SZ(facs)-1) {debug(facs[i]);debug(dp[facs[i]]);}
#endif
	facs=F::de(yrem);
	init(yrem);
	primes=P::de(yrem);
	if(primes.back()[0]>K){
		cout<<-1<<"\n";
		return;
	}
	dfs(yrem);
#ifdef LOCAL
    cerr << "OK2:"<<lT << '\n';
    FOR(i,0,SZ(facs)-1) {debug(facs[i]);debug(dp[facs[i]]);}
    // FOR(i,1,N){
    	// debug(i);
    // }
#endif
	ans+=dp[yrem];
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2114/submission/323597405
*/

心路历程（WA，TLE，MLE……）

CF-1027-E. Kirei Attacks the Estate

Posted on 2025-06-07 Edited on 2026-04-06

思路讲解

是比较简单的树上dp问题，记录一下。

void dfs(ll node,ll x0,ll x1,ll cnt){
	// x0表示cnt%2==0时加
	if(vis[node]) return;
	vis[node]=true;
	ans[node]= cnt%2==0?A[node]+x1:A[node]+x0;
	if(cnt%2==0){
		x0-=A[node];
		x1+=A[node];
	}
	if(cnt%2==1){
		x0+=A[node];
		x1-=A[node];
	}
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i];
		if(vis[lnode]) continue;
		dfs(lnode,max(0ll,x0),max(0ll,x1),cnt+1);
	}
}

AC代码

https://codeforces.com/contest/2114/submission/323228554

源代码

// Problem: E. Kirei Attacks the Estate
// Contest: Codeforces - Codeforces Round 1027 (Div. 3)
// URL: https://codeforces.com/contest/2114/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
vector<ll> g[MAXN];		// 记得要清空
bool vis[MAXN];
ll ans[MAXN];
ll mxx[2];
inline void init(){
	mxx[0]=0;mxx[1]=0;
	FOR(i,0,N+5){g[i].clear();vis[i]=false;}
}
//                         cnt 是指 node 是该 vertical path 上的第几个点
void dfs(ll node,ll x0,ll x1,ll cnt){
	// x0表示cnt%2==0时加
	if(vis[node]) return;
	vis[node]=true;
	ans[node]= cnt%2==0?A[node]+x1:A[node]+x0;
#ifdef LOCAL
    debug(node);
    debug(ans[node]);
    debug(x0);
    debug(x1);
    debug(A[node]);
#endif
	if(cnt%2==0){
		x0-=A[node];
		x1+=A[node];
	}
	if(cnt%2==1){
		x0+=A[node];
		x1-=A[node];
	}
#ifdef LOCAL
    debug(x0);
    debug(x1);
    cerr<<"\n";
#endif
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i];
		if(vis[lnode]) continue;
		dfs(lnode,max(0ll,x0),max(0ll,x1),cnt+1);
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){cin>>A[i];}
	FOR(i,1,N-1){
		ll u,v;cin>>u>>v;
		g[u].pb(v);g[v].pb(u);
	}
	// root=1;
	dfs(1,0,0,1);
	FOR(i,1,N){cout<<ans[i]<<" ";}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2114/submission/323228554
*/

心路历程（WA，TLE，MLE……）

Edu-179-E. Changing the String

Posted on 2025-06-04 Edited on 2026-04-06

思路讲解

感觉每次选择都可能有后效性怎么办？

1
2
3

// 碰到b,a   c,a operate 在最近的位置
// a,b  a,c   not operate
// b,c   c,b    operate or not?

仔细一想那，这道题目也没有那么复杂其实，其实只有b，c是需要考虑是否操作的。

只考虑那么一种情况的话，其实就看后面有没有c，a，而且b的前面c的数量啦。

https://www.cnblogs.com/fwdzh/p/18909502

这个题解告诉我们，我们是不可能在线处理的，这个难度是比较大的，但是我前面一直在想这个（QAQ）。

AC代码

https://codeforces.com/contest/2111/submission/322930903

源代码

// Problem: E. Changing the String
// Contest: Codeforces - Educational Codeforces Round 179 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2111/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
// #define getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
using arc2=array<char,2>;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(1e9)+9;	// 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
/*

*/
// arc2 opC[MAXN];
set<ll> g[50];	// 直接懒得上有序表了，直接用vector 吧 开摆
inline void solve(){
	cin>>N>>Q;
	FOR(i, 0, 50-1) g[i].clear();
	// g[0].clear();g[1].clear();g[2].clear();
	// set<arc2> opC;
	string s;
	cin>>s;
	// FOR(i,0,SZ(s)-1){
		// g[s[i]-'a'].pb(i);
	// }
	FOR(i,1,Q){
		char x,y;
		cin>>x>>y;
		g[(x-'a')*5+y-'a'].insert(i);
	}
	// 碰到b,a   c,a operate 在最近的位置
	// a,b  a,c   not operate
	// b,c   c,b    operate or not?
	FOR(i,0,N-1){		
		if(s[i]=='a'){
			continue;
		}
		// 2 'c' -> 'a'  'c'->'b'->'a'  'c'->'b'
		if(s[i]=='c'){
			char x='c',y='a';
			ll idx=(x-'a')*5+y-'a';
			if(!g[idx].empty()){
				// g[idx].pop_front();		// 后面的操作是需要b->c->a组合，所以尽量删前面的
				g[idx].erase(g[idx].begin());
				s[i]='a';
			}else{
				ll idx2=('c'-'a')*5+'b'-'a',idx3=('b'-'a')*5;
				if(g[idx2].empty()) continue;
				if(g[idx3].empty()){
					// g[idx2].pop_back();
					g[idx2].erase(prev(g[idx2].end()));
					s[i]='b';
				}else{
					if(*g[idx2].begin()<*g[idx3].rbegin()){
						// g[idx2].pop_front();
						auto it=g[idx3].lower_bound(*g[idx2].begin());
						g[idx2].erase(g[idx2].begin());
						g[idx3].erase(it);
						s[i]='a';
					}else{
						// g[idx2].pop_back();
						// s[i]='b';
						g[idx2].erase(g[idx2].begin());
						s[i]='b';
					}
				}
			}
		}else{		// 1'b'->'a' 'b'->'c'->'a'
			char x='b',y='a';
			ll idx=(x-'a')*5+y-'a';
			// if(!g[idx].empty()){
				// g[idx].pop_front(); // 后面的操作是需要'c'->'b'->'a'组合，所以尽量删前面的
				// s[i]='a';
			// }else{
				// ll idx2=('b'-'a')*5+'c'-'a',idx3=('c'-'a')*5;
				// if(g[idx2].empty()) continue;
				// if(g[idx3].empty()){
					// // g[idx2].pop_back();
					// // s[i]='b';
				// }else{
					// if(g[idx2].front()<g[idx3].back()){
						// g[idx2].pop_front();
						// g[idx3].pop_back();
						// s[i]='a';
					// }else{
// 						
					// }
				// }
			// }
			if(!g[idx].empty()){
				// g[idx].pop_front(); // 后面的操作是需要'c'->'b'->'a'组合，所以尽量删前面的
				g[idx].erase(g[idx].begin());
				s[i]='a';
			}else{
				ll idx2=('b'-'a')*5+'c'-'a',idx3=('c'-'a')*5;
				if(g[idx2].empty()) continue;
				if(g[idx3].empty()){
					// g[idx2].pop_back();
					g[idx2].erase(prev(g[idx2].end()));
					s[i]='b';
				}else{
					if(*g[idx2].begin()<*g[idx3].rbegin()){
						// g[idx2].pop_front();
						auto it=g[idx3].lower_bound(*g[idx2].begin());
						g[idx2].erase(g[idx2].begin());
						g[idx3].erase(it);
						s[i]='a';
					}
				}
			}
		}
	}
	cout<<s<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2111/submission/322930903
*/

心路历程（WA，TLE，MLE……）

那么我们发现，匹配应该是这样匹配，而不是用最大的匹配最小的。

if(*g[idx2].begin()<*g[idx3].rbegin()){
	// g[idx2].pop_front();
	auto it=g[idx3].lower_bound(*g[idx2].begin());
	g[idx2].erase(g[idx2].begin());
	g[idx3].erase(it);
	s[i]='a';
}

Edu-179-D. Creating a Schedule

Posted on 2025-06-04 Edited on 2026-04-06

思路讲解

这道D题确实不算太难，我赛时应该也是可以写出来的。

采用类似于下图的构造方式即可

AC代码

https://codeforces.com/contest/2111/submission/322856069

源代码

// Problem: D. Creating a Schedule  D. 创建时间表
// Contest: Codeforces - Educational Codeforces Round 179 (Rated for Div. 2)教育 Codeforces 第 179 轮（评级为 Div. 2）
// URL: https://codeforces.com/contest/2111/problem/D
// Memory Limit: 512 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
// #define getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9;	// 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
// ll ans[MAXN][MAXN];
/*

*/

inline void solve(){
	scanf("%lld%lld",&N,&M);
	FOR(i,1,M){
		ll num;
		scanf("%lld",&A[i]);
		// A[i]=num/100;
	}
	sort(A+1,A+1+M);
	ll beg=0,ed=M+1;
	FOR(i,1,N){
		if(i%2==1){
			++beg;--ed;
			FOR(j,1,6){
				if(j%2==1) printf("%lld ",A[beg]);
				else printf("%lld ",A[ed]);
			}
			printf("\n");
		}else{
			FOR(j,1,6){
				if(j%2==1) printf("%lld ",A[ed]);
				else printf("%lld ",A[beg]);
			}
			printf("\n");
		}
		
	}
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	scanf("%lld",&lT);
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2111/submission/322856069
*/