#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int tests;
	cin >> tests;
	while (tests--) {
		int n;
		cin >> n;

		vector<int> cnt(26);
		for (int i = 0; i < n; ++i) {
			string s;
			cin >> s;
			for (char ch : s) {
				++cnt[ch - 'a'];
			}
		}

		bool ans = true;
		for (int i = 0; i < 26; ++i) {
			if (cnt[i] % n != 0) {
				ans = false;
				break;
			}
		}

		cout << (ans ? "YES" : "NO") << endl;
	}
}

numTests = int(input())
for testNo in range(numTests):
	n = int(input())
	cnt = [0 for i in range(26)]
	for _ in range(n):
	    s = input()
	    for i in s:
	        cnt[ord(i) - 97] += 1

	ans = True
	for i in range(26):
	    if cnt[i] % n != 0:
	        ans = False
	        break

	if ans:
	    print('YES')
	else:
	    print('NO')

Note that the cost the transform $$$a_i$$$ to $$$c^i$$$ is $$$\lvert a_i - c^i \rvert$$$. While there is a pair $$$(a_i, a_j)$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$, swap $$$a_i$$$ and $$$a_j$$$. Since $$$\lvert x \rvert + \lvert y \rvert = max \{ \lvert x + y \rvert, \lvert x - y \rvert \}$$$, we have

$$$\lvert a_i - c^i \rvert + \lvert a_j - c^j \rvert$$$

$$$= max \{ \lvert (a_i + a_j) - (c^i + c^j) \rvert, \lvert (a_i - a_j) - (c^i - c^j) \rvert \}$$$

$$$\ge max \{ \lvert (a_j + a_i) - (c^i + c^j) \rvert, \lvert (a_j - a_i) - (c^i - c^j) \rvert \}$$$

$$$= \lvert a_j - c^i \rvert + \lvert a_i - c^j \rvert$$$

when $$$a_i > a_j$$$ and $$$c^i \le c^j$$$, so the total cost does not increase. Hence, it is best to have $$$a_0 \le a_1 \le \cdots \le a_{n-1}$$$.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

const int64_t INF = 1e17;
inline int64_t mul(int64_t a, int64_t b)
{
	return (INF / a > b ? a * b : INF);
}

inline int64_t add(int64_t a, int64_t b)
{
	return (a + b >= INF ? INF : a + b);
}

int main()
{
	int n;
	cin >> n;

	vector<int> a(n);
	for (int &x : a) cin >> x;
	sort(a.begin(), a.end());

	if (n <= 2) {
		cout << a[0] - 1 << endl;
	} else {
		int64_t ans = accumulate(a.begin(), a.end(), 0ll) - n;

		for (int x = 1; ; ++x) {
			int64_t curPow = 1, curCost = 0;
			for (int i = 0; i < n; ++i) {
				curCost = add(curCost, abs(a[i] - curPow));
				curPow = mul(curPow, x);
			}

			if (curPow == INF || curPow / x > ans + a[n - 1]) break;
			ans = min(ans, curCost);
		}

		cout << ans << endl;
	}
}

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
inf = 10**18

if n <= 2:
    print(a[0] - 1)
else:
    ans = sum(a) - n

    for x in range(1, 10**9):
        curPow = 1
        curCost = 0
        for i in range(n):
            curCost += abs(a[i] - curPow)
            curPow *= x
            if curPow > inf:
                break

        if curPow > inf:
            break
        if curPow / x > ans + a[n - 1]:
            break

        ans = min(ans, curCost)

    print(ans)

$$$1 \space \space 1$$$
$$$0$$$
$$$1 \space \space 1$$$
$$$0$$$
$$$1 \space \space 1$$$
$$$-a_1$$$

$$$1 \space \space 1$$$
$$$-a_1$$$
$$$1 \space \space n$$$
$$$0, \space -n \cdot a_2, \space -n \cdot a_3, \space \dots , \space -n \cdot a_n$$$
$$$2 \space \space n$$$
$$$(n-1) \cdot a_2, \space (n-1) \cdot a_3, \space \dots , \space (n-1) \cdot a_n$$$

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int N;
   cin >> N;
   vector<ll> A(N);
   for (int i = 0; i < N; ++i) cin >> A[i];
   if (N == 1) {
      for (int z = 0; z < 3; ++z) {
         cout << "1 1\n";
         cout << -A[0] << "\n";
         A[0] = 0;
      }
      return 0;
   }
   cout << "1 " << N << "\n";
   for (int i = 0; i + 1 < N; ++i) cout << -A[i] * N << " "; cout << "0\n";
   cout << "1 " << N - 1 << "\n";
   for (int i = 0; i + 1 < N; ++i) cout << A[i] * (N - 1) << " "; cout << "\n";
   cout << N << " " << N << "\n";
   cout << -A[N - 1] << "\n";
   return 0;
}

