#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();
}