QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #627775 | #5541. Substring Sort | ucup-team5062# | AC ✓ | 1303ms | 10668kb | C++20 | 8.0kb | 2024-10-10 17:06:20 | 2024-10-10 17:06:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int BACKET = 300;
int N;
int Q, L[1 << 19], R[1 << 19];
int Lexico[1 << 19][3][3];
int Orders[1 << 19][3];
string S[3];
// ======================================================================== Base Function
// -1: idx1 is smaller
// 0: same
// +1: idx1 is larger
int Compare(int pos, int idx1, int idx2) {
int cl = pos * BACKET;
int cr = pos * BACKET + BACKET; cr = min(cr, N);
int ord1 = Orders[pos][idx1];
int ord2 = Orders[pos][idx2];
for (int i = cl; i < cr; i++) {
if (S[ord1][i] < S[ord2][i]) return -1;
if (S[ord1][i] > S[ord2][i]) return +1;
}
return 0;
}
int FastCompare(int cl, int cr, int idx1, int idx2) {
int backet_l = cl / BACKET + 1;
int backet_r = cr / BACKET;
// First Compare
int fst_ord1 = Orders[backet_l - 1][idx1];
int fst_ord2 = Orders[backet_l - 1][idx2];
for (int i = cl; i < backet_l * BACKET; i++) {
if (S[fst_ord1][i] < S[fst_ord2][i]) return -1;
if (S[fst_ord1][i] > S[fst_ord2][i]) return +1;
}
// Second Compare
for (int i = backet_l; i < backet_r; i++) {
int snd_ord1 = Orders[i][idx1];
int snd_ord2 = Orders[i][idx2];
if (Lexico[i][snd_ord1][snd_ord2] == -1) return -1;
if (Lexico[i][snd_ord1][snd_ord2] == +1) return +1;
}
// Last Compare
int srd_ord1 = Orders[backet_r][idx1];
int srd_ord2 = Orders[backet_r][idx2];
for (int i = backet_r * BACKET; i < cr; i++) {
if (S[srd_ord1][i] < S[srd_ord2][i]) return -1;
if (S[srd_ord1][i] > S[srd_ord2][i]) return +1;
}
return 0;
}
// ======================================================================== Update Function
void Update(int cl, int cr, int fst, int snd, int srd) {
int backet_l = cl / BACKET + 1;
int backet_r = cr / BACKET;
// Middle Update
for (int i = backet_l; i < backet_r; i++) {
int v[3] = {Orders[i][0], Orders[i][1], Orders[i][2]};
Orders[i][0] = v[fst];
Orders[i][1] = v[snd];
Orders[i][2] = v[srd];
}
// Case 1
if (backet_l - 1 == backet_r) {
string sub[3] = {"", "", ""};
int pl = (backet_l - 1) * BACKET;
int pr = (backet_l - 1) * BACKET + BACKET; pr = min(pr, N);
for (int i = pl; i < pr; i++) sub[0] += S[0][i];
for (int i = pl; i < pr; i++) sub[1] += S[1][i];
for (int i = pl; i < pr; i++) sub[2] += S[2][i];
for (int i = pl; i < pr; i++) S[0][i] = sub[Orders[backet_l - 1][0]][i - pl];
for (int i = pl; i < pr; i++) S[1][i] = sub[Orders[backet_l - 1][1]][i - pl];
for (int i = pl; i < pr; i++) S[2][i] = sub[Orders[backet_l - 1][2]][i - pl];
// Latter
sub[0] = "";
sub[1] = "";
sub[2] = "";
for (int i = cl; i < cr; i++) sub[0] += S[0][i];
for (int i = cl; i < cr; i++) sub[1] += S[1][i];
for (int i = cl; i < cr; i++) sub[2] += S[2][i];
for (int i = cl; i < cr; i++) S[0][i] = sub[fst][i - cl];
for (int i = cl; i < cr; i++) S[1][i] = sub[snd][i - cl];
for (int i = cl; i < cr; i++) S[2][i] = sub[srd][i - cl];
}
else {
// First Update
if (true) {
string sub[3] = {"", "", ""};
int pl = (backet_l - 1) * BACKET;
int pr = (backet_l - 1) * BACKET + BACKET;
pr = min(pr, N);
for (int i = pl; i < pr; i++) sub[0] += S[0][i];
for (int i = pl; i < pr; i++) sub[1] += S[1][i];
for (int i = pl; i < pr; i++) sub[2] += S[2][i];
for (int i = pl; i < pr; i++) S[0][i] = sub[Orders[backet_l - 1][0]][i - pl];
for (int i = pl; i < pr; i++) S[1][i] = sub[Orders[backet_l - 1][1]][i - pl];
for (int i = pl; i < pr; i++) S[2][i] = sub[Orders[backet_l - 1][2]][i - pl];
// Latter
sub[0] = "";
sub[1] = "";
sub[2] = "";
for (int i = cl; i < pr; i++) sub[0] += S[0][i];
for (int i = cl; i < pr; i++) sub[1] += S[1][i];
for (int i = cl; i < pr; i++) sub[2] += S[2][i];
for (int i = cl; i < pr; i++) S[0][i] = sub[fst][i - cl];
for (int i = cl; i < pr; i++) S[1][i] = sub[snd][i - cl];
for (int i = cl; i < pr; i++) S[2][i] = sub[srd][i - cl];
}
// Last Update
if (true) {
string sub[3] = {"", "", ""};
int pl = (backet_r + 0) * BACKET;
int pr = (backet_r + 0) * BACKET + BACKET;
pr = min(pr, N);
for (int i = pl; i < pr; i++) sub[0] += S[0][i];
for (int i = pl; i < pr; i++) sub[1] += S[1][i];
for (int i = pl; i < pr; i++) sub[2] += S[2][i];
for (int i = pl; i < pr; i++) S[0][i] = sub[Orders[backet_r - 0][0]][i - pl];
for (int i = pl; i < pr; i++) S[1][i] = sub[Orders[backet_r - 0][1]][i - pl];
for (int i = pl; i < pr; i++) S[2][i] = sub[Orders[backet_r - 0][2]][i - pl];
// Latter
sub[0] = "";
sub[1] = "";
sub[2] = "";
for (int i = pl; i < cr; i++) sub[0] += S[0][i];
for (int i = pl; i < cr; i++) sub[1] += S[1][i];
for (int i = pl; i < cr; i++) sub[2] += S[2][i];
for (int i = pl; i < cr; i++) S[0][i] = sub[fst][i - pl];
for (int i = pl; i < cr; i++) S[1][i] = sub[snd][i - pl];
for (int i = pl; i < cr; i++) S[2][i] = sub[srd][i - pl];
}
}
// Final
vector<int> tmp = {backet_l - 1, backet_r};
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
for (int idx : tmp) {
Orders[idx][0] = 0;
Orders[idx][1] = 1;
Orders[idx][2] = 2;
Lexico[idx][0][1] = Compare(idx, 0, 1);
Lexico[idx][1][2] = Compare(idx, 1, 2);
Lexico[idx][2][0] = Compare(idx, 2, 0);
Lexico[idx][1][0] = Compare(idx, 1, 0);
Lexico[idx][2][1] = Compare(idx, 2, 1);
Lexico[idx][0][2] = Compare(idx, 0, 2);
}
}
// ======================================================================== Main Function
int main() {
// Step 1. Input
cin >> N >> Q;
for (int i = 0; i < 3; i++) cin >> S[i];
for (int i = 0; i < Q; i++) cin >> L[i] >> R[i];
for (int i = 0; i < Q; i++) L[i] -= 1;
for (int i = 0; i < Q; i++) R[i] -= 1;
// Step 2. Initialize
for (int i = 0; i < N; i += BACKET) Orders[i / BACKET][0] = 0;
for (int i = 0; i < N; i += BACKET) Orders[i / BACKET][1] = 1;
for (int i = 0; i < N; i += BACKET) Orders[i / BACKET][2] = 2;
for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][0][1] = Compare(i / BACKET, 0, 1);
for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][1][2] = Compare(i / BACKET, 1, 2);
for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][2][0] = Compare(i / BACKET, 2, 0);
for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][1][0] = Compare(i / BACKET, 1, 0);
for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][2][1] = Compare(i / BACKET, 2, 1);
for (int i = 0; i < N; i += BACKET) Lexico[i / BACKET][0][2] = Compare(i / BACKET, 0, 2);
// Step 3. Solve
for (int i = 0; i < Q; i++) {
pair<int, int> score[3];
int v1 = FastCompare(L[i], R[i] + 1, 0, 1);
int v2 = FastCompare(L[i], R[i] + 1, 1, 2);
int v3 = FastCompare(L[i], R[i] + 1, 2, 0);
score[0].second = 0;
score[1].second = 1;
score[2].second = 2;
score[0].first += v1; score[1].first -= v1;
score[1].first += v2; score[2].first -= v2;
score[2].first += v3; score[0].first -= v3;
// Sorting
sort(score, score + 3);
// Update
Update(L[i], R[i] + 1, score[0].second, score[1].second, score[2].second);
/*cout << "i = " << i << endl;
cout << S[0] << " " << S[1] << " " << S[2] << endl;
for (int i = 0; i <= 2; i++) cout << i << " -> " << Orders[i][0] << " " << Orders[i][1] << " " << Orders[i][2] << endl;
cout << endl;
cout << "Lexico: " << endl;
for (int i = 0; i <= 2; i++) {
cout << Lexico[i][0][1] << " " << Lexico[i][1][0] << " ";
cout << Lexico[i][1][2] << " " << Lexico[i][2][1] << " ";
cout << Lexico[i][2][0] << " " << Lexico[i][0][2] << " ";
cout << endl;
}
cout << endl;*/
}
// Output
string ans[3] = {"", "", ""};
for (int i = 0; i < N; i += BACKET) {
string sub[3] = {"", "", ""};
int cl = i;
int cr = i + BACKET; cr = min(cr, N);
for (int j = cl; j < cr; j++) sub[0] += S[0][j];
for (int j = cl; j < cr; j++) sub[1] += S[1][j];
for (int j = cl; j < cr; j++) sub[2] += S[2][j];
ans[0] += sub[Orders[i / BACKET][0]];
ans[1] += sub[Orders[i / BACKET][1]];
ans[2] += sub[Orders[i / BACKET][2]];
}
cout << ans[0] << endl;
cout << ans[1] << endl;
cout << ans[2] << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9796kb
input:
5 2 icpca siaja karta 2 4 1 5
output:
iarta kiaja scpca
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 9764kb
input:
6 6 aabbcc bcacab cbcaba 1 1 2 2 3 3 4 4 5 5 6 6
output:
aaaaaa bbbbbb cccccc
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 9640kb
input:
3 1 aba aab aac 1 3
output:
aab aac aba
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 9792kb
input:
1 1 z y x 1 1
output:
x y z
result:
ok 3 lines
Test #5:
score: 0
Accepted
time: 1303ms
memory: 10232kb
input:
100000 100000 llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
result:
ok 3 lines
Test #6:
score: 0
Accepted
time: 1151ms
memory: 10404kb
input:
100000 100000 ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttottttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttotttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttqtttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttkttttttttttttttttttttttttttttttttttttttttttttttt...
result:
ok 3 lines
Test #7:
score: 0
Accepted
time: 1001ms
memory: 10184kb
input:
100000 100000 aijpxjjjjcjwjjjjjmjajkjjjjjjoijjjjjjjjjeyjjwujvajjjjjjyjjjoejkhejdjoajjjzjjjjjkjjjjiqjjjjljjbjzjjjjjjepujjjjjejjjjjyjjjjjjjjjjjhjjjjjjjjjhjojejjjitjjjjjjjjjjujzjjrwjhjljjjjjjjjjjjjmjjjjjjjjjjzjjjjzijjjjjjjjjjjhjjjyjjjjjjjjrjjjjjjjjjjdbjjjvjjhjjcsjjrjjuljiejjjjjajkvjokrjhjkjjjjjjtljijjz...
output:
aicjbhjjjcjjjjjjjjjajkjjjjjjovfxjjjjjjjdjcjjjjjjjjnjjjejjjojjfhjzjkoajjdjjjjjjkjjjjijjjjjljjwjjjjjjjjjxjjjczjejjjjaykjjjdjjjjjjhjjjjvcjjjjjjjjjbjzykjjjdjjhtjujzjjzwjhjlocjjjjjjjjjjmnjjhjycjjjzjjjjjhjjjujjjjjjjcjjjyjjjjjjjcrdjjjjjjjjjdpfjrjjjjjjcfjjrjjujjjjjjjmhajkjjodnjjjkjjjjjjapjijjjjjejjljjtoayjj...
result:
ok 3 lines
Test #8:
score: 0
Accepted
time: 914ms
memory: 10248kb
input:
100000 100000 mvvvvvvvvvvvvvvvvvvvvvvvvevvvvvvvvvvvvvvvvvvvvvvvvdvvvvvvvvvvvvvvvvvvvvvvvvpvvvvvvvvvvvvvvvvvvvvvvvvdvvvvvvvvvvvvvvvvvvvvvvvvcvvvvvvvvvvvvvvvvvvvvvvvvkvvvvvvvvvvvvvvvvvvvvvvvvgvvvvvvvvvvvvvvvvvvvvvvvvtvvvvvvvvvvvvvvvvvvvvvvvvtvvvvvvvvvvvvvvvvvvvvvvvvbvvvvvvvvvvvvvvvvvvvvvvvvfvvvvvvvvvv...
output:
mvvvvvvvvvvvvvvvvvvvvvvvvevvvvvvvvvvvvvvvvvvvvvvvvdvvvvvvvvvvvvvvvvvvvvvvvvbvvvvvvvvvvvvvvvvvvvvvvvvdvvvvvvvvvvvvvvvvvvvvvvvvcvvvvvvvvvvvvvvvvvvvvvvvvevvvvvvvvvvvvvvvvvvvvvvvvavvvvvvvvvvvvvvvvvvvvvvvvtvvvvvvvvvvvvvvvvvvvvvvvvgvvvvvvvvvvvvvvvvvvvvvvvvbvvvvvvvvvvvvvvvvvvvvvvvvevvvvvvvvvvvvvvvvvvvvvvvv...
result:
ok 3 lines
Test #9:
score: 0
Accepted
time: 1153ms
memory: 10668kb
input:
100000 100000 keeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee...
output:
keeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee...
result:
ok 3 lines
Test #10:
score: 0
Accepted
time: 1204ms
memory: 10408kb
input:
100000 100000 wjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...
output:
mjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...
result:
ok 3 lines
Test #11:
score: 0
Accepted
time: 1067ms
memory: 10492kb
input:
100000 100000 cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
output:
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
result:
ok 3 lines
Test #12:
score: 0
Accepted
time: 1136ms
memory: 10484kb
input:
100000 100000 qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
result:
ok 3 lines
Test #13:
score: 0
Accepted
time: 1002ms
memory: 10292kb
input:
100000 100000 bccccbacaaaacaaaacabaacccabaabacacccbabcaacbbabbcbcaacbabccbccaaccbcaaabbccbaccbccbbaabcbbcbbabaabbaccabbcacbcabbbaabccbcbbbaccccbbabbacbabaabbbccccaabbbabbacabbcbaacbccababcbaccabccacbacbbaacbaaabaacabacbcccbbacbacbacaabbccabcaaaaabbbccccbaabacaaaacacbabcccaccbbaaaccbaacbbabcacbbaccab...
output:
aaaaaaaaaaaaaaaabaaaaaabaaababcaaacacccbabbabacbabbabaacbabacabbabbabbbbcaabaccacacabaacccaccbababbcccacabaccabaccbaaaccbaabbbbacaacaaaabcaabbacaacccccaabcacacccbccaabcacbcbbaabbcccbbcaccccbaacabccababcbbabaacaabcbaaabaaacabcbcacaabcaabbaaacbabbcbabbcbabcbbabccbbccbbabbcbcaaaaaaabcabacbbbbbbabbabaab...
result:
ok 3 lines
Test #14:
score: 0
Accepted
time: 955ms
memory: 10336kb
input:
100000 100000 bacbabbacabbbcbaccccabcbccbcbacaaabbcacaabaaacaacaccaccbabcbaccabbabccbcccacbccabbcacaacaaabcbbcccccacbabcaacccacabbccacacaccabcbcaaccbcbcbacacacbacaaaaacbcbcaccbacbcacccacacbbabcccaccbcbacbccbcabccabacccabcbbacaaacbbabbaaaaacaacabcaaabbacccbacacacbacbaabbccabaaabaccbacaaaaabcacacacacb...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok 3 lines
Test #15:
score: 0
Accepted
time: 1ms
memory: 9732kb
input:
1 1 w w w 1 1
output:
w w w
result:
ok 3 lines
Test #16:
score: 0
Accepted
time: 995ms
memory: 10380kb
input:
100000 100000 hrwrlmxrhlyjibbyhspkrnnsvqowvahkzyurqhyjqpuousezjxotsbkdyuxmoffscrietmpyexgemtkkhfhergdxfjjthyplhysvakfbzoarnitovvdeetpvfcymorejruutwjboeyjvgefqpwupoddtyuqfynecsebasfsskfuwisafcwyjhxjueptownnuqugoqxuiylipyxyilgwhijfpqtkwhmkawbmmeicsxhhtvrblfslgzsxaaodwetqndawnqbtgxcvaobtxokmzagjewgismy...
output:
hrwrldxpmayviawdgrvvknqwjhonauhkzfpssodpmlfoveograuevoidyjilosvxaxesgmihnxgemkpvghrirgdxfjjthnprwfazykfhasfzjudzmrceuypugqsdbnejruudsddbenidxafqxwzpxgtfyvubpincsebapunvemvclcunnlinorgxplnsofypqxcsxavrdlkhhjzykgwsttwiiamhdfybebvddicsshhttbkgfkzglsclaodkjyqndljkbhghecbhrfarrkmzagjewgwjhqrgyxwdjqsolmex...
result:
ok 3 lines
Test #17:
score: 0
Accepted
time: 1034ms
memory: 10236kb
input:
100000 100000 sxigpbnutawzekewadxbnkvbwocjfdfmtkqecqlfchesyygyqqzrobsjfkqgyruuotdgggxejzkvekezyjhqilvahkbrgtjccltijrpqpqnjyckhjjyrtkqgoaixczfkxdxzihslpqdazmjdypczbxlxzxrgjyxshyqdbknywltuuxteafyicqseszuaqlnvvsbknacmqdgagdygitmkldnihkpmjfdvhcotzhqeyqivmpwjjytbrdwldkfvhgilewiweauerretsupeudvtoqcrjaioie...
output:
bddgugahkamrekedaogbcdvargaurjfdtcocpygfcvtswbbjaqeoomzvfwegynknwtpgugygkzteeaejvvhanlmuhgqroekkfitzjtqoponedckhjfyftuogopioqzskxwuzndtrpddgmvhdyptcpblxtuqeafxaeyvotkvgjwtuhctisfgsvnlzlwjawqlvssljoncmfwgmjvjkizsklfvshcjmjpdapjsbzhwbivivjpeyxgturolprkovfgimeeivnzyerrgkfulrukwqlqcrbtisxeijbumidvltsfky...
result:
ok 3 lines
Test #18:
score: 0
Accepted
time: 857ms
memory: 10476kb
input:
100000 100000 jjrvgzoqdnqekkrmnknpoowdpicfhxoonddenrnjwblgcakwfmqhtajsigglkezubtonxtwpdeululjzzvavpkwpmzprxujafkhjduoacjpkqfmbibwixucewxuiwgkjrdctyjjslgordypqjcrxvpankaqjcdympwzpwnhghlphjejzrvrgoiubctqixxruerxfjailsqvbmgalwdwcyzwgfykmscvbmxlqwmbjkkczeguxxlilohovateiiyvjrvpvjqdsxdtjtqhuoymbjhakrmgpth...
output:
jjrvdlovdjiepsubnwxnhowdpicfhxumnbdjjdvqwblggcacmihttaxlxemtztptbtogktxmsewxigjsydrhpkwfysfsmeiqeehhftoaijpkqfdbibwixzcesnuiwgkcklpgnblmrgordypqnkdxvpacpmordthmpaakwnenjmahjdjzrvrdtigbsfigxrrdbnugjsvlsqvbkbilhuleydxrfykmjgvbfiufqpnjkkevhxfeklildtkbyeegnyvdcvpvjqcsxgtjyskuopsbyfybvblplnadcgpxmjuedget...
result:
ok 3 lines
Test #19:
score: 0
Accepted
time: 2ms
memory: 9916kb
input:
4 4 adsz absd basc 4 4 3 4 2 4 1 4
output:
aasz absd bdsc
result:
ok 3 lines
Test #20:
score: 0
Accepted
time: 390ms
memory: 9996kb
input:
27486 40833 svpwowlqqjlhxbzhjmuvnmokyvbicqajvyudwwzmuulnurdsqpdnytnckmgeutlfodaiqdpfqkyxrljplxscbzrqrefjdtipjioalqzycqfqezqpgkmmgqeicrridufyjrvacqvrczzwmnzbpltablhzdjhmdriwkxbfsoowgnnxcxocyhiarvdqsvhgekpoaevjadrohsthzlgtokpxoqfxyrllwzsdhtvkkrwgpiwzspsrnnyfqklqpmamhsrhhjqtlwdchcojpooaqzqilfxdjclzxgun...
output:
sqoqdcivdmldxbzdpwfgdhbuyqvncfamvcumwrebqulkwiagpuafuldxkzbeunldodavymppfcojppylqorynqjqxejomtmpegnleleinbzmpeqpggsmxceacmrssxggvrvacqpdtpzwmxzbpbrtsrfgujhextiwkyoqojokdqdscxcsyhuarmtqsejgeakncqijaylohyapuvhzbkbzmxfdbwllnasevdsukmkgspwzgdqugmbhakpupatrjsmhhrqaleucucojpozaqzqilgkysuczxpvbmrcxnlswpcad...
result:
ok 3 lines
Test #21:
score: 0
Accepted
time: 416ms
memory: 9796kb
input:
16247 43020 gkhfgkozymylzzeupoaavhhyzxqbsduyoepdpmbardxqmkvebrcgvwjggscpaqwrqwjnopuastbysarbiuawyvvdnhsarxixdmdhgjxzsqgcvputskskxtgdkhpricvnqcplzcizexdxicawfutylhvljytttbynhqeypdtvdpqctdxkvmbityeqpdnjrvwxeecjujokdwaxulhospusmzjdqwqpymkfqxsnqngvakgwhignjbrcgjgxalgfbojugfjiarkuttvmgjtuxiknbriuovnlmizp...
output:
gedfgkopahletkwuzaaavhirxouerdeyobpjpmbafdxwmzwpbstzywrzwwcbbqdchbnlopcvgtbyoanpioagypvfnmxuzvuxcmhwvjxzixtyvpuuskmcxtgfkbzrsdawxmpszuilfgdlegpwfunyltdtgytvtbmshmlypptvnpqwkowdvmsblybqpjbsrbfcewcrujihtweoalktbpqqmdkdbwjpybyfdxsiqngeatcwbwvunbrmijoaowthbokwfyjgacruxrjmgiuuxikhbrzuonzwqinpninimokcgsfh...
result:
ok 3 lines
Test #22:
score: 0
Accepted
time: 416ms
memory: 10016kb
input:
41563 43585 hyfoxmsexwutmmxvfzsuxexyvyngsaswzhgravymmponvzxzhymteflmhqmyxkumfzhmkxfhumpgrmuwcuvduxwwxxrztdnodedvbipjibrnwjscdkwwwqvuybocqgtjmzbjcocwwlnysjlyllrwxpaybuhazpbpgqbjvluqaacjktkylcgwucofcptygawolpiuqudfrulysmxaqzjbufatcjuqkhhqouxobitkimnabxgiaehhaciseccthislpjbiihejsndcgcyxezohgtlddkecmeft...
output:
fncicqmexwhcmbkwflsusvpyvynucasynhgrkvyerchnnljzhymyisbwxbxyxheqpgvfodkjlmkbrmugquvduxwfxxgztfzidbgjzvktibrniubjvrxwjqvuyufcpgtwijbjcocwwsjxajlyujuixpvunumjzuobijaciflaaackktoglcgeehowmptygautnpiumnhiktlkcpxhczerjmaezeklieeovqmtnemayjyyjvqiaehiamisexrxwxgljmboihhisnzmgcyxsqohteobwgecmesnwstxjajplegs...
result:
ok 3 lines
Test #23:
score: 0
Accepted
time: 361ms
memory: 9908kb
input:
33194 36811 migurpyumyjthmmhctxrweckuebrkhonoirgbipbgeftnawzqfyijdwyavtzysxhvcusfknonbhlcbjeoywfbaoixsgnyvfrpfvbikheiukvnftmqiqxwopiozonvqqsihqadomsishfdwcuwfafwawtsxlofucmuwhzcsvvsidgehgyeybrudyczejjcoetknjfjnkyjraoxfsimmzjfdwrklmsiggknrrdvntfddpddwgsuchudcgaalbwgmzybievdelradiklprolmvvertzxkctqshw...
output:
mifhjbkcmojehvmgcaiunpckqenanhoxhivkbxpzgjgzaqplqyfklfgyjjnzynxdvlaenkjoobhlybjvoywysyhufognxkenpqturublbnkvfntybiggzoalozmnvnxsihqtaembmshfrwcfdfafhaatbxllquruutyarsxisxdgpufyeggrtrvxzezdtoetxayzchkimraosflimytvkdoruhpdwbhhvcrsevtfddpduwpquzhuucgxademgmsufifvdekrblikloxolmvbczakxohtwrywgpcjknzukzxu...
result:
ok 3 lines
Test #24:
score: 0
Accepted
time: 483ms
memory: 10300kb
input:
49558 49843 cbofhipshjqyaeigtwhfxdfslpvnrepwotsujyvzyxzajiwcmmmzxrxvsvssfhhtqadzlpcchjthwrcxzdpuwezrryakbbvpbijomoxysorgbkytclureigezreytvjsvpapnjpqpzhwtwwsnclpazkmybluftxielnhdukhhvbdxxfvytyuwufhxuxbdqvblzfyessweunyquobdhmgdqzvmzumavzvizulvgcrrvjjugvcatuuueyudztkzwuutazmigguhnqdwiptfuurvmpakuqhgrdt...
output:
abzfefbbmjqheeigtwhatdfnlphwebpworhejyvrzmhajiwcmmmzjpxrjolvfhhfqbsoudweyhhvmiiysjtjwvbrgyaotbonztgoshngqurgfkyyfeucilerzreyddjsvcnxzzymomhxzyhynrabrfkdwclffqaielnhdpaleaxarkovytyqwufhqnnisbpekzfyeexeeunemarfdhmgfyddmsdbavzvizbwtizrruijaqbzatuuuhwxvstlwvehbazmigguhdzdwxqaslurvyjakuqhhkctgcilulziaosy...
result:
ok 3 lines
Test #25:
score: 0
Accepted
time: 476ms
memory: 10100kb
input:
47097 47879 lgfihdebrdscubyblbaxnnshsgevdmpdfzehqxyipfosbddjbwwvosusbcftpriisyvghbgudzwjxczdrqvcewnyeialotookodvgxsfiwklkjymdmltszrwzwiocgfiuomhhzwgjpyiawkztluepsjevloknxgesgwqqonekopnfkuxskwrafenrjvujdzajdfpfnwjwzmtffacgirennllocsedqfhwdoabwevtrlvnerogrpriikiiscdggavxyiczvsizmekwutvvnkxqbzxquqoasxh...
output:
lgfcedebrcewubfuqbawwvyhsznvshxdzletgpxnyissbpvzelehpqisbsfuxrbayevohxwrdnmesczdrrrceqqhsidlrwkokufoghsfhwnlkkyxdmlxttjwzwipbgfiunbhbrwzqwyicsxmbcutpbcyzxowuxgeepxqggnsuoiysgorswufxeckrkcujwzgselgvmgjswmsvxacglewsiqyjvcyrqsrnxldowspgtlzgtksrtrobicltfcehgavxuicavrycmukwuttaxarnmznklqomditelprlwcrnuzw...
result:
ok 3 lines