n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print('1 1', -a[0], '1 1', '0', '1 1', '0', sep='\n')
    exit(0)

print(1, n)
for i in range(n):
    print(-a[i] * n, end = ' ')
    a[i] -= a[i] * n
print()

print(1, n - 1)
for i in range(n - 1):
    print(-a[i], end = ' ')
    a[i] = 0
print()

print(2, n)
for i in range(1, n):
    print(-a[i], end = ' ')
    a[i] = 0
print()

Let us prove by induction:

When $$$S = 0$$$, the second player obviously wins.

When $$$S \geq 2$$$, consider the game state after the first player moves. If there is a pile that now has more than $$$\lfloor \frac{S}{2} \rfloor$$$ stones, then we arrive back at case A where the next player to move wins. Otherwise, the second player can choose from any valid pile (note that the case condition implies that there are at least two non-empty piles before the first player's move). Now $$$S$$$ has been reduced by $$$2$$$, and every pile still has at most $$$\lfloor \frac{S}{2} \rfloor$$$ stones.

The condition allows us to assign a perfect matching of stones, where one stone is matched with exactly one stone from a different pile.

A greedy way to create such a matching: Give each label $$$0, 1, \dots, S - 1$$$ to a different stone so that for every pair of stones with labels $$$l < r$$$ that are from the same pile, stones $$$l + 1, l + 2, \dots, r - 1$$$ are also from that pile; then match stones $$$i$$$ with $$$i + \frac{S}{2}$$$ for all $$$0 \le i < \frac{S}{2}$$$.

For every stone that the first player removes, the second player can always remove its matching stone, until the first player can no longer make a move and loses.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;

		vector<int> a(n);
		for (int &x : a) cin >> x;

		int maxPile = *max_element(a.begin(), a.end());
		int numStones = accumulate(a.begin(), a.end(), 0);

		if (maxPile * 2 > numStones || (numStones & 1)) cout << "T" << endl;
		else cout << "HL" << endl;
	}
}

t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(x) for x in input().split()]

    maxPile = max(a)
    numStones = sum(a)

    if maxPile * 2 > numStones or (numStones & 1):
        print('T')
    else:
        print('HL')

/*input
4 2 4 4 1
4 5 1 2
*/
#include <bits/stdc++.h>
using namespace std;

int read() {
	int x = 0, c = getchar();
	for(; !(c > 47 && c < 58); c = getchar());
	for(; (c > 47 && c < 58); c = getchar()) x = x * 10 + c - 48;
	return x;
}

void upd(long long &a, long long b) {
	a = (a < b) ? a : b;
}

const int N = 1e6 + 5;

long long f[N][2];
int n, r1, r2, r3, d, a[N];

int main(){ 
	n = read(), r1 = read(), r2 = read(), r3 = read(), d = read();
	for(int i = 1; i <= n; a[i ++] = read());

	for(int i = 2; i <= n; ++ i) f[i][0] = f[i][1] = 1e18;

	f[1][0] = 1ll * r1 * a[1] + r3;
	f[1][1] = min(0ll + r2, 1ll * r1 * a[1] + r1);
	for(int i = 1; i < n; ++ i) {
		// 0 -> 0
		// so we clear this one and the next one as well
		upd(f[i + 1][0], f[i][0] + d + 1ll * r1 * a[i + 1] + r3);

		// 0 -> 1
		// this one is cleared, but next one isnt
		upd(f[i + 1][1], f[i][0] + d + min(0ll + r2, 1ll * r1 * a[i + 1] + r1));
		
		// 1 -> 0
		upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r3 + 2 * d + r1);
		upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r1 + d + r1 + d + r1);
		upd(f[i + 1][0], f[i][1] + d + r2 + d + r1 + d + r1);

		// 1 -> 1
		upd(f[i + 1][1], f[i][1] + d + r2 + d + r1 + d);
		upd(f[i + 1][1], f[i][1] + d + 1ll * r1 * a[i + 1] + r1 + d + r1 + d);

		if(i == n - 1) {
			upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r3 + d + r1);
		}
	}
	cout << f[n][0] << endl;
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MOD = 1000000007;

int L;
ll sum[8040];
int len[8040];
int last[8040];
int lazy[8040];

void init(int v, int l, int r, const vector<int> &xs) {
   len[v] = xs[r] - xs[l - 1];
   if (l < r) {
      int md = (l + r) >> 1;
      init(v << 1, l, md, xs);
      init(v << 1 | 1, md + 1, r, xs);
   }
}

