void execute(int test_number)
{
  cin>>n>>k>>str;
  vector <int> count_char(26, 0);
  for (char c: str) count_char[c - 'a']++;
  string ans = "";
  for (int i = 0; i < min(25, n/k); i++) {
    while (k - ans.size() > count_char[i]) {
      ans.push_back(i + 'a');
    }
  }

  char c = 'a' + min(n / k, 25);
  while (k > ans.size()) {
    ans += c;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << "\n";
}
...

...
ll l, r;

ll bs_sqrt(ll x) {
  ll left = 0, right = 2000000123;
  while (right > left) {
      ll mid = (left + right) / 2;
      
      if (mid * mid > x) right = mid;
      else left = mid + 1;
  }
  return left - 1;
}

// main solution goes here:
void execute(int test_number)
{
  cin >> l >> r;
  ll sql = bs_sqrt(l), sqr = bs_sqrt(r);
  ll ans;
  if (sql == sqr) {
    ans = 0;
    for (int i = 0; i < 3; i++) {
      if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;
    }
  } else {
    ans = (sqr - sql - 1) * 3;
    for (int i = 0; i < 3; i++) {
      if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;
      if (l <= sqr * (sqr + i) && sqr * (sqr + i) <= r) ans++;
    }
  }
  cout << ans << "\n";
}
...

...
int n;
int x[3], y[3];
int u, v;

pii centralSquare() {
  int a = (x[0] == x[1]) ? x[0] : x[2];
  int b = (y[0] == y[1]) ? y[0] : y[2];
  return {a, b};
}
// main solution goes here:
void execute(int test_number)
{
  cin>>n;
  for (int i=0; i<3; i++) cin>>x[i]>>y[i];
  cin>>u>>v;

  int cx = centralSquare().first, cy = centralSquare().second;

  if ((cx == 1 || cx == n) && (cy == 1 || cy == n)) { // "corner" case, literally
    // the crickets can only reach coordinates within the edges that already contains at least 2 crickets,
    // which contains the centralSquare of the L
    cout << ((u == cx || v == cy) ? "YES\n" : "NO\n");
  } else {
    if ((cx + cy) % 2 == (u + v) % 2) {
      cout << (cx % 2 == u % 2 ? "YES\n" : "NO\n"); 
    } else { // can be prove to always reach, since we have ways to align 2 crickets in the same diagonal as target
      cout << "YES\n"; 
    }
  }
}
...

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define ull unsigned long long
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

#define pper(a) cerr << #a << " = " << a << endl;

void per() { cerr << endl; }
template<typename Head, typename... Tail> void per(Head H, Tail... T) { cerr << H << ' '; per(T...); }

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

template<class U, class V> 
ostream& operator<<(ostream& out, const pair<U, V>& a) {
  return out << "(" << a.x << ", " << a.y << ")";
}

template<class U, class V> 
istream& operator>>(istream& in, pair<U, V>& a) {
  return in >> a.x >> a.y;
}

template<typename W, typename T = typename enable_if<!is_same<W, string>::value, typename W::value_type>::type>
ostream& operator<<(ostream& out, const W& v) { out << "{ "; for (const auto& x : v) out << x << ", "; return out << '}'; }

template<class T>
void readArr(T from, T to) {
  for (auto i = from; i != to; ++i) cin >> *i;
}

mt19937 mrand(1337); 
unsigned int myRand32() {
  return mrand() & (unsigned int)(-1);
}
 
unsigned ll myRand64() {
  return ((ull)myRand32() << 32) ^ myRand32();
}

const int mod = 1000000007;

void add(int& a, int b) {
  a += b; if (a >= mod) a -= mod;
}

void dec(int &a, int b) {
  a -= b; if (a < 0) a += mod;
}

int mult(int a, int b) {
  return a * (ll)b % mod;
}

int bp(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}

const int N = 507;

ll f[N][N];

int main(){
#ifdef LOCAL
	freopen("N_input.txt", "r", stdin);
	//freopen("N_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

  int t;
  cin >> t;

  for (int a = 0; a < t; ++a) {

    int n, m;
    cin >> n >> m;

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

    vector<tuple<int, int, int> > ed;

    for (int i = 0; i < m; ++i) {
      int u, v, w;
      cin >> u >> v >> w;
      ed.pb(make_tuple(u - 1, v - 1, w));
      f[u - 1][v - 1] = 1;
      f[v - 1][u - 1] = 1;
    }

    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        }
      }
    }

    ll ans = 1e18;
    for (auto x : ed) {
      int u = get<0>(x);
      int v = get<1>(x);
      int w = get<2>(x);

//      per(ans, u, v, w);

      ans = min(ans, (ll) w * (f[0][u] + f[n - 1][v] + 1));
      ans = min(ans, (ll) w * (f[0][v] + f[n - 1][u] + 1));

  //    per(ans, u, v, w);

      for (int i = 0; i < n; ++i) {
        ans = min(ans, (ll) w * (f[v][i] + 1 + f[i][0] + f[i][n-1] + 1));
        ans = min(ans, (ll) w * (f[u][i] + 1 + f[i][0] + f[i][n-1] + 1));
      }

    }

    cout << ans << '\n';

  }
}

