#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
#define cerr if(0) cerr
#define cout if(0) cout
ll count_triangles(v<v<int>> &edges, v<v<int>> &adj) {
ll cnt = 0;
for (auto x : edges) {
int u = x[0];
int v = x[1];
if (adj[u].size() > adj[v].size()) {
swap(u, v);
}
int i, j;
i=j=0;
while (i < (int)adj[u].size() && j<(int)adj[v].size()) {
if (adj[u][i] == adj[v][j]) {
cnt++;
i++; j++;
}
else if (adj[u][i] > adj[v][j]) j++;
else i++;
}
}
return cnt/3;
}
long long count_triples(std::vector<int> H) {
ll ans=0;
int N = H.size();
rep(i, 0, N) {
if (H[i]+i < N) {
int k = H[i]+i;
if (k-H[k] >= 0) {
int j = k-H[k];
if (H[i] == k-i && H[k] == k-j && H[j] == j-i && (i != j && j != k && k != i) && !(H[i] == k-i && H[k] == j-i && H[j] == k-j) && (i < j && j < k)) {
ans++;
cout << "1" << endl;
cout << i << " " << j << " " << k << endl;
}
}
if (H[k]+i < N) {
int j = H[k]+i;
if (H[i] == k-i && H[k] == j-i && H[j] == k-j && (i != j && j != k && k != i) && (i < j && j < k)) {
ans++;
cout << "2" << endl;
cout << i << " " << j << " " << k << endl;
}
}
}
}
rep(k, 0, N) {
if (k-H[k] >= 0) {
int i = k-H[k];
if (H[i]+i < N) {
int j = H[i]+i;
if (H[k] == k-i && H[i] == j-i && H[j] == k-j && (i != j && j != k && k != i) && !(H[k] == k-i && H[i] == k-j && H[j] == j-i) && (i < j && j < k)) {
ans++;
cout << i << " " << j << " " << k << endl;
}
}
if (k-H[i] >= 0) {
int j = k-H[i];
if (H[k] == k-i && H[i] == k-j && H[j] == j-i && (i != j && j != k && k != i) && (i < j && j < k)) {
ans++;
cout << i << " " << j << " " << k << endl;
}
}
}
}
rep(i, 0, N) {
if (H[i]+i < N) {
int j = H[i]+i;
if (H[j]+i < N) {
int k = H[j]+i;
if (H[i] == j-i && H[k] == k-j && H[j] == k-i && (i != j && j != k && k != i) && !(H[i] == k-j && H[k] == j-i && H[j] == k-i) && (i < j && j < k)) {
ans++;
cout << i << " " << j << " " << k << endl;
}
}
}
}
unordered_map<int, int> mp;
int id = 0;
rep(i, 0, N) {
if (!mp.count(i-H[i])) {
mp[i-H[i]] = id++;
}
if (!mp.count(i+H[i])) {
mp[i+H[i]] = id++;
}
}
v<v<int>> edges;
v<v<int>> adj(id);
rep(i, 0, N) {
edges.push_back({mp[i-H[i]], mp[i+H[i]]});
}
for (auto x : edges) {
int u = x[0];
int v = x[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
for (auto &x : adj) {
sort(x.begin(), x.end());
}
ans += count_triangles(edges, adj);
return ans;
}
std::vector<int> construct_range(int M, int K) {
int N = M;
v<int> X = {-1}, Y = {1};
v<int> used(2*N, 0), C = {0};
v<int> H(N), V(2*N, -1e9);
for (int i = 2; i < 2*N; i+=2) V[i] = 1;
while (1) {
auto it = max_element(V.begin(), V.end());
int mx = *it, optimal = it-V.begin();
cerr << optimal << " " << mx << endl;
if (mx == 0) break;
for (auto &x : C) {
if (x+optimal < 2*N && !used[x+optimal]) {
used[x+optimal] = 1;
X.push_back(min(x, optimal));
Y.push_back(max(x, optimal));
for (auto &y : C) {
int aux = x+optimal-y;
if (0 <= aux && aux < 2*N) V[aux]--;
}
}
}
for (int i=0; optimal+i < 2*N; i += 2) if (!used[optimal+i]) V[i]++;
C.push_back(optimal);
V[optimal] = -1e9;
}
rep(i, 0, N) {
H[(X[i]+Y[i])/2] = (Y[i]-X[i])/2;
}
ll cnt = count_triples(H);
while (cnt < K) {
rep(i, 0, N) {
rep(j, 1, N) {
int aux = H[i];
H[i] = j;
ll cntt = count_triples(H);
if (cntt > cnt) cnt = cntt;
else H[i] = aux;
}
}
}
return H;
}
