UVa 11342 - Three-square

// UVa 11342 - Three-square

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

#define MaxN 50000

int main() {
	int T[4][MaxN + 1];
	memset(T, 127, sizeof(T));
	vector<int> v1, v2;
	int oo = T[0][0];
	for (int i = 0; i * i <= MaxN; i++) {
		T[1][i * i] = i;
		v1.push_back(i * i);
	}
	for (int j = 0; j < v1.size(); j++) {
		int f = v1[j];
		for (int i = 0; i * i + f <= MaxN; i++)
			if (T[2][i * i + f] == oo) {
				T[2][i * i + f] = i;
				v2.push_back(i * i + f);
			}
	}
	for (int j = 0; j < v2.size(); j++) {
		int f = v2[j];
		for (int i = 0; i * i + f <= MaxN; i++)
			if (T[3][i * i + f] == oo)
				T[3][i * i + f] = i;
	}

	int cases;
	for (cin >> cases; cases; cases--) {
		int n;
		cin >> n;
		if (T[3][n] == oo)
			cout << "-1" << endl;
		else {
			int s[4];
			for (int i = 3; i >= 1; i--) {
				s[i] = T[i][n];
				n -= T[i][n] * T[i][n];
			}
			cout << s[1] << " " << s[2] << " " << s[3] << endl;
		}
	}
	return 0;
}