void reset(int v, int l, int r, const vector<int> &go) {
   lazy[v] = -1;
   if (l == r) {
      sum[v] = ll(len[v]) * (L - go[l]);
      last[v] = go[l];
      return;
   }
   int md = (l + r) >> 1;
   reset(v << 1, l, md, go);
   reset(v << 1 | 1, md + 1, r, go);
   sum[v] = sum[v << 1] + sum[v << 1 | 1];
   last[v] = last[v << 1 | 1];
}

void push(int v, int l, int r) {
   if (lazy[v] != -1) {
      last[v] = lazy[v];
      sum[v] = ll(len[v]) * (L - lazy[v]);
      if (l < r) {
         lazy[v << 1] = lazy[v];
         lazy[v << 1 | 1] = lazy[v];
      }
      lazy[v] = -1;
   }
}

void modify(int v, int l, int r, int L, int R, int qv) {
   push(v, l, r);
   if (L > r || R < l) return;
   if (L <= l && r <= R) {
      lazy[v] = qv;
      push(v, l, r);
      return;
   }
   int md = (l + r) >> 1;
   modify(v << 1, l, md, L, R, qv);
   modify(v << 1 | 1, md + 1, r, L, R, qv);
   sum[v] = sum[v << 1] + sum[v << 1 | 1];
   last[v] = last[v << 1 | 1];
}

