//AB题无需多言

C

//贪心思路挺简单，就是代码实现有点...，
//我用的是n方的方法
//看视频有kmp算法（还没学）
//尸山代码，末尾有hh的
#include <bits/stdc++.h>
using namespace std;


string computeXOR(const string &a, const string &b){
    int len_a = a.size();
    int len_b = b.size();
    int max_len = max(len_a, len_b);
    string a_padded = a;
    string b_padded = b;


    while(a_padded.size() < max_len) a_padded = "0" + a_padded;
    while(b_padded.size() < max_len) b_padded = "0" + b_padded;

    string xor_str = "";
    for(int i=0; i<max_len; i++){
        xor_str += (a_padded[i] == b_padded[i]) ? '0' : '1';
    }


    int start = 0;
    while(start < xor_str.size()-1 && xor_str[start] == '0') start++;
    xor_str = xor_str.substr(start);

    return xor_str;
}

void solve(){
    string s;
    cin>>s;
    int n = s.size();
    int b=0;


    while(b < n && s[b] == '1'){
        b++;
    }

    if(b >= n){
        int pos = (n +1)/2;
        cout<< pos <<" "<< pos <<" "<< "1 " << n <<"\n";
        return;
    }


    string cop = s.substr(b, n - b); 
    int len = n - b;


    string max_xor = "";
    pair<int, int> p1 = {1,1}, p2 = {b+1, n}; 


    for(int i=0; i + len <=n; i++){
        if(s[i] != '1') continue;
        string substr = s.substr(i, len);
        string current_xor = computeXOR(substr, cop);


        if(current_xor.size() > max_xor.size() || 
           (current_xor.size() == max_xor.size() && current_xor > max_xor)){
            max_xor = current_xor;
            p1 = {i+1, i+len}; 
        }
    }


    if(max_xor.empty()){

        p1 = {1,1};
    }

    cout<< p1.first <<" "<< p1.second <<" "<< 1 <<" "<< s.size() <<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}
/////
#include <bits/stdc++.h>
#include <random>
#include <unordered_set>
using namespace std;
#define int long long
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
#define lowbit(x) ((x)&(-x))
#define endl '\n';

void solve() {

    string s;cin>>s;

    int n=s.size();

    if(count(s.begin(),s.end(),'0')==0) {
        cout<<"1 1 1 "<<n<<endl;
        return;
    }

    string t;

    for(int i=0;i<n;i++) {
        if(s[i]=='0') {
            t=s.substr(i);
            break;
        }
    }
    int m=t.size();

    string best="";
    int ans=-1;
    for(int i=0;i+m<=n;i++) {
        string candi;
        for(int j=i;j<i+m;j++) {
            candi+=(t[j-i]+s[j]=='0'+'1')+'0';
        }
        if(candi>best) {
            best=candi;
            ans=i;
        }
    }

    cout<<1<<" "<<n<<" "<<ans+1<<" "<<ans+m<<endl;
}

signed main() {

    ios::sync_with_stdio(0); cin.tie(0);

    int _=1;
    cin>>_;
    while(_--) {
        solve();
    }

    return 0;
}

G

//这道题状态设计还是比较简单的，但是观察到结果固定，应该用dp打标，dfs不太适合
//题解转化为二维前缀和，通过反转和坐标对应（还没理解对应关系）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 10;
unordered_set<ll> firstSequence;
unordered_set<ll> secondSequence;
ll f[N];  
void precomputeSequences(int limit) {
    ll sum = 1, increment = 1;
    while (sum <= limit) {
        if (sum != 1) firstSequence.insert(sum);
        sum += increment;
        increment++;
    }
    sum = 1, increment = 2;
    while (sum <= limit) {
        if (sum != 1) secondSequence.insert(sum);
        sum += increment;
        increment++;
    }
}

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

    const ll LIMIT = 1000000;
    precomputeSequences(LIMIT);
    f[1] = 1;
    int curr = 2;
    int geshu = 2;
    int jishu = 0;

    for (ll i = 2; i <= LIMIT; i++) {
        if (firstSequence.find(i) != firstSequence.end()) {
            f[i] = f[i - curr + 1] + i * i; 
        } else if (secondSequence.find(i) != secondSequence.end()) {
            f[i] = f[i - curr] + i * i; 
        } else {
            f[i] = f[i - curr + 1] + f[i - curr] + i * i - f[i-curr*2+2];
        }

        jishu++;
        if (jishu == geshu) {
            jishu = 0;
            geshu++;
            curr++;
        }
    }

    while (t--) {
        int n;
        cin >> n; 
        cout << f[n] << "\n"; 
    }

    return 0;
}
//
#include <bits/stdc++.h>

using namespace std;

long long ans[2000007];
long long a[1500][1500] = {}, curr = 1;

void solve() {
    int n;
    cin >> n;
    cout << ans[n] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 1; i < 1500; i++) {
        for (int j = i - 1; j >= 1; j--) {
            a[j][i - j] = a[j - 1][i - j] + a[j][i - j - 1] - a[j - 1][i - j - 1] + curr * curr;
            ans[curr] = a[j][i - j];
            curr++;
        }
    }

    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

B

//很经典的硬币题，这种题有贪心和dp的两者提醒，根据数据范围确定
//这题1e9肯定是贪心，但是懒得推公式，直接先使用dp进行30以内打表
//三十以外贪心的使用15这个最大面值，但是注意多对一的情况比如35可以分解为
//15 20，30 5，这种时候特判就好了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll yingbi[] = {0, 1, 3, 6, 10, 15};
ll dp[6][31];

void init() {

    for(int i = 0; i <=5; i++) {
        for(int j = 0; j <=30; j++) {
            dp[i][j] = 1e18;
        }
    }
    dp[0][0] = 0;
    for(int i = 1; i <=5; i++) {
        for(int j = 0; j <=30; j++) {
            dp[i][j] = min(dp[i][j], dp[i-1][j]);
            if(j >= yingbi[i]) {
                dp[i][j] = min(dp[i][j], dp[i][j - yingbi[i]] + 1);
            }
        }
    }
}


ll get_min_coins(ll n) {特判多种组合


    ll res = 1e18;

    ll max_k = n / 15;
                    //留个三以上让枚举
    for(ll k = max(max_k - 2, (ll)0); k <= max_k; k++) {
        ll remaining = n - k * 15;
        if(remaining < 0) continue;
        if(remaining > 30) continue; 
        res = min(res, k + dp[5][remaining]);
    }

    return res;
}

void solve() {
    ll n;
    cin >> n;
    cout << get_min_coins(n) << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    init();
    while(t--){
        solve();
    }
}

D

//这一题有些复杂，给我搞不会了
//这个好复杂。
//但是理解后又感觉，我当时咋不会呢，我觉得是面对复杂题面处理能力不足
//首先对于小于kl的题，kl都能拿第一，大于的就排在后面。
//然后划分的时候，有余数（不选的题），我们要尽量让他卡在大于kl的地方，为什么，显然题越难做出来的越少；
//然后对于一组中，要用一组中最简单（最左的来代表整个组）题的解决人数来代表排名
#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve() {
    int n , m;
    cin >> n >> m;
    vector<int> a(n + 1) , b(m + 1);
    for(int i = 1;i <= n;i ++) 
        cin >> a[i];
    int fir = a[1];
    sort(a.begin() + 1 , a.begin() + 1 + n);
    for(int i = 1;i <= m;i ++) 
        cin >> b[i];
    sort(b.begin() + 1 , b.begin() + m + 1);
    for(int i = 1;i <= m;i ++) {
        int ans = 0;
        int s = upper_bound(b.begin() + 1 , b.begin() + 1 + m , fir) - b.begin();
        for(int j = s + m % i;j <= m;j += i) {
            int seat = lower_bound(a.begin() + 1 , a.begin() + 1 + n , b[j]) - a.begin();
            ans += (n - seat + 1);
        }
        cout << ans + m / i << ' ';
    }
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    int t;cin >> t;while(t --) solve();
    return 0;
}