#include "diameter.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
constexpr int inf = 1e9, mod = 998244353;
int id[20][20], a[20][20];
int qpow(int b, int k)
{
	int res = 1;
	while (k) {
		if (k & 1) res = (ll) res * b % mod;
		b = (ll) b * b % mod;
		k >>= 1;
	}
	return res;
}
pii find(vector<int>v)
{
	if (v.size() == 1) return pii(v[0], v[0]);
	if (v.size() == 2) return pii(v[0], v[1]);
	if (v.size() == 3) {
		if (in(v[0], v[1], v[2])) return pii(v[1], v[2]);
		if (in(v[1], v[0], v[2])) return pii(v[0], v[2]);
		return pii(v[0], v[1]);
	}
	assert(v.size() == 5);
	// for (int x : v) cerr << x << ' '; cerr << '\n';
	int n = 0, cnt = 0;
	for (int i = 0; i < 5; ++i) {
		for (int j = i + 1; j < 5; ++j) {
			id[i][j] = ++cnt;
		}
	}
	for (int i = 0; i < 5; ++i) {
		for (int j = i + 1; j < 5; ++j) {
			for (int k = j + 1; k < 5; ++k) {
				++n;
				a[n][id[i][j]] = a[n][id[i][k]] = a[n][id[j][k]] = 1;
				a[n][cnt + 1] = query(v[i], v[j], v[k]);
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			if (a[j][i]) {
				swap(a[i], a[j]);
				break;
			}
		}
		for (int j = 1; j <= n; ++j) {
			if (j == i) continue;
			int c = (ll) a[j][i] * qpow(a[i][i], mod - 2) % mod;
			for (int k = i; k <= n + 1; ++k) {
				a[j][k] = (a[j][k] - (ll) c * a[i][k]) % mod;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		a[i][n + 1] = ((ll) a[i][n + 1] * qpow(a[i][i], mod - 2) % mod + mod) % mod;
		a[i][i] = 0;
	}
	cnt = 0;
	pair<int, pii>mx;
	for (int i = 0; i < 5; ++i) {
		for (int j = i + 1; j < 5; ++j) {
			++cnt;
			mx = max(mx, make_pair(a[cnt][n + 1], pii(v[i], v[j])));
		}
	}
	return mx.second;
}
pii find_diameter(int subid, int n) {
	if (n <= 3) {
		vector<int>v;
		for (int i = 1; i <= n; ++i) v.emplace_back(i);
		return find(v);
	}
	if (n == 4) {
		pair<int, tuple<int, int, int>>t[4];
		t[0] = {query(1, 2, 3), {1, 2, 3}};
		t[1] = {query(1, 2, 4), {1, 2, 4}};
		t[2] = {query(1, 3, 4), {1, 3, 4}};
		t[3] = {query(2, 3, 4), {2, 3, 4}};
		pair<int, tuple<int, int, int>>mx = *max_element(t, t + 4);
		int x = get<0>(mx.second), y = get<1>(mx.second), z = get<2>(mx.second);
		int k = 10 - x - y - z;
		int d1 = query(x, y, k), d2 = query(x, z, k), d3 = query(y, z, k);
		if (max({d1, d2, d3}) == d1) return pii(x, y);
		if (max({d1, d2, d3}) == d2) return pii(x, z);
		return pii(y, z);
	}
	vector<int>v(2);
	v[0] = 1, v[1] = 2;
	int id = 2;
	n -= 2;
	for (int i = 1; i <= n / 3; ++i) {
		v.resize(5);
		v[2] = ++id, v[3] = ++id, v[4] = ++id;
		auto [x, y] = find(v);
		v[0] = x, v[1] = y;
	}
	v.resize(2);
	for (int i = n / 3 * 3 + 1; i <= n; ++i) {
		v.emplace_back(++id);
	} 
	id = 0;
	while (v.size() < 5) {
		++id;
		if (id != v[0] && id != v[1]) {
			v.emplace_back(id);
		}
	}
	return find(v);
}