int walk(int v, int l, int r, int qv) {
   push(v, l, r);
   if (last[v] <= qv) return -1;
   if (l == r) return l;
   int md = (l + r) >> 1;
   int ans = walk(v << 1, l, md, qv);
   if (ans == -1) ans = walk(v << 1 | 1, md + 1, r, qv);
   return ans;
}

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int N, K; cin >> N >> K >> L;
   vector<int> X(N), Y(N), C(N);
   vector<int> xs = {-1, L};
   vector<int> ys = {-1, L};
   for (int i = 0; i < N; ++i) {
      cin >> X[i] >> Y[i] >> C[i];
      --C[i];
      xs.emplace_back(X[i]);
      ys.emplace_back(Y[i]);
   }
   sort(xs.begin(), xs.end());
   xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
   sort(ys.begin(), ys.end());
   ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
   int NX = xs.size();
   int NY = ys.size();
   {
      vector<int> order(N);
      iota(order.begin(), order.end(), 0);
      sort(order.begin(), order.end(), [&](int i, int j) {
         return make_pair(Y[i], -X[i]) > make_pair(Y[j], -X[j]);
      });
      vector<int> newX(N), newY(N), newC(N);
      for (int i = 0; i < N; ++i) {
         newX[i] = X[order[i]];
         newY[i] = Y[order[i]];
         newC[i] = C[order[i]];
      }
      X.swap(newX), Y.swap(newY), C.swap(newC);
   }
   init(1, 1, NX - 2, xs);
   int ans = 0;
   for (int yr = 1; yr + 1 < NY; ++yr) {
      vector<vector<int>> addAt(NX);
      for (int i = 0; i < N; ++i) {
         if (Y[i] <= ys[yr]) {
            int xi = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
            addAt[xi].emplace_back(C[i]);
         }
      }
      int bad = K;
      vector<int> cnts(K);
      auto inc = [&](int z) {
         if (++cnts[z] == 1) --bad;
      };
      auto dec = [&](int z) {
         if (--cnts[z] == 0) ++bad;
      };
      vector<int> go(NX);
      int ptr = 0;
      for (int i = 1; i + 1 < NX; ++i) {
         while (bad && ptr + 2 < NX) {
            ptr++;
            for (int z : addAt[ptr]) inc(z);
         }
         if (bad) go[i] = L;
         else go[i] = xs[ptr];
         for (int z : addAt[i]) dec(z);
      }
      reset(1, 1, NX - 2, go);
      vector<int> prv(N);
      vector<int> nxt(N);
      vector<map<int, int>> mp(K);
      for (int i = 0; i < N; ++i) {
         if (Y[i] <= ys[yr]) {
            auto it = mp[C[i]].lower_bound(X[i]);
            if (it == mp[C[i]].end()) {
               nxt[i] = -1;
            } else {
               nxt[i] = it->second;
            }
            it = mp[C[i]].upper_bound(X[i]);
            if (it == mp[C[i]].begin()) {
               prv[i] = -1;
            } else {
               prv[i] = prev(it)->second;
            }
            mp[C[i]][X[i]] = i;
         }
      }
      auto remove = [&](int i) {
         int xprv = (prv[i] == -1 ? -1 : X[prv[i]]);
         int xcur = X[i];
         int xnxt = (nxt[i] == -1 ? L : X[nxt[i]]);
         int l =  lower_bound(xs.begin(), xs.end(), xprv) - xs.begin() + 1;
         int r = walk(1, 1, NX - 2, xnxt);
         if (r == -1) r = NX - 1; --r;
         r = min(r, int(lower_bound(xs.begin(), xs.end(), xcur) - xs.begin()));
         if (l <= r) modify(1, 1, NX - 2, l, r, xnxt);
      };
      ptr = N - 1;
      for (int yl = 1; yl <= yr; ++yl) {
         ll add = sum[1] % MOD * (ys[yr + 1] - ys[yr]) % MOD * (ys[yl] - ys[yl - 1]) % MOD;
         ans = (ans + add) % MOD;
         while (ptr >= 0 && Y[ptr] == ys[yl]) remove(ptr--);
      }
      assert(sum[1] == 0);
   }
   cout << ans << "\n";
   return 0;
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int N; ll K;
   cin >> N >> K;
   vector<vector<int>> adj(N);
   for (int i = 0; i < N - 1; ++i) {
      int v, u;
      cin >> v >> u;
      adj[--v].emplace_back(--u);
      adj[u].emplace_back(v);
   }
   vector<int> sz(N);
   function<void(int, int)> dfs1 = [&](int v, int p) {
      sz[v] = 1;
      for (int u : adj[v]) if (u != p) {
         dfs1(u, v);
         sz[v] += sz[u];
      }
   };
   dfs1(0, -1);
   int root = 0;
   for (int i = 1; i < N; ++i) {
      if (sz[i] >= N / 2 && sz[i] < sz[root]) root = i;
   }
   vector<int> dist(N);
   vector<int> top(N, -1);
   vector<int> par(N, -1);
   ll low = 0, high = 0;
   function<void(int, int, int)> dfs2 = [&](int v, int p, int r) {
      dist[v] = dist[p] + 1;
      top[v] = r;
      par[v] = p;
      {
         auto it = find(adj[v].begin(), adj[v].end(), p);
         assert(it != adj[v].end());
         adj[v].erase(it);
      }
      sz[v] = 1;
      for (int u : adj[v]) {
         dfs2(u, v, r);
         sz[v] += sz[u];
      }
      low += (sz[v] & 1);
      high += sz[v];
   };
   for (int v : adj[root]) {
      dfs2(v, root, v);
   }
   if (low > K || high < K || (high - K) % 2) {
      cout << "NO\n";
      return 0;
   }
   set<pair<int, int>> sizes;
   for (int v : adj[root]) {
      sizes.emplace(sz[v], v);
   }
   vector<set<pair<int, int>>> lcas(N);
   vector<int> deg(N);
   for (int v = 0; v < N; ++v) deg[v] = adj[v].size();
   for (int v = 0; v < N; ++v) if (v != root) {
      if (deg[v] == 0) {
      } else {
         lcas[top[v]].emplace(dist[v], v);
      }
   }
   vector<bool> matched(N);
   function<void(int)> kill = [&](int v) {
      assert(deg[v] == 0);
      if (--deg[par[v]] == 0) {
         v = par[v];
         lcas[top[v]].erase(pair<int, int>(dist[v], v));
      }
   };
   cout << "YES\n";
   while (high > K) {
      assert(sizes.size());
      int v = (--sizes.end())->second;
      sizes.erase(pair<int, int>(sz[v], v));
      assert(lcas[v].size());
      int mdist = (--lcas[v].end())->first;
      if (high - 2 * mdist <= K) {
         int x = lcas[v].lower_bound(pair<int, int>((high - K) / 2, -1))->second;
         int y = -1;
         for (int z : adj[x]) if (!matched[z]) {
            y = z;
            break;
         }
         high = K;
         cout << x + 1 << " " << y + 1 << "\n";
         matched[x] = true;
         matched[y] = true;
         break;
      } else {
         high -= 2 * mdist;
         assert(lcas[v].size());
         int u = (--lcas[v].end())->second;
         vector<int> nxts;
         while (nxts.size() < 2 && adj[u].size()) {
            int w = adj[u].back();
            adj[u].pop_back();
            if (!matched[w]) {
               nxts.emplace_back(w);
            }
         }
         if (nxts.size() < 2) nxts.emplace_back(u);
         assert(nxts.size() == 2);
         cout << nxts[0] + 1 << " " << nxts[1] + 1 << "\n";
         matched[nxts[0]] = true;
         matched[nxts[1]] = true;
         kill(nxts[0]);
         kill(nxts[1]);
         sz[v] -= 2;
         if (sz[v]) sizes.emplace(sz[v], v);
      }
   }
   vector<int> seq;
   function<void(int)> dfs3 = [&](int v) {
      if (!matched[v]) seq.emplace_back(v);
      for (int u : adj[v]) dfs3(u);
   };
   dfs3(root);
   int h = seq.size() / 2;
   for (int i = 0; i < h; ++i) {
      cout << seq[i] + 1 << " " << seq[i + h] + 1 << "\n";
   }
}