#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
#include<set>
#include<map>
#include<bitset>
#include<ctime>
#include<queue>
using namespace std;
#define ll long long
#define pii pair <ll, ll>
#define ld long double
#define XX first
#define YY second
#define mattype ll
#define matrix vector <vector <mattype> >
 
// constants:
const int mn = 1000005;
const int mod = 1000000007;
const long long inf = 4444444444444444444;
const int sminf = 1111111111;
const bool is_multitest = 1;
const bool is_interactive = 0;
 
// i/o methods:
const bool input_from_file = 0;
const bool output_to_file = 0;
#define filename ""
#define in_extension "inp"
#define out_extension "out"
 
// debug functions
void debug_vector(string name, vector <ll> v) {
  cerr << name << " @size=" << v.size() << ": [";
  for (int x: v) cerr << x << " ";
  cerr << "]\n";
}
 
void debug_2d_vector(string name, vector <vector<ll> > v) {
 
  cerr << name << " @size=" << v.size() << ": {\n";
  for (int i = 0; i < v.size(); i++) {
    cerr << "\t";
    debug_vector(name + "[" + to_string(i) + "]", v[i]);
  }
  cerr << "}\n";
}
 
// data preprocessing: (e.g.: divisor generating, prime sieve)
ll POW2[mn];
void preprocess()
{
  POW2[0] = 1;
  for (int i = 1; i < mn; i++) POW2[i] = POW2[i &mdash; 1] * 2 % mod;
}
 
// global variables:
ll n;
 
