#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include <algorithm>
#include <stack>
#include <cassert>
#include <queue>
#include <map>
#include <set>
#include <iterator>
#include <bitset>
using namespace std;

template <class T>
class heap {
public:
    int size() {
        return n;
    }
    int top() {
        return h[0];
    }
    bool empty() {
        return n == 0;
    }
    void push(T a) {
        h.push_back(a);
        SiftUp(n);
        n++;
    }
    void pop() {
        n--;
        swap(h[n], h[0]);
        h.pop_back();
        SiftDown(0);
    }
    void clear() {
        h.clear();
        n = 0;
    }
    T operator [] (int a) {
        return h[a];
    }
private:
    vector<T> h;
    int n = 0;
    void SiftUp(int a) {
        while (a) {
            int p = (a - 1) / 2;
            if (h[p] > h[a]) swap(h[p], h[a]);
            else break;
            a--; a /= 2;
        }
    }
    void SiftDown(int a) {
        while (2 * a + 1 < n) {
            int l = 2 * a + 1, r = 2 * a + 2;
            if (r == n) {
                if (h[l] < h[a]) swap(h[l], h[a]);
                break;
            }
            else if (h[l] <= h[r]) {
                if (h[l] < h[a]) {
                    swap(h[l], h[a]);
                    a = l;
                }
                else break;
            }
            else if (h[r] < h[a]) {
                swap(h[r], h[a]);
                a = r;
            }
            else break;
        }
    }
};
int randint() {
    return rand() * RAND_MAX + rand();
}
const int len[4] = { 1e5, 1e6, 1e7, 1e8 };
int curt = 1;

void bubblesort(int* l, int* r) {
    int sz = r - l;
    if (sz <= 1) return;
    bool b = true;
    while (b) {
        b = false;
        for (int* i = l; i + 1 < r; i++) {
            if (*i > *(i + 1)) {
                swap(*i, *(i + 1));
                b = true;
            }
        }
        r--;
    }
}
void _bubblesort(vector<int> &a, int l, int r) {
    int sz = r - l;
    if (sz <= 1) return;
    bool b = true;
    while (b) {
        b = false;
        for (int i = l; i < r - 1; i++) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                b = true;
            }
        }
        r--;
    }
}
void bubblesort(vector<int> &a) {
    _bubblesort(a, 0, a.size());
}

void shakersort(int* l, int* r) {
    int sz = r - l;
    if (sz <= 1) return;
    bool b = true;
    int* beg = l - 1;
    int* end = r - 1;
    while (b) {
        b = false;
        beg++;
        for (int* i = beg; i < end; i++) {
            if (*i > *(i + 1)) {
                swap(*i, *(i + 1));
                b = true;
            }
        }
        if (!b) break;
        end--;
        for (int* i = end; i > beg; i--) {
            if (*i < *(i - 1)) {
                swap(*i, *(i - 1));
                b = true;
            }
        }
    }
}
void _shakersort(vector<int> &a, int l, int r) {
    int sz = r - l;
    if (sz <= 1) return;
    bool b = true;
    int beg = l - 1, end = r - 1;
    while (b) {
        b = false;
        beg++;
        for (int i = beg; i < end; i++) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                b = true;
            }
        }
        if (!b) break;
        end--;
        for (int i = end; i > beg; i--) {
            if (a[i] < a[i - 1]) {
                swap(a[i], a[i - 1]);
                b = true;
            }
        }
    }
}
void shakersort(vector<int> &a) {
    _shakersort(a, 0, a.size());
}

void insertionsort(int* l, int* r) {
    for (int *i = l + 1; i < r; i++) {
        int* j = i;
        while (j > l && *(j - 1) > *j) {
            swap(*(j - 1), *j);
            j--;
        }
    }
}
void _insertionsort(vector<int> &a, int l, int r) {
    for (int i = l + 1; i < r; i++) {
        int j = i;
        while (j > l && a[j - 1] > a[j]) {
            swap(a[j - 1], a[j]);
            j--;
        }
    }
}
void insertionsort(vector<int> &a) {
    _insertionsort(a, 0, a.size());
}

void selectionsort(int* l, int* r) {
    for (int *i = l; i < r; i++) {
        int minz = *i, *ind = i;
        for (int *j = i + 1; j < r; j++) {
            if (*j < minz) minz = *j, ind = j;
        }
        swap(*i, *ind);
    }
}
void _selectionsort(vector<int> &a, int l, int r) {
    for (int i = l; i < r; i++) {
        int minz = a[i], ind = i;
        for (int j = i + 1; j < r; j++) {
            if (minz > a[j]) minz = a[j], ind = j;
        }
        swap(a[i], a[ind]);
    }
}
void selectionsort(vector<int> &a) {
    _selectionsort(a, 0, a.size());
}

void gnomesort(int* l, int* r) {
    int *i = l;
    while (i < r) {
        if (i == l || *(i - 1) <= *i) i++;
        else swap(*(i - 1), *i), i--;
    }
}
void _gnomesort(vector<int> &a, int l, int r) {
    int i = l;
    while (i < r) {
        if (i == l || a[i - 1] <= a[i]) i++;
        else swap(a[i - 1], a[i]), i--;
    }
}
void gnomesort(vector<int> &a) {
    _gnomesort(a, 0, a.size());
}

void combsort(int* l, int* r) {
    int sz = r - l;
    if (sz <= 1) return;
    double k = 1.2473309;
    int step = sz - 1;
    while (step > 1) {
        for (int* i = l; i + step < r; i++) {
            if (*i > *(i + step))
                swap(*i, *(i + step));
        }
        step /= k;
    }
    bool b = true;
    while (b) {
        b = false;
        for (int* i = l; i + 1 < r; i++) {
            if (*i > *(i + 1)) {
                swap(*i, *(i + 1));
                b = true;
            }
        }
    }
}
void _combsort(vector<int> &a, int l, int r) {
    int sz = r - l;
    if (sz <= 1) return;
    double k = 1.2473309;
    int step = r - l - 1;
    while (step > 1) {
        for (int i = l; i + step < r; i++) {
            if (a[i] > a[i + step])
                swap(a[i], a[i + step]);
        }
        step /= k;
    }
    bool b = true;
    while (b) {
        b = false;
        for (int i = l; i < r - 1; i++) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                b = true;
            }
        }
    }
}
void combsort(vector<int> &a) {
    _combsort(a, 0, a.size());
}

void shellsort(int* l, int* r) {
    int sz = r - l;
    int step = sz / 2;
    while (step >= 1) {
        for (int *i = l + step; i < r; i++) {
            int *j = i;
            int *diff = j - step;
            while (diff >= l && *diff > *j) {
                swap(*diff, *j);
                j = diff;
                diff = j - step;
            }
        }
        step /= 2;
    }
}
void _shellsort(vector<int> &a, int l, int r) {
    int n = r - l;
    int step = n / 2;
    while (step >= 1) {
        for (int i = l + step; i < r; i++) {
            int j = i, diff = j - step;
            while (diff >= l && a[diff] > a[j]) {
                swap(a[diff], a[j]);
                j = diff;
                diff = j - step;
            }
        }
        step /= 2;
    }
}
void shellsort(vector<int> &a) {
    _shellsort(a, 0, a.size());
}

void shellsorthib(int* l, int* r) {
    int sz = r - l;
    if (sz <= 1) return;
    int step = 1;
    while (step < sz) step <<= 1;
    step >>= 1;
    step--;
    while (step >= 1) {
        for (int *i = l + step; i < r; i++) {
            int *j = i;
            int *diff = j - step;
            while (diff >= l && *diff > *j) {
                swap(*diff, *j);
                j = diff;
                diff = j - step;
            }
        }
        step /= 2;
    }
}
void _shellsorthib(vector<int> &a, int l, int r) {
    int n = r - l;
    int step = 1;
    while (step < n) step <<= 1;
    step >>= 1;
    while (step >= 1) {
        for (int i = l + step; i < r; i++) {
            int j = i, diff = j - step;
            while (diff >= l && a[diff] > a[j]) {
                swap(a[diff], a[j]);
                j = diff;
                diff = j - step;
            }
        }
        step /= 2;
    }
}
void shellsorthib(vector<int> &a) {
    _shellsorthib(a, 0, a.size());
}

int steps[100];
void shellsortsedgwick(int* l, int* r) {
    int sz = r - l;
    steps[0] = 1;
    int q = 1;
    while (steps[q - 1] * 3 < sz) {
        if (q % 2 == 0)
            steps[q] = 9 * (1 << q) - 9 * (1 << (q / 2)) + 1;
        else
            steps[q] = 8 * (1 << q) - 6 * (1 << ((q + 1) / 2)) + 1;
        q++;
    }
    q--;
    for (; q >= 0; q--) {
        int step = steps[q];
        for (int *i = l + step; i < r; i++) {
            int *j = i;
            int *diff = j - step;
            while (diff >= l && *diff > *j) {
                swap(*diff, *j);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void _shellsortsedgwick(vector<int> &a, int l, int r) {
    int n = r - l;
    vector<int> steps;
    steps.push_back(1);
    int q = 1;
    while (steps.back() * 3 < n) {
        if (q % 2 == 0)
            steps.push_back(9 * (1 << q) - 9 * (1 << (q / 2)) + 1);
        else
            steps.push_back(8 * (1 << q) - 6 * (1 << ((q + 1) / 2)) + 1);
        q++;
    }
    for (int q = steps.size() - 1; q >= 0; q--) {
        int step = steps[q];
        for (int i = l + step; i < r; i++) {
            int j = i, diff = j - step;
            while (diff >= l && a[diff] > a[j]) {
                swap(a[diff], a[j]);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void shellsortsedgwick(vector<int> &a) {
    _shellsortsedgwick(a, 0, a.size());
}

void shellsortpratt(int* l, int* r) {
    int sz = r - l;
    steps[0] = 1;
    int cur = 1, q = 1;
    for (int i = 1; i < sz; i++) {
        int cur = 1 << i;
        if (cur > sz / 2) break;
        for (int j = 1; j < sz; j++) {
            cur *= 3;
            if (cur > sz / 2) break;
            steps[q++] = cur;
        }
    }
    insertionsort(steps, steps + q);
    q--;
    for (; q >= 0; q--) {
        int step = steps[q];
        for (int *i = l + step; i < r; i++) {
            int *j = i;
            int *diff = j - step;
            while (diff >= l && *diff > *j) {
                swap(*diff, *j);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void _shellsortpratt(vector<int> &a, int l, int r) {
    int n = r - l;
    vector<int> steps;
    steps.push_back(1);
    int cur = 1;
    for (int i = 1; i < n; i++) {
        int cur = 1 << i;
        if (cur > n / 2) break;
        for (int j = 1; j < n; j++) {
            cur *= 3;
            if (cur > n / 2) break;
            steps.push_back(cur);
        }
    }
    sort(steps.begin(), steps.end());
    for (int q = steps.size() - 1; q >= 0; q--) {
        int step = steps[q];
        for (int i = l + step; i < r; i++) {
            int j = i, diff = j - step;
            while (diff >= l && a[diff] > a[j]) {
                swap(a[diff], a[j]);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void shellsortpratt(vector<int> &a) {
    _shellsortpratt(a, 0, a.size());
}

void myshell1(int* l, int* r) {
    int sz = r - l, q = 1;
    steps[0] = 1;
    while (steps[q - 1] < sz) {
        int s = steps[q - 1];
        steps[q++] = s * 4 + s / 4;
    }
    q--;
    for (; q >= 0; q--) {
        int step = steps[q];
        for (int *i = l + step; i < r; i++) {
            int *j = i;
            int *diff = j - step;
            while (diff >= l && *diff > *j) {
                swap(*diff, *j);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void _myshell1(vector<int> &a, int l, int r) {
    int n = r - l;
    vector<int> steps;
    steps.push_back(1);
    while (steps.back() < n) {
        int s = steps.back();
        steps.push_back(s * 4 + s / 4);
    }
    for (int q = steps.size() - 1; q >= 0; q--) {
        int step = steps[q];
        for (int i = l + step; i < r; i++) {
            int j = i, diff = j - step;
            while (diff >= l && a[diff] > a[j]) {
                swap(a[diff], a[j]);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void myshell1(vector<int> &a) {
    _myshell1(a, 0, a.size());
}

void myshell2(int* l, int* r) {
    int sz = r - l, q = 1;
    steps[0] = 1;
    while (steps[q - 1] < sz) {
        int s = steps[q - 1];
        steps[q++] = s * 3 + s / 3;
    }
    q--;
    for (; q >= 0; q--) {
        int step = steps[q];
        for (int *i = l + step; i < r; i++) {
            int *j = i;
            int *diff = j - step;
            while (diff >= l && *diff > *j) {
                swap(*diff, *j);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void _myshell2(vector<int> &a, int l, int r) {
    int n = r - l;
    vector<int> steps;
    steps.push_back(1);
    while (steps.back() < n) {
        int s = steps.back();
        steps.push_back(s * 3 + s / 3);
    }
    for (int q = steps.size() - 1; q >= 0; q--) {
        int step = steps[q];
        for (int i = l + step; i < r; i++) {
            int j = i, diff = j - step;
            while (diff >= l && a[diff] > a[j]) {
                swap(a[diff], a[j]);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void myshell2(vector<int> &a) {
    _myshell2(a, 0, a.size());
}

void myshell3(int* l, int* r) {
    int sz = r - l, q = 1;
    steps[0] = 1;
    while (steps[q - 1] < sz) {
        int s = steps[q - 1];
        steps[q++] = s * 4 - s / 5;
    }
    q--;
    for (; q >= 0; q--) {
        int step = steps[q];
        for (int *i = l + step; i < r; i++) {
            int *j = i;
            int *diff = j - step;
            while (diff >= l && *diff > *j) {
                swap(*diff, *j);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void _myshell3(vector<int> &a, int l, int r) {
    int n = r - l;
    vector<int> steps;
    steps.push_back(1);
    while (steps.back() < n) {
        int s = steps.back();
        steps.push_back(s * 4 - s / 5);
    }
    for (int q = steps.size() - 1; q >= 0; q--) {
        int step = steps[q];
        for (int i = l + step; i < r; i++) {
            int j = i, diff = j - step;
            while (diff >= l && a[diff] > a[j]) {
                swap(a[diff], a[j]);
                j = diff;
                diff = j - step;
            }
        }
    }
}
void myshell3(vector<int> &a) {
    _myshell3(a, 0, a.size());
}

void quicksort(int* l, int* r) {
    if (r - l <= 1) return;
    int z = *(l + (r - l) / 2);
    int* ll = l, *rr = r - 1;
    while (ll <= rr) {
        while (*ll < z) ll++;
        while (*rr > z) rr--;
        if (ll <= rr) {
            swap(*ll, *rr);
            ll++;
            rr--;
        }
    }
    if (l < rr) quicksort(l, rr + 1);
    if (ll < r) quicksort(ll, r);
}
void _quicksort(vector<int> &a, int l, int r) {
    if (r - l <= 1) return;
    int z = a[(l + r) / 2];
    int ll = l, rr = r - 1;
    while (ll <= rr) {
        while (a[ll] < z) ll++;
        while (a[rr] > z) rr--;
        if (ll <= rr) swap(a[ll++], a[rr--]);
    }
    if (l < rr) _quicksort(a, l, rr + 1);
    if (ll < r) _quicksort(a, ll, r);
}
void quicksort(vector<int> &a) {
    _quicksort(a, 0, a.size());
}

void quickinssort(int* l, int* r) {
    if (r - l <= 32) {
        insertionsort(l, r);
        return;
    }
    int z = *(l + (r - l) / 2);
    int* ll = l, *rr = r - 1;
    while (ll <= rr) {
        while (*ll < z) ll++;
        while (*rr > z) rr--;
        if (ll <= rr) {
            swap(*ll, *rr);
            ll++;
            rr--;
        }
    }
    if (l < rr) quickinssort(l, rr + 1);
    if (ll < r) quickinssort(ll, r);
}
void _quickinssort(vector<int> &a, int l, int r) {
    if (r - l <= 32) {
        _insertionsort(a, l, r);
        return;
    }
    int z = a[(l + r) / 2];
    int ll = l, rr = r - 1;
    while (ll <= rr) {
        while (a[ll] < z) ll++;
        while (a[rr] > z) rr--;
        if (ll <= rr) swap(a[ll++], a[rr--]);
    }
    if (l < rr) _quickinssort(a, l, rr + 1);
    if (ll < r) _quickinssort(a, ll, r);
}
void quickinssort(vector<int> &a) {
    _quickinssort(a, 0, a.size());
}

void heapsort(int* l, int* r) {
    heap<int> h;
    for (int *i = l; i < r; i++) h.push(*i);
    for (int *i = l; i < r; i++) {
        *i = h.top();
        h.pop();
    }
}
void _heapsort(vector<int> &a, int l, int r) {
    heap<int> h;
    for (int i = l; i < r; i++) h.push(a[i]);
    for (int i = l; i < r; i++) {
        a[i] = h.top();
        h.pop();
    }
}
void heapsort(vector<int> &a) {
    _heapsort(a, 0, a.size());
}

void merge(int* l, int* m, int* r, int* temp) {
    int *cl = l, *cr = m, cur = 0;
    while (cl < m && cr < r) {
        if (*cl < *cr) temp[cur++] = *cl, cl++;
        else temp[cur++] = *cr, cr++;
    }
    while (cl < m) temp[cur++] = *cl, cl++;
    while (cr < r) temp[cur++] = *cr, cr++;
    cur = 0;
    for (int* i = l; i < r; i++)
         *i = temp[cur++];
}
void _mergesort(int* l, int* r, int* temp) {
    if (r - l <= 1) return;
    int *m = l + (r - l) / 2;
    _mergesort(l, m, temp);
    _mergesort(m, r, temp);
    merge(l, m, r, temp);
}
void mergesort(int* l, int* r) {
    int* temp = new int[r - l];
    _mergesort(l, r, temp);
    delete temp;
}
void merge(vector<int> &a, int l, int r, int* temp) {
    int m = (l + r) / 2;
    int cl = l, cr = m, cur = 0;
    while (cl < m && cr < r) {
        if (a[cl] < a[cr]) temp[cur++] = a[cl++];
        else temp[cur++] = a[cr++];
    }
    while (cl < m) temp[cur++] = a[cl++];
    while (cr < r) temp[cur++] = a[cr++];
    for (int i = 0; i < r - l; i++)
        a[i + l] = temp[i];
}
void _mergesort(vector<int> &a, int l, int r, int* temp) {
    if (l >= r - 1) return;
    int m = (l + r) / 2;
    _mergesort(a, l, m, temp);
    _mergesort(a, m, r, temp);
    merge(a, l, r, temp);
}
void mergesort(vector<int> &a) {
    int* temp = new int[a.size()];
    _mergesort(a, 0, a.size(), temp);
    delete temp;
}

void _mergeinssort(int* l, int* r, int* temp) {
    if (r - l <= 32) {
        insertionsort(l, r);
        return;
    }
    int *m = l + (r - l) / 2;
    _mergeinssort(l, m, temp);
    _mergeinssort(m, r, temp);
    merge(l, m, r, temp);
}
void mergeinssort(int* l, int* r) {
    int* temp = new int[r - l];
    _mergeinssort(l, r, temp);
    delete temp;
}
void _mergeinssort(vector<int> &a, int l, int r, int* temp) {
    if (r - l <= 64) {
        _insertionsort(a, l, r);
        return;
    }
    int m = (l + r) / 2;
    _mergeinssort(a, l, m, temp);
    _mergeinssort(a, m, r, temp);
    merge(a, l, r, temp);
}
void mergeinssort(vector<int> &a) {
    int* temp = new int[a.size()];
    _mergeinssort(a, 0, a.size(), temp);
    delete temp;
}

int digit(int n, int k, int N, int M) {
    return (n >> (N * k) & (M - 1));
}
void _radixsort(int* l, int* r, int N) {
    int k = (32 + N - 1) / N;
    int M = 1 << N;
    int sz = r - l;
    int* b = new int[sz];
    int* c = new int[M];
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < M; j++)
            c[j] = 0;
        for (int* j = l; j < r; j++)
            c[digit(*j, i, N, M)]++;
        for (int j = 1; j < M; j++)
            c[j] += c[j - 1];
        for (int* j = r - 1; j >= l; j--)
            b[--c[digit(*j, i, N, M)]] = *j;
        int cur = 0;
        for (int* j = l; j < r; j++)
            *j = b[cur++];
    }
    delete b;
    delete c;
}
void radixsort(int* l, int* r) {
    _radixsort(l, r, 8);
}
void _radixsort(vector<int> &a, int N) {
    int k = (32 + N - 1) / N;
    int M = 1 << N;
    int n = a.size();
    vector<int> b(n);
    for (int i = 0; i < k; i++) {
        vector<int> c(M);
        for (int j = 0; j < n; j++)
            c[digit(a[j], i, N, M)]++;
        for (int j = 1; j < M; j++)
            c[j] += c[j - 1];
        for (int j = n - 1; j >= 0; j--)
            b[--c[digit(a[j], i, N, M)]] = a[j];
        swap(a, b);
    }
}
void radixsort(vector<int> &a) {
    _radixsort(a, 8);
}

void _radixsortmsd(int* l, int* r, int N, int d, int* temp) {
    if (d == -1) return;
    if (r - l <= 32) {
        insertionsort(l, r);
        return;
    }
    int M = 1 << N;
    int* cnt = new int[M + 1];
    for (int i = 0; i <= M; i++)
        cnt[i] = 0;
    int cur = 0;
    for (int* i = l; i < r; i++) {
        temp[cur++] = *i;
        cnt[digit(*i, d, N, M) + 1]++;
    }
    int sz = 0;
    for (int i = 1; i <= M; i++)
        if (cnt[i]) sz++;
    int* run = new int[sz];
    cur = 0;
    for (int i = 1; i <= M; i++)
        if (cnt[i]) run[cur++] = i - 1;
    for (int i = 1; i <= M; i++)
        cnt[i] += cnt[i - 1];
    cur = 0;
    for (int *i = l; i < r; i++) {
        int ind = digit(temp[cur], d, N, M);
        *(l + cnt[ind]) = temp[cur];
        cur++;
        cnt[ind]++;
    }
    for (int i = 0; i < sz; i++) {
        int r = run[i];
        if (r != 0) _radixsortmsd(l + cnt[r - 1], l + cnt[r], N, d - 1, temp);
        else _radixsortmsd(l, l + cnt[r], N, d - 1, temp);
    }
    delete run;
    delete cnt;
}
void radixsortmsd(int* l, int* r) {
    int* temp = new int[r - l];
    _radixsortmsd(l, r, 8, 3, temp);
    delete temp;
}

void _radixsortmsd(vector<int> &a, int N, int d) {
    if (d == -1 || a.size() <= 1) return;
    if (a.size() <= 64) {
        insertionsort(a);
        return;
    }
    int k = (32 + N - 1) / N;
    int M = 1 << N;
    int n = a.size();
    vector<vector<int>> c(M);
    for (int i = 0; i < n; i++)
        c[digit(a[i], d, N, M)].push_back(a[i]);
    for (int i = 0; i < M; i++)
        _radixsortmsd(c[i], N, d - 1);
    int cur = 0;
    for (int i = 0; i < M; i++)
        for (int j = 0; j < c[i].size(); j++)
            a[cur++] = c[i][j];
}
void radixsortmsd(vector<int> &a) {
    _radixsortmsd(a, 4, 7);
}

void _stlsort(vector<int> &a, int l, int r) {
    sort(a.begin() + l, a.begin() + r);
}
void stlsort(vector<int> &a) {
    sort(a.begin(), a.end());
}

void _timsort(int* l, int* r, int* temp) {
    int sz = r - l;
    if (sz <= 64) {
        insertionsort(l, r);
        return;
    }
    int minrun = sz, f = 0;
    while (minrun >= 64) {
        f |= minrun & 1;
        minrun >>= 1;
    }
    minrun += f;
    int* cur = l;
    stack<pair<int, int*>> s;
    while (cur < r) {
        int* c1 = cur;
        while (c1 < r - 1 && *c1 <= *(c1 + 1)) c1++;
        int* c2 = cur;
        while (c2 < r - 1 && *c2 >= *(c2 + 1)) c2++;
        if (c1 >= c2) {
            c1 = max(c1, cur + minrun - 1);
            c1 = min(c1, r - 1);
            insertionsort(cur, c1 + 1);
            s.push({ c1 - cur + 1, cur });
            cur = c1 + 1;
        }
        else {
            c2 = max(c2, cur + minrun - 1);
            c2 = min(c2, r - 1);
            reverse(cur, c2 + 1);
            insertionsort(cur, c2 + 1);
            s.push({ c2 - cur + 1, cur });
            cur = c2 + 1;
        }
        while (s.size() >= 3) {
            pair<int, int*> x = s.top();
            s.pop();
            pair<int, int*> y = s.top();
            s.pop();
            pair<int, int*> z = s.top();
            s.pop();
            if (z.first >= x.first + y.first && y.first >= x.first) {
                s.push(z);
                s.push(y);
                s.push(x);
                break;
            }
            else if (z.first >= x.first + y.first) {
                merge(y.second, x.second, x.second + x.first, temp);
                s.push(z);
                s.push({ x.first + y.first, y.second });
            }
            else {
                merge(z.second, y.second, y.second + y.first, temp);
                s.push({ z.first + y.first, z.second });
                s.push(x);
            }
        }
    }
    while (s.size() != 1) {
        pair<int, int*> x = s.top();
        s.pop();
        pair<int, int*> y = s.top();
        s.pop();
        if (x.second < y.second) swap(x, y);
        merge(y.second, x.second, x.second + x.first, temp);
        s.push({ y.first + x.first, y.second });
    }
}
void timsort(int* l, int* r) {
    int* temp = new int[r - l];
    _timsort(l, r, temp);
    delete temp;
}

void mergetim(vector<int> &a, int l, int m, int r, int* temp) {
    int cl = l, cr = m, cur = 0;
    while (cl < m && cr < r) {
        if (a[cl] < a[cr]) temp[cur++] = a[cl++];
        else temp[cur++] = a[cr++];
    }
    while (cl < m) temp[cur++] = a[cl++];
    while (cr < r) temp[cur++] = a[cr++];
    for (int i = 0; i < r - l; i++)
        a[i + l] = temp[i];
}
void _timsort(vector<int> &a, int l, int r, int* temp) {
    int sz = r - l;
    if (sz <= 64) {
        _insertionsort(a, l, r);
        return;
    }
    int minrun = sz, f = 0;
    while (minrun >= 64) {
        f |= minrun & 1;
        minrun >>= 1;
    }
    minrun += f;
    int cur = l;
    stack<pair<int, int>> s;
    while (cur < r) {
        int c1 = cur;
        while (c1 < r - 1 && a[c1] <= a[c1 + 1]) c1++;
        int c2 = cur;
        while (c2 < r - 1 && a[c2] >= a[c2 + 1]) c2++;
        if (c1 >= c2) {
            c1 = max(c1, cur + minrun - 1);
            c1 = min(c1, r - 1);
            _insertionsort(a, cur, c1 + 1);
            s.push({ c1 - cur + 1, cur });
            cur = c1 + 1;
        }
        else {
            c2 = max(c2, cur + minrun - 1);
            c2 = min(c2, r - 1);
            reverse(a.begin() + cur, a.begin() + c2 + 1);
            _insertionsort(a, cur, c2 + 1);
            s.push({ c2 - cur + 1, cur });
            cur = c2 + 1;
        }
        while (s.size() >= 3) {
            pair<int, int> x = s.top();
            s.pop();
            pair<int, int> y = s.top();
            s.pop();
            pair<int, int> z = s.top();
            s.pop();
            if (z.first >= x.first + y.first && y.first >= x.first) {
                s.push(z);
                s.push(y);
                s.push(x);
                break;
            }
            else if (z.first >= x.first + y.first) {
                mergetim(a, y.second, x.second, x.second + x.first, temp);
                s.push(z);
                s.push({ x.first + y.first, y.second });
            }
            else {
                mergetim(a, z.second, y.second, y.second + y.first, temp);
                s.push({ z.first + y.first, z.second });
                s.push(x);
            }
        }
    }
    while (s.size() != 1) {
        pair<int, int> x = s.top();
        s.pop();
        pair<int, int> y = s.top();
        s.pop();
        if (x.second < y.second) swap(x, y);
        mergetim(a, y.second, x.second, x.second + x.first, temp);
        s.push({ y.first + x.first, y.second });
    }
}
void timsort(vector<int> &a) {
    int* temp = new int[a.size()];
    _timsort(a, 0, a.size(), temp);
    delete temp;
}

void bucketinssort(vector<int> &a);
void _bucketinssort(vector<int> &a, int l, int r) {
    int sz = r - l;
    if (sz <= 128) {
        _insertionsort(a, l, r);
        return;
    }
    int minz = a[0], maxz = a[0];
    for (int i = l; i < r; i++) {
        minz = min(minz, a[i]);
        maxz = max(maxz, a[i]);
    }
    int diff = maxz - minz + 1;
    if (diff == 1) return;
    int numbuckets;
    numbuckets = max(2, int(4 * log2(diff)));
    vector<vector<int>> buckets(numbuckets);
    int range = (diff + numbuckets - 1) / numbuckets;
    for (int i = l; i < r; i++) {
        int ind = (a[i] - minz) / range;
        buckets[ind].push_back(a[i]);
    }
    for (int i = 0; i < numbuckets; i++)
        bucketinssort(buckets[i]);
    int cur = l;
    for (int i = 0; i < numbuckets; i++)
        for (int j = 0; j < buckets[i].size(); j++)
            a[cur++] = buckets[i][j];
}
void bucketinssort(vector<int> &a) {
    _bucketinssort(a, 0, a.size());
}
void bucketquicksort(vector<int> &a);
void _bucketquicksort(vector<int> &a, int l, int r) {
    int sz = r - l;
    if (sz <= 10000) {
        _quicksort(a, l, r);
        return;
    }
    int minz = a[0], maxz = a[0];
    for (int i = l; i < r; i++) {
        minz = min(minz, a[i]);
        maxz = max(maxz, a[i]);
    }
    int diff = maxz - minz + 1;
    if (diff == 1) return;
    int numbuckets;
    numbuckets = max(2, int(4 * log2(diff)));
    vector<vector<int>> buckets(numbuckets);
    int range = (diff + numbuckets - 1) / numbuckets;
    for (int i = l; i < r; i++) {
        int ind = (a[i] - minz) / range;
        buckets[ind].push_back(a[i]);
    }
    for (int i = 0; i < numbuckets; i++)
        bucketquicksort(buckets[i]);
    int cur = l;
    for (int i = 0; i < numbuckets; i++)
        for (int j = 0; j < buckets[i].size(); j++)
            a[cur++] = buckets[i][j];
}
void bucketquicksort(vector<int> &a) {
    _bucketquicksort(a, 0, a.size());
}
void bucketquickinssort(vector<int> &a);
void _bucketquickinssort(vector<int> &a, int l, int r) {
    int sz = r - l;
    if (sz <= 10000) {
        _quickinssort(a, l, r);
        return;
    }
    int minz = a[0], maxz = a[0];
    for (int i = l; i < r; i++) {
        minz = min(minz, a[i]);
        maxz = max(maxz, a[i]);
    }
    int diff = maxz - minz + 1;
    if (diff == 1) return;
    int numbuckets;
    numbuckets = max(2, int(4 * log2(diff)));
    vector<vector<int>> buckets(numbuckets);
    int range = (diff + numbuckets - 1) / numbuckets;
    for (int i = l; i < r; i++) {
        int ind = (a[i] - minz) / range;
        buckets[ind].push_back(a[i]);
    }
    for (int i = 0; i < numbuckets; i++)
        bucketquickinssort(buckets[i]);
    int cur = l;
    for (int i = 0; i < numbuckets; i++)
        for (int j = 0; j < buckets[i].size(); j++)
            a[cur++] = buckets[i][j];
}
void bucketquickinssort(vector<int> &a) {
    _bucketquickinssort(a, 0, a.size());
}

void _newbucketsort(int* l, int* r, int* temp) {
    if (r - l <= 64) {
        insertionsort(l, r);
        return;
    }
    int minz = *l, maxz = *l;
    bool is_sorted = true;
    for (int *i = l + 1; i < r; i++) {
        minz = min(minz, *i);
        maxz = max(maxz, *i);
        if (*i < *(i - 1)) is_sorted = false;
    }
    if (is_sorted) return;
    int diff = maxz - minz + 1;
    int numbuckets;
    if (r - l <= 1e7) numbuckets = 1500;
    else numbuckets = 3000;
    int range = (diff + numbuckets - 1) / numbuckets;
    int* cnt = new int[numbuckets + 1];
    for (int i = 0; i <= numbuckets; i++)
        cnt[i] = 0;
    int cur = 0;
    for (int* i = l; i < r; i++) {
        temp[cur++] = *i;
        int ind = (*i - minz) / range;
        cnt[ind + 1]++;
    }
    int sz = 0;
    for (int i = 1; i <= numbuckets; i++)
        if (cnt[i]) sz++;
    int* run = new int[sz];
    cur = 0;
    for (int i = 1; i <= numbuckets; i++)
        if (cnt[i]) run[cur++] = i - 1;
    for (int i = 1; i <= numbuckets; i++)
        cnt[i] += cnt[i - 1];
    cur = 0;
    for (int *i = l; i < r; i++) {
        int ind = (temp[cur] - minz) / range;
        *(l + cnt[ind]) = temp[cur];
        cur++;
        cnt[ind]++;
    }
    for (int i = 0; i < sz; i++) {
        int r = run[i];
        if (r != 0) _newbucketsort(l + cnt[r - 1], l + cnt[r], temp);
        else _newbucketsort(l, l + cnt[r], temp);
    }
    delete run;
    delete cnt;
}
void newbucketsort(int* l, int* r) {
    int *temp = new int[r - l];
    _newbucketsort(l, r, temp);
    delete temp;
}
void _newbucketsort(vector<int> &a, int l, int r, int* temp) {
    if (r - l <= 64) {
        _insertionsort(a, l, r);
        return;
    }
    int minz = a[l], maxz = a[l];
    bool is_sorted = true;
    for (int i = l + 1; i < r; i++) {
        minz = min(minz, a[i]);
        maxz = max(maxz, a[i]);
        if (a[i] < a[i - 1]) is_sorted = false;
    }
    if (is_sorted) return;
    int diff = maxz - minz + 1;
    int numbuckets = 1500;
    //numbuckets = min(diff, int(4.0 * log2(diff)));
    //numbuckets = min(diff, int(6.0 * log2(r - l)));
    //numbuckets = min(diff, min(int(4.0 * log2(diff)),
    //  int(6.0 * log2(r - l))));
    int range = (diff + numbuckets - 1) / numbuckets;
    vector<int> cnt(numbuckets + 1);
    cnt[0] = l;
    for (int i = l; i < r; i++) {
        temp[i] = a[i];
        int ind = (a[i] - minz) / range;
        cnt[ind + 1]++;
    }
    vector<int> run;
    int sz = 0;
    for (int i = 1; i <= numbuckets; i++)
        if (cnt[i]) sz++;
    run.resize(sz);
    int cur = 0;
    for (int i = 1; i <= numbuckets; i++)
        if (cnt[i]) run[cur++] = i - 1;
    for (int i = 1; i <= numbuckets; i++)
        cnt[i] += cnt[i - 1];
    for (int i = l; i < r; i++) {
        int ind = (temp[i] - minz) / range;
        a[cnt[ind]++] = temp[i];
    }
    for (int i = 0; i < sz; i++) {
        int r = run[i];
        if (r != 0) _newbucketsort(a, cnt[r - 1], cnt[r], temp);
        else _newbucketsort(a, l, cnt[r], temp);
    }
}
void newbucketsort(vector<int> &a) {
    int *temp = new int[a.size()];
    _newbucketsort(a, 0, a.size(), temp);
    delete temp;
}

void treesort(int* l, int* r) {
    multiset<int> m;
    for (int *i = l; i < r; i++)
        m.insert(*i);
    for (int q : m)
        *l = q, l++;
}
void _treesort(vector<int> &a, int l, int r) {
    multiset<int> m;
    for (int i = l; i < r; i++)
        m.insert(a[i]);
    int cur = l;
    for (int q : m)
        a[cur++] = q;
}
void treesort(vector<int> &a) {
    _treesort(a, 0, a.size());
}

void bitseqsort(int* l, int* r, bool inv) {
    if (r - l <= 1) return;
    int *m = l + (r - l) / 2;
    for (int *i = l, *j = m; i < m && j < r; i++, j++) {
        if (inv ^ (*i > *j)) swap(*i, *j);
    }
    bitseqsort(l, m, inv);
    bitseqsort(m, r, inv);
}
void makebitonic(int* l, int* r) {
    if (r - l <= 1) return;
    int *m = l + (r - l) / 2;
    makebitonic(l, m);
    bitseqsort(l, m, 0);
    makebitonic(m, r);
    bitseqsort(m, r, 1);
}
void bitonicsort(int* l, int* r) {
    int n = 1;
    int inf = *max_element(l, r) + 1;
    while (n < r - l) n *= 2;
    int* a = new int[n];
    int cur = 0;
    for (int *i = l; i < r; i++)
        a[cur++] = *i;
    while (cur < n) a[cur++] = inf;
    makebitonic(a, a + n);
    bitseqsort(a, a + n, 0);
    cur = 0;
    for (int *i = l; i < r; i++)
        *i = a[cur++];
    delete a;
}
void bitseqsort(vector<int> &a, int l, int r, bool inv) {
    if (l == r - 1) return;
    int m = (l + r) / 2;
    for (int i = l, j = m; i < m && j < r; i++, j++) {
        if (inv ^ (a[i] > a[j])) swap(a[i], a[j]);
    }
    bitseqsort(a, l, m, inv);
    bitseqsort(a, m, r, inv);
}
void makebitonic(vector<int> &a, int l, int r) {
    if (r - l <= 1) return;
    int m = (l + r) / 2;
    makebitonic(a, l, m);
    bitseqsort(a, l, m, 0);
    makebitonic(a, m, r);
    bitseqsort(a, m, r, 1);
}
void bitonicsort(vector<int> &a) {
    int n = 1;
    int inf = *max_element(a.begin(), a.end()) + 1;
    while (n < a.size()) n *= 2;
    a.resize(n, inf);
    makebitonic(a, 0, n);
    bitseqsort(a, 0, n, 0);
    while (a.back() == inf && !a.empty()) a.pop_back();
}

/*void(*func1[5])(vector<int>&) =
{ bubblesort, gnomesort, insertionsort, selectionsort, shakersort };
string names1[5] =
{ "bubblesort", "gnomesort", "insertionsort", "selectionsort", "shakersort" };
void(*func2[4])(vector<int>&) =
{ bitonicsort, shellsorthib, shellsortpratt, treesort };
string names2[4] =
{ "bitonicsort", "shellsorthib", "shellsortpratt", "treesort" };
void(*func3[18])(vector<int>&) =
{ combsort, bucketinssort, heapsort, stlsort, quicksort, quickinssort, mergesort,
mergeinssort, shellsort, shellsortsedgwick, radixsort, radixsortmsd, timsort,
myshell1, myshell2, myshell3, bucketquicksort, bucketquickinssort };
string names3[18] =
{ "combsort", "bucketinssort", "heapsort", "stlsort", "quicksort", "quickinssort",
"mergesort", "mergeinssort", "shellsort", "shellsortsedgwick", "radixsort",
"radixsortmsd", "timsort", "myshell1", "myshell2", "myshell3",
"bucketquicksort", "bucketquickinssort" };*/

const int N = 100000000;
int arr[N];

void testprint(int n, string section) {
    string s = section + "\\test" + to_string(curt) + ".txt";
    freopen(s.c_str(), "w", stdout);
    printf("%d\n", n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    fclose(stdout);
    curt++;
}
void testprint(vector<int> &a, string section) {
    string s = section + "\\test" + to_string(curt) + ".txt";
    freopen(s.c_str(), "w", stdout);
    int n = a.size();
    printf("%d\n", n);
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    fclose(stdout);
    curt++;
}

void testgen1() {
    string section = "Random";
    vector<int> arr;
    for (int q = 0; q < 4; q++) {
        int n = len[q];
        if (arr.size() != n) arr.resize(n);
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)10;
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1000;
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e5;
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e7;
            testprint(arr, section);
        }
        for (int w = 0; w < 10; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            testprint(arr, section);
        }
    }
}
void testgen2() {
    string section = "Part sorted";
    vector<int> arr;
    for (int q = 0; q < 4; q++) {
        int n = len[q];
        if (arr.size() != n) arr.resize(n);
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            int cur = 0;
            while (cur < n) {
                int l = randint() % min((int)10, n - cur) + 1;
                sort(arr.begin() + cur, arr.begin() + cur + l);
                cur += l;
            }
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            int cur = 0;
            while (cur < n) {
                int l = randint() % min((int)100, n - cur) + 1;
                sort(arr.begin() + cur, arr.begin() + cur + l);
                cur += l;
            }
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            int cur = 0;
            while (cur < n) {
                int l = randint() % min((int)1000, n - cur) + 1;
                sort(arr.begin() + cur, arr.begin() + cur + l);
                cur += l;
            }
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            int cur = 0;
            while (cur < n) {
                int l = randint() % min((int)1e4, n - cur) + 1;
                sort(arr.begin() + cur, arr.begin() + cur + l);
                cur += l;
            }
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            int cur = 0;
            while (cur < n) {
                int l = randint() % min((int)1e5, n - cur) + 1;
                sort(arr.begin() + cur, arr.begin() + cur + l);
                cur += l;
            }
            testprint(arr, section);
        }
        if (n == 1e5) continue;
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            int cur = 0;
            while (cur < n) {
                int l = randint() % min((int)1e6, n - cur) + 1;
                sort(arr.begin() + cur, arr.begin() + cur + l);
                cur += l;
            }
            testprint(arr, section);
        }
        if (n == 1e6) continue;
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            int cur = 0;
            while (cur < n) {
                int l = randint() % min((int)1e7, n - cur) + 1;
                sort(arr.begin() + cur, arr.begin() + cur + l);
                cur += l;
            }
            testprint(arr, section);
        }
        if (n == 1e7) continue;
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            int cur = 0;
            while (cur < n) {
                int l = randint() % min((int)1e8, n - cur) + 1;
                sort(arr.begin() + cur, arr.begin() + cur + l);
                cur += l;
            }
            testprint(arr, section);
        }
    }
}
void testgen3() {
    string section = "Swaps";
    vector<int> arr;
    for (int q = 0; q < 4; q++) {
        int n = len[q];
        if (arr.size() != n) arr.resize(n);
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            radixsort(arr);
            for (int d = 0; d < 10; d++) {
                int p1 = 1, p2 = 1;
                while (p1 == p2) {
                    p1 = randint() % n;
                    p2 = randint() % n;
                }
                swap(arr[p1], arr[p2]);
            }
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            radixsort(arr);
            for (int d = 0; d < 100; d++) {
                int p1 = 1, p2 = 1;
                while (p1 == p2) {
                    p1 = randint() % n;
                    p2 = randint() % n;
                }
                swap(arr[p1], arr[p2]);
            }
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            radixsort(arr);
            for (int d = 0; d < 1000; d++) {
                int p1 = 1, p2 = 1;
                while (p1 == p2) {
                    p1 = randint() % n;
                    p2 = randint() % n;
                }
                swap(arr[p1], arr[p2]);
            }
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            radixsort(arr);
            for (int d = 0; d < 10000; d++) {
                int p1 = 1, p2 = 1;
                while (p1 == p2) {
                    p1 = randint() % n;
                    p2 = randint() % n;
                }
                swap(arr[p1], arr[p2]);
            }
            testprint(arr, section);
        }
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            radixsort(arr);
            for (int d = 0; d < 1e5; d++) {
                int p1 = 1, p2 = 1;
                while (p1 == p2) {
                    p1 = randint() % n;
                    p2 = randint() % n;
                }
                swap(arr[p1], arr[p2]);
            }
            testprint(arr, section);
        }
        if (n == 1e5) continue;
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            radixsort(arr);
            for (int d = 0; d < 1e6; d++) {
                int p1 = 1, p2 = 1;
                while (p1 == p2) {
                    p1 = randint() % n;
                    p2 = randint() % n;
                }
                swap(arr[p1], arr[p2]);
            }
            testprint(arr, section);
        }
        if (n == 1e6) continue;
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            radixsort(arr);
            for (int d = 0; d < 1e7; d++) {
                int p1 = 1, p2 = 1;
                while (p1 == p2) {
                    p1 = randint() % n;
                    p2 = randint() % n;
                }
                swap(arr[p1], arr[p2]);
            }
            testprint(arr, section);
        }
        if (n == 1e7) continue;
        for (int w = 0; w < 5; w++) {
            for (int j = 0; j < n; j++)
                arr[j] = randint() % (int)1e9;
            radixsort(arr);
            for (int d = 0; d < 1e8; d++) {
                int p1 = 1, p2 = 1;
                while (p1 == p2) {
                    p1 = randint() % n;
                    p2 = randint() % n;
                }
                swap(arr[p1], arr[p2]);
            }
            testprint(arr, section);
        }
    }
}
void testgen4() {
    string section = "Additional";
    for (int q = 0; q < 4; q++) {
        int n = len[q];
        for (int i = 0; i < n; i++)
            arr[i] = i + 1;
        testprint(n, section);
        for (int i = 0; i < n; i++)
            arr[i] = n - i;
        testprint(n, section);
        for (int w = 0; w < 2; w++) {
            for (int i = 0; i < n; i++)
                arr[i] = randint() % (int)1e9;
            radixsort(arr, arr + n);
            testprint(n, section);
        }
        for (int w = 0; w < 2; w++) {
            for (int i = 0; i < n; i++)
                arr[i] = randint() % (int)1e9;
            radixsort(arr, arr + n);
            reverse(arr, arr + n);
            testprint(n, section);
        }
        for (int w = 0; w < 2; w++) {
            for (int i = 0; i < n; i++)
                arr[i] = i + 1;
            for (int i = 0; i < 10; i++) {
                int pos = randint() % n;
                int v = randint() % (int)1e9;
                arr[pos] = v;
            }
            testprint(n, section);
        }
        for (int w = 0; w < 2; w++) {
            for (int i = 0; i < n; i++)
                arr[i] = i + 1;
            for (int i = 0; i < 100; i++) {
                int pos = randint() % n;
                int v = randint() % (int)1e9;
                arr[pos] = v;
            }
            testprint(n, section);
        }
        for (int w = 0; w < 2; w++) {
            for (int i = 0; i < n; i++)
                arr[i] = i + 1;
            for (int i = 0; i < 1000; i++) {
                int pos = randint() % n;
                int v = randint() % (int)1e9;
                arr[pos] = v;
            }
            testprint(n, section);
        }
        for (int w = 0; w < 2; w++) {
            for (int i = 0; i < n; i++)
                arr[i] = i + 1;
            for (int i = 0; i < 1e4; i++) {
                int pos = randint() % n;
                int v = randint() % (int)1e9;
                arr[pos] = v;
            }
            testprint(n, section);
        }
        for (int w = 0; w < 2; w++) {
            for (int i = 0; i < n; i++)
                arr[i] = i + 1;
            for (int i = 0; i < 1e5; i++) {
                int pos = randint() % n;
                int v = randint() % (int)1e9;
                arr[pos] = v;
            }
            testprint(n, section);
        }
        if (n > 1e5) {
            for (int w = 0; w < 2; w++) {
                for (int i = 0; i < n; i++)
                    arr[i] = i + 1;
                for (int i = 0; i < 1e6; i++) {
                    int pos = randint() % n;
                    int v = randint() % (int)1e9;
                    arr[pos] = v;
                }
                testprint(n, section);
            }
            if (n > 1e6) {
                for (int w = 0; w < 2; w++) {
                    for (int i = 0; i < n; i++)
                        arr[i] = i + 1;
                    for (int i = 0; i < 1e7; i++) {
                        int pos = randint() % n;
                        int v = randint() % (int)1e9;
                        arr[pos] = v;
                    }
                    testprint(n, section);
                }
                if (n > 1e7) {
                    for (int w = 0; w < 2; w++) {
                        for (int i = 0; i < n; i++)
                            arr[i] = i + 1;
                        for (int i = 0; i < 1e8; i++) {
                            int pos = randint() % n;
                            int v = randint() % (int)1e9;
                            arr[pos] = v;
                        }
                        testprint(n, section);
                    }
                }
            }
        }
        for (int w = 0; w < 3; w++) {
            int repeat = randint() % (int)1e9;
            int nn = n / 10;
            for (int i = 0; i < nn; i++)
                arr[i] = repeat;
            for (int i = nn; i < n; i++)
                arr[i] = randint() % (int)1e9;
            random_shuffle(arr, arr + n);
            testprint(n, section);
        }
        for (int w = 0; w < 3; w++) {
            int repeat = randint() % (int)1e9;
            int nn = n / 4;
            for (int i = 0; i < nn; i++)
                arr[i] = repeat;
            for (int i = nn; i < n; i++)
                arr[i] = randint() % (int)1e9;
            random_shuffle(arr, arr + n);
            testprint(n, section);
        }
        for (int w = 0; w < 3; w++) {
            int repeat = randint() % (int)1e9;
            int nn = n / 2;
            for (int i = 0; i < nn; i++)
                arr[i] = repeat;
            for (int i = nn; i < n; i++)
                arr[i] = randint() % (int)1e9;
            random_shuffle(arr, arr + n);
            testprint(n, section);
        }
        for (int w = 0; w < 3; w++) {
            int repeat = randint() % (int)1e9;
            int nn = 3 * n / 4;
            for (int i = 0; i < nn; i++)
                arr[i] = repeat;
            for (int i = nn; i < n; i++)
                arr[i] = randint() % (int)1e9;
            random_shuffle(arr, arr + n);
            testprint(n, section);
        }
        for (int w = 0; w < 3; w++) {
            int repeat = randint() % (int)1e9;
            int nn = 9 * n / 10;
            for (int i = 0; i < nn; i++)
                arr[i] = repeat;
            for (int i = nn; i < n; i++)
                arr[i] = randint() % (int)1e9;
            random_shuffle(arr, arr + n);
            testprint(n, section);
        }
    }
}
int cur[N];
int ans[N];
int made[N];
int read(string &test) {
    freopen(test.c_str(), "r", stdin);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &cur[i]);
    for (int i = 0; i < n; i++)
        ans[i] = cur[i];
    fclose(stdin);
    radixsort(ans, ans + n);
    return n;
}
bool check(int n) {
    bool right = true;
    for (int i = 0; i < n; i++)
        if (ans[i] != made[i])
            right = false;
    return right;
}
bool fasttest(string section, int num) {
    string s = section + "\\test" + to_string(num) + ".txt";
    freopen(s.c_str(), "r", stdin);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &cur[i]);
    for (int i = 0; i < n; i++)
        ans[i] = cur[i];
    radixsort(ans, ans + n);
    int t1, t2;
    for (int run = 0; run < 20; run++) {
        for (int i = 0; i < n; i++)
            made[i] = cur[i];
        t1 = clock();
        mergesort(made, made + n);
        t2 = clock();
        if (check(n)) cout << t2 - t1 << " ";
        else {
            cout << "incorrect";
            return false;
        }
    }
    return true;
}
void fasttestpart() {
    string output;
    output = "Results\\shellsorthibr1e6.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 31; t <= 60; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            shellsorthib(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\shellsorthibr1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 61; t <= 90; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            shellsorthib(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\shellsorthibp1e6.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 26; t <= 55; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            shellsorthib(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\shellsorthibp1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            shellsorthib(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\shellsorthibs1e6.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 26; t <= 55; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            shellsorthib(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\shellsorthibs1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            shellsorthib(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\shellsorthiba1e6.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 32; t <= 64; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            shellsorthib(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\shellsorthiba1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 65; t <= 99; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            shellsorthib(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
}
void exttest() {
    string output;
    output = "Results\\Random\\combsort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 61; t <= 90; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            combsort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Random\\quicksort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 61; t <= 90; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quicksort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Random\\quickinssort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 61; t <= 90; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quickinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Random\\mergeinssort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 61; t <= 90; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            mergeinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Random\\radixsortmsd1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 61; t <= 90; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            radixsortmsd(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Random\\quicksort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 120; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quicksort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Random\\quickinssort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 120; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quickinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Random\\mergeinssort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 120; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            mergeinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Random\\radixsortmsd1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 120; t++) {
        int n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            radixsortmsd(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Part sorted\\quicksort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quicksort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Part sorted\\quickinssort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quickinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Part sorted\\mergeinssort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            mergeinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Part sorted\\radixsortmsd1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            radixsortmsd(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Part sorted\\quicksort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 130; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quicksort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Part sorted\\quickinssort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 130; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quickinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Part sorted\\mergeinssort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 130; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            mergeinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Part sorted\\radixsortmsd1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 130; t++) {
        int n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            radixsortmsd(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Swaps\\quicksort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quicksort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Swaps\\quickinssort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quickinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Swaps\\mergeinssort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            mergeinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Swaps\\radixsortmsd1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 56; t <= 90; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            radixsortmsd(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Swaps\\quicksort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 130; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quicksort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Swaps\\quickinssort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 130; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quickinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Swaps\\mergeinssort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 130; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            mergeinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Swaps\\radixsortmsd1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 91; t <= 130; t++) {
        int n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            radixsortmsd(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Additional\\combsort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 65; t <= 99; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            combsort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Additional\\quicksort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 65; t <= 99; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quicksort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Additional\\quickinssort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 65; t <= 99; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quickinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Additional\\mergeinssort1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 65; t <= 99; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            mergeinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Additional\\radixsortmsd1e7.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 65; t <= 99; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            radixsortmsd(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Additional\\quicksort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 100; t <= 136; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quicksort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Additional\\quickinssort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 100; t <= 136; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            quickinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Additional\\mergeinssort1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 100; t <= 136; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            mergeinssort(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
    output = "Results\\Additional\\radixsortmsd1e8.txt";
    freopen(output.c_str(), "w", stdout);
    for (int t = 100; t <= 136; t++) {
        int n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            int t1 = clock();
            radixsortmsd(made, made + n);
            int t2 = clock();
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
        }
    }
    fclose(stdout);
}
void fulltest1() {
    // Random
    // 1 - 30   : 10^5
    // 31 - 60  : 10^6
    // 61 - 90  : 10^7
    // 91 - 120 : 10^8

    string input, output;
    int n, t1, t2;

    for (int t = 1; t <= 30; t++) {
        n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bubblesort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\bubblesort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shakersort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\shakersort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            selectionsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\selectionsort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            insertionsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\insertionsort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            gnomesort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\gnomesort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 31; t <= 60; t++) {
        n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bitonicsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\bitonicsort1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            treesort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\treesort1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsorthib(made, made + n);
            t2 = clock();
            output = "Results\\Random\\shellsorthib1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortpratt(made, made + n);
            t2 = clock();
            output = "Results\\Random\\shellsortpratt1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 61; t <= 90; t++) {
        n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bitonicsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\bitonicsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            treesort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\treesort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsorthib(made, made + n);
            t2 = clock();
            output = "Results\\Random\\shellsorthib1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortpratt(made, made + n);
            t2 = clock();
            output = "Results\\Random\\shellsortpratt1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 61; t <= 90; t++) {
        n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            combsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\combsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            newbucketsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\bucketsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            heapsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\heapsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            sort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\stlsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quicksort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\quicksort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quickinssort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\quickinssort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergesort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\mergesort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergeinssort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\mergeinssort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\shellsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortsedgwick(made, made + n);
            t2 = clock();
            output = "Results\\Random\\shellsortsedgwick1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            radixsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\radixsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            timsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\timsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell1(made, made + n);
            t2 = clock();
            output = "Results\\Random\\myshell1_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell2(made, made + n);
            t2 = clock();
            output = "Results\\Random\\myshell2_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell3(made, made + n);
            t2 = clock();
            output = "Results\\Random\\myshell3_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 91; t <= 120; t++) {
        n = read("Random\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            combsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\combsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            newbucketsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\bucketsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            heapsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\heapsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            sort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\stlsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quicksort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\quicksort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quickinssort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\quickinssort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergesort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\mergesort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergeinssort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\mergeinssort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\shellsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortsedgwick(made, made + n);
            t2 = clock();
            output = "Results\\Random\\shellsortsedgwick1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            radixsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\radixsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            timsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\timsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell1(made, made + n);
            t2 = clock();
            output = "Results\\Random\\myshell1_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell2(made, made + n);
            t2 = clock();
            output = "Results\\Random\\myshell2_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell3(made, made + n);
            t2 = clock();
            output = "Results\\Random\\myshell3_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
}
void fulltest2() {
    // Part sorted
    // 1 - 25   : 10^5
    // 26 - 55  : 10^6
    // 56 - 90  : 10^7
    // 91 - 130 : 10^8

    string input, output;
    int n, t1, t2;

    for (int t = 1; t <= 25; t++) {
        n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bubblesort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\bubblesort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shakersort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\shakersort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            selectionsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\selectionsort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            insertionsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\insertionsort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            gnomesort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\gnomesort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 26; t <= 55; t++) {
        n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bitonicsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\bitonicsort1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            treesort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\treesort1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsorthib(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\shellsorthib1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortpratt(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\shellsortpratt1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 56; t <= 90; t++) {
        n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bitonicsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\bitonicsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            treesort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\treesort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsorthib(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\shellsorthib1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortpratt(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\shellsortpratt1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 56; t <= 90; t++) {
        n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            combsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\combsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            newbucketsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\bucketsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            heapsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\heapsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            sort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\stlsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quicksort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\quicksort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quickinssort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\quickinssort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergesort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\mergesort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergeinssort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\mergeinssort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\shellsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortsedgwick(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\shellsortsedgwick1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            radixsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\radixsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            timsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\timsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell1(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\myshell1_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell2(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\myshell2_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell3(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\myshell3_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 91; t <= 130; t++) {
        n = read("Part sorted\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            combsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\combsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            newbucketsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\bucketsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            heapsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\heapsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            sort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\stlsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quicksort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\quicksort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quickinssort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\quickinssort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergesort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\mergesort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergeinssort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\mergeinssort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\shellsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortsedgwick(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\shellsortsedgwick1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            radixsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\radixsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            timsort(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\timsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell1(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\myshell1_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell2(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\myshell2_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell3(made, made + n);
            t2 = clock();
            output = "Results\\Part sorted\\myshell3_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
}
void fulltest3() {
    // Swaps
    // 1 - 25   : 10^5
    // 26 - 55  : 10^6
    // 56 - 90  : 10^7
    // 91 - 130 : 10^8

    string input, output;
    int n, t1, t2;

    for (int t = 1; t <= 25; t++) {
        n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bubblesort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\bubblesort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shakersort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\shakersort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            selectionsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\selectionsort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            insertionsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\insertionsort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            gnomesort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\gnomesort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 26; t <= 55; t++) {
        n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bitonicsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\bitonicsort1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            treesort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\treesort1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsorthib(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\shellsorthib1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortpratt(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\shellsortpratt1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 56; t <= 90; t++) {
        n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bitonicsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\bitonicsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            treesort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\treesort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsorthib(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\shellsorthib1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortpratt(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\shellsortpratt1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 56; t <= 90; t++) {
        n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            combsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\combsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            newbucketsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\bucketsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            heapsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\heapsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            sort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\stlsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quicksort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\quicksort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quickinssort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\quickinssort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergesort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\mergesort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergeinssort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\mergeinssort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\shellsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortsedgwick(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\shellsortsedgwick1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            radixsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\radixsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            timsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\timsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell1(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\myshell1_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell2(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\myshell2_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell3(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\myshell3_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 91; t <= 130; t++) {
        n = read("Swaps\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            combsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\combsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            newbucketsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\bucketsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            heapsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\heapsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            sort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\stlsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quicksort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\quicksort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quickinssort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\quickinssort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergesort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\mergesort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergeinssort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\mergeinssort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\shellsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortsedgwick(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\shellsortsedgwick1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            radixsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\radixsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            timsort(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\timsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell1(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\myshell1_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell2(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\myshell2_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell3(made, made + n);
            t2 = clock();
            output = "Results\\Swaps\\myshell3_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
}
void fulltest4() {
    // Additional
    // 1 - 31    : 10^5
    // 32 - 64   : 10^6
    // 65 - 99   : 10^7
    // 100 - 136 : 10^8

    string input, output;
    int n, t1, t2;

    for (int t = 1; t <= 31; t++) {
        n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bubblesort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\bubblesort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shakersort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\shakersort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            selectionsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\selectionsort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            insertionsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\insertionsort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            gnomesort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\gnomesort1e5.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 32; t <= 64; t++) {
        n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bitonicsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\bitonicsort1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            treesort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\treesort1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsorthib(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\shellsorthib1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortpratt(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\shellsortpratt1e6.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 65; t <= 99; t++) {
        n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            bitonicsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\bitonicsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            treesort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\treesort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsorthib(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\shellsorthib1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortpratt(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\shellsortpratt1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 65; t <= 99; t++) {
        n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            combsort(made, made + n);
            t2 = clock();
            output = "Results\\Random\\combsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            newbucketsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\bucketsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            heapsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\heapsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            sort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\stlsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quicksort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\quicksort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quickinssort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\quickinssort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergesort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\mergesort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergeinssort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\mergeinssort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\shellsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortsedgwick(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\shellsortsedgwick1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            radixsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\radixsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            timsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\timsort1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell1(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\myshell1_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell2(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\myshell2_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell3(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\myshell3_1e7.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
    for (int t = 100; t <= 136; t++) {
        n = read("Additional\\test" + to_string(t) + ".txt");
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            combsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\combsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            newbucketsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\bucketsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            heapsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\heapsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            sort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\stlsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quicksort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\quicksort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            quickinssort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\quickinssort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergesort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\mergesort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            mergeinssort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\mergeinssort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\shellsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            shellsortsedgwick(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\shellsortsedgwick1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            radixsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\radixsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            timsort(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\timsort1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell1(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\myshell1_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell2(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\myshell2_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
        for (int run = 1; run <= 20; run++) {
            for (int i = 0; i < n; i++)
                made[i] = cur[i];
            t1 = clock();
            myshell3(made, made + n);
            t2 = clock();
            output = "Results\\Additional\\myshell3_1e8.txt";
            freopen(output.c_str(), "a", stdout);
            if (!check(n)) printf("incorrect");
            else printf("%d", t2 - t1);
            if (run != 20) printf(" ");
            else printf("\n");
            fclose(stdout);
        }
    }
}
int main() {
    srand(time(0));
    //fulltest4();
    //fulltest1();
    //fulltest2();
    //fulltest3();
}