#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
using namespace std;
const int n = 5000;
const int m = 5;
const int Dmax = n + 100;
int D, D2, itor[Dmax] = {}, itor2[Dmax], rtoi[Dmax], rtoi2[Dmax];
long long d[n];
int p[n];
int main(void)
{
int a, b, g, i, j, k, r, r2, ra, rb;
for (D2 = n + 1, k = 0; k < 2; k++) {
for (; D2 <= Dmax; D2++) {
fill(rtoi2, rtoi2 + D2, 0);
for (i = 1; i <= n; i++) {
r = (long long)i * i * i % D2;
if (rtoi2[r]) break; else rtoi2[r] = i;
}
if (i > n) break;
}
if (D2 > Dmax) return cout << "D not found." << endl, -1;
if (k == 0) D = D2++, copy(rtoi2, rtoi2 + D, rtoi);
}
for (r = 0; r < D; r++) itor[rtoi[r]] = r;
for (r = 0; r < D2; r++) itor2[rtoi2[r]] = r;
vector<vector<array<int, 2>>> AB(D2);
vector<int> R2(D2);
for (r = 1; r < D; r++) {
for (r2 = 0; r2 < D2; r2++) AB[r2].clear();
R2.clear();
for (a = 2; a <= n; a++) {
ra = itor[a];
if ((rb = ra - r) < 0) rb += D;
if (b = rtoi[rb], b == 0 || b >= a) continue;
if ((r2 = itor2[a] - itor2[b]) < 0) r2 += D2;
AB[r2].push_back({a, b});
if (AB[r2].size() == m) R2.push_back(r2);
}
for (g = 0; g < R2.size(); g++) {
auto &ab = AB[R2[g]];
for (k = 0, i = 0; i < ab.size(); i++) {
a = ab[i][0];
b = ab[i][1];
d[k] = (long long)a * a * a - (long long)b * b * b;
p[k] = k;
k++;
}
sort(p, p + k, [](int x, int y) {return d[x] < d[y];});
for (i = 0; i < k - m + 1; i++) {
if (d[p[i]] != d[p[i + m - 1]]) continue;
cout << d[p[i]] << ": ";
for (j = i + m; j < k && d[p[j]] == d[p[i]]; j++);
sort(p + i, p + j, [&](int x, int y) {return ab[x][0] < ab[y][0];});
for_each(p + i, p + j, [&](int &x) {
a = ab[x][0];
b = ab[x][1];
cout << (&x > p + i ? ", (" : "(") << a << ", " << b << ")";
});
cout << endl;
i = j - 1;
}
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8YXJyYXk+CiNpbmNsdWRlIDx2ZWN0b3I+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IG4gPSA1MDAwOwpjb25zdCBpbnQgbSA9IDU7CmNvbnN0IGludCBEbWF4ID0gbiArIDEwMDsKCmludCBELCBEMiwgaXRvcltEbWF4XSA9IHt9LCBpdG9yMltEbWF4XSwgcnRvaVtEbWF4XSwgcnRvaTJbRG1heF07CmxvbmcgbG9uZyBkW25dOwppbnQgcFtuXTsKCmludCBtYWluKHZvaWQpCnsKICAgIGludCBhLCBiLCBnLCBpLCBqLCBrLCByLCByMiwgcmEsIHJiOwoKICAgIGZvciAoRDIgPSBuICsgMSwgayA9IDA7IGsgPCAyOyBrKyspIHsKICAgICAgICBmb3IgKDsgRDIgPD0gRG1heDsgRDIrKykgewogICAgICAgICAgICBmaWxsKHJ0b2kyLCBydG9pMiArIEQyLCAwKTsKICAgICAgICAgICAgZm9yIChpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICAgICAgICAgIHIgPSAobG9uZyBsb25nKWkgKiBpICogaSAlIEQyOwogICAgICAgICAgICAgICAgaWYgKHJ0b2kyW3JdKSBicmVhazsgZWxzZSBydG9pMltyXSA9IGk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKGkgPiBuKSBicmVhazsKICAgICAgICB9CiAgICAgICAgaWYgKEQyID4gRG1heCkgcmV0dXJuIGNvdXQgPDwgIkQgbm90IGZvdW5kLiIgPDwgZW5kbCwgLTE7CiAgICAgICAgaWYgKGsgPT0gMCkgRCA9IEQyKyssIGNvcHkocnRvaTIsIHJ0b2kyICsgRCwgcnRvaSk7CiAgICB9CiAgICBmb3IgKHIgPSAwOyByIDwgRDsgcisrKSBpdG9yW3J0b2lbcl1dID0gcjsKICAgIGZvciAociA9IDA7IHIgPCBEMjsgcisrKSBpdG9yMltydG9pMltyXV0gPSByOwoKICAgIHZlY3Rvcjx2ZWN0b3I8YXJyYXk8aW50LCAyPj4+IEFCKEQyKTsKICAgIHZlY3RvcjxpbnQ+IFIyKEQyKTsKCiAgICBmb3IgKHIgPSAxOyByIDwgRDsgcisrKSB7CiAgICAgICAgZm9yIChyMiA9IDA7IHIyIDwgRDI7IHIyKyspIEFCW3IyXS5jbGVhcigpOwogICAgICAgIFIyLmNsZWFyKCk7CiAgICAgICAgZm9yIChhID0gMjsgYSA8PSBuOyBhKyspIHsKICAgICAgICAgICAgcmEgPSBpdG9yW2FdOwogICAgICAgICAgICBpZiAoKHJiID0gcmEgLSByKSA8IDApIHJiICs9IEQ7CiAgICAgICAgICAgIGlmIChiID0gcnRvaVtyYl0sIGIgPT0gMCB8fCBiID49IGEpIGNvbnRpbnVlOwogICAgICAgICAgICBpZiAoKHIyID0gaXRvcjJbYV0gLSBpdG9yMltiXSkgPCAwKSByMiArPSBEMjsKICAgICAgICAgICAgQUJbcjJdLnB1c2hfYmFjayh7YSwgYn0pOwogICAgICAgICAgICBpZiAoQUJbcjJdLnNpemUoKSA9PSBtKSBSMi5wdXNoX2JhY2socjIpOwogICAgICAgIH0KCiAgICAgICAgZm9yIChnID0gMDsgZyA8IFIyLnNpemUoKTsgZysrKSB7CiAgICAgICAgICAgIGF1dG8gJmFiID0gQUJbUjJbZ11dOwogICAgICAgICAgICBmb3IgKGsgPSAwLCBpID0gMDsgaSA8IGFiLnNpemUoKTsgaSsrKSB7CiAgICAgICAgICAgICAgICBhID0gYWJbaV1bMF07CiAgICAgICAgICAgICAgICBiID0gYWJbaV1bMV07CiAgICAgICAgICAgICAgICBkW2tdID0gKGxvbmcgbG9uZylhICogYSAqIGEgLSAobG9uZyBsb25nKWIgKiBiICogYjsKICAgICAgICAgICAgICAgIHBba10gPSBrOwogICAgICAgICAgICAgICAgaysrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHNvcnQocCwgcCArIGssIFtdKGludCB4LCBpbnQgeSkge3JldHVybiBkW3hdIDwgZFt5XTt9KTsKCiAgICAgICAgICAgIGZvciAoaSA9IDA7IGkgPCBrIC0gbSArIDE7IGkrKykgewogICAgICAgICAgICAgICAgaWYgKGRbcFtpXV0gIT0gZFtwW2kgKyBtIC0gMV1dKSBjb250aW51ZTsKCiAgICAgICAgICAgICAgICBjb3V0IDw8IGRbcFtpXV0gPDwgIjogIjsKICAgICAgICAgICAgICAgIGZvciAoaiA9IGkgKyBtOyBqIDwgayAmJiBkW3Bbal1dID09IGRbcFtpXV07IGorKyk7CiAgICAgICAgICAgICAgICBzb3J0KHAgKyBpLCBwICsgaiwgWyZdKGludCB4LCBpbnQgeSkge3JldHVybiBhYlt4XVswXSA8IGFiW3ldWzBdO30pOwogICAgICAgICAgICAgICAgZm9yX2VhY2gocCArIGksIHAgKyBqLCBbJl0oaW50ICZ4KSB7CiAgICAgICAgICAgICAgICAgICAgYSA9IGFiW3hdWzBdOwogICAgICAgICAgICAgICAgICAgIGIgPSBhYlt4XVsxXTsKICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICgmeCA+IHAgKyBpID8gIiwgKCIgOiAiKCIpIDw8IGEgPDwgIiwgIiA8PCBiIDw8ICIpIjsKICAgICAgICAgICAgICAgIH0pOwogICAgICAgICAgICAgICAgY291dCA8PCBlbmRsOwogICAgICAgICAgICAgICAgaSA9IGogLSAxOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0=