ll POW(ll u, ll v) {
  if (v == 0) return 1;
  ll mid = POW(u, v / 2);
  mid = (mid * mid) % mod;
  return (v & 1) ? (mid * u % mod) : mid;
}
// main solution goes here:
void execute(int test_number)
{
  cin>>n;
 
  if (n == 1) {
    cout << "1\n";
    return;
  }
  vector <ll> ans(n + 1, 0), sufsum(n + 1, 0);
  sufsum[n] = ans[n] = POW(POW2[(n &mdash; 1) / 2], mod &mdash; 2);
  for (int i = n &mdash; 1; i > 1; i--) {
    ans[i] = POW(POW2[(i + 1) / 2], mod &mdash; 2);
    if (2 * i <= n) ans[i] = ans[i] * (1 &mdash; sufsum[i * 2] + mod) % mod;
    sufsum[i] = (sufsum[i + 1] + ans[i]) % mod;
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
 
}
// REMEMBER TO CHOOSE TEST METHODS
// PLEASE REMOVE cout AND cerr DEBUG LINES BEFORE SUBMITTING PROBLEMS
// Solution by low_

signed main()
{
#ifdef lowie
    if (!is_interactive)
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
#else
    if (input_from_file) freopen(filename"."in_extension, "r", stdin);
    if (output_to_file) freopen(filename"."out_extension, "w", stdout);
#endif
    if (!is_interactive)
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
 
    preprocess();
    int ntest;
    if (is_multitest) cin >> ntest;
    else ntest = 1;
 
    for (int testno = 1; testno <= ntest; testno++)
    // use for instead of while to serve facebook hacker cup test format
    {
        execute(testno); // only start coding in this function, not in main
    }
}
// Template by low_
// Contact me via mail: ttuandung1803@gmail.com
// ...or codeforces: www.codeforces.com/profiles/low_
// ...or if you're interested in food: www.instagram.com/lowie.exe/

Observation: Assume that x is composite number and divisor of n. Among all the multiples of x, the number of the divisor of n must be less than or equal to m/2.

First, factorize n. Assume that w is divisor of n. If w is in the form of a^4, a^3b^2, or a^2b^2c^2, it can be proved that there is no answer. Otherwise, there can be two cases.

If the possible maximum exponent of prime factor is 2, place the divisors like this: 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a. And expand the sequence as follows:

1. Repeat the current sequence twice — 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a 1 a^2 a.
2. Multiply the odd-indexed elements of first half and the even-indexed elements of second half by the new prime factor. Index 1 is exception — 1 a^2b^2 bc a^2b b^2c ab a^2c ab^2 ac c a^2b^2c b a^2bc b^2 abc a^2 ab^2c a / 1 a^2 ab b a^2b a.
3. If more prime factor exists, jump to "Otherwise".

Otherwise, place the divisors like this: 1 a^3 a a^2 / 1 a. Now the exponents of other prime factors are all 1, and we can expand the sequence as follows:

1. Repeat the current sequence twice — 1 a^3 a a^2 1 a^3 a a^2 / 1 a 1 a.
2. Multiply the even-indexed elements of first half and the odd-indexed elements of second half by the new prime factor — 1 a^3b a a^2b b a^3 ab a^2 / 1 ab b a. 3-1. If the maximum exponent is 3, swap a and b — 1 a^3b b a^2b a a^3 ab a^2 3-2. Otherwise, swap b and ab — 1 b ab a.

Like this, we can expand the sequence

import<bits/stdc++.h>

define endl '\n'

using namespace std;

int m, t, b[18], check[18], cnt[5]; vectorv; vector<vector>a;

void initialize(int m) { fill(b, b + m + 1, 0); fill(check, check + m + 1, 0); fill(cnt, cnt + 5, 0); v.clear(); a.clear(); } void insert1(int p1, int c1) { v[p1] = c1; a.push_back(v); } void insert2(int p1, int p2, int c1, int c2) { v[p1] = c1; v[p2] = c2; a.push_back(v); }

void f1(int x) { int n = a.size(); for(int i = 0; i < n; i++)a.push_back(a[i]); for(int i = 0; i < n; i += 2) { a[i + 1][x] = 1; a[i + n][x] = 1; } swap(a[n / 2], a[n]); } void f2(int x) { int n = a.size(); for(int i = 0; i < n; i++)a.push_back(a[i]); for(int i = 1; i < n; i += 2) { a[i + 1][x] = 1; a[i + n][x] = 1; } a[n][x] = 1; } void f3(int x) { int n = a.size(); for(int i = 0; i < n; i++)a.push_back(a[i]); for(int i = 0; i < n; i += 2) { a[i + 1][x] = 1; a[i + n][x] = 1; } swap(a[n], a[2 * n — 1]); }

int main() { ios::sync_with_stdio(0); cin.tie(0); for(cin >> t; t--;) { cin >> m; for(int i = 1; i <= m; i++) { cin >> b[i]; cnt[min(b[i], 4)]++; } if(cnt[4] || cnt[3] >= 2 || cnt[3] && cnt[2] || cnt[2] >= 3) { cout << -1 << endl; initialize(m); continue; }

    for(int i = 1; i <= m; i++)v.push_back(0);
    a.push_back(v);

    if(cnt[2])
    {
       int p1 = -1, p2 = -1;
       for(int i = 1; i <= m; i++)
       {
         if(b[i] == 2)
         {
          if(~p1)p2 = i - 1;
          else p1 = i - 1;
         }
       }
       if(~p2)
       {
         insert2(p1, p2, 2, 2);
         insert2(p1, p2, 0, 1);
         insert2(p1, p2, 2, 1);
         insert2(p1, p2, 0, 2);
         insert2(p1, p2, 1, 1);
         insert2(p1, p2, 2, 0);
         insert2(p1, p2, 1, 2);
         insert2(p1, p2, 1, 0);
         check[p1 + 1] = check[p2 + 1] = 1;
       }
       else
       {
         insert1(p1, 2);
         insert1(p1, 1);
         check[p1 + 1] = 1;
       }
       for(int i = 1; i <= m; i++)
       {
         if(check[i])continue;
         if(a.size() % 2)f2(i - 1);
         else f3(i - 1);
       }
    }
    else
    {
       if(cnt[3])
       {
         int p = 0;
         for(int i = 1; i <= m; i++)
         {
          if(b[i] == 3)p = i - 1;
         }
         insert1(p, 3);
         insert1(p, 1);
         insert1(p, 2);
         check[p + 1] = 1;
       }
       else
       {
         insert1(0, 1);
         check[1] = 1;
       }
       for(int i = 1; i <= m; i++)
       {
         if(!check[i])f1(i - 1);
       }
    }

    for(auto &v: a)
    {
       if(*max_element(v.begin(), v.end()))
       {
         for(auto &p: v)cout << p << ' ';
         cout << endl;
       }
    }
    initialize(m);
}

}

175031734