#include "diameter.h"
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;

pair<int, int> Special(int n) {
  if(n <= 2) return make_pair(1, n);
  if(n == 3) {
    if(in(1, 2, 3)) return make_pair(2, 3);
    if(in(2, 1, 3)) return make_pair(1, 3);
    return make_pair(1, 2);
  }
  int x, y, z, cnt = 0;
  for(int i = 1; i <= n; i++)
    for(int j = i + 1; j <= n; j++)
      for(int k = j + 1; k <= n; k++)
        if(query(i, j, k) == 6)
          cnt++, x = i, y = j, z = k;
  if(cnt == 1) return make_pair(x, y);
  if(in(x, y, z)) return make_pair(y, z);
  if(in(y, x, z)) return make_pair(x, z);
  return make_pair(x, y);
}

const int kMod = 998244353;
int Pow(int x, int y) {
  int b = x, r = 1;
  for(; y; b = (ll)b * b % kMod, y /= 2)
    if(y & 1) r = (ll)r * b % kMod;
  return r;
}

array<array<int, 11>, 10> A;

void Gauss() {
  int n = 10;
  for(int i = 0; i < n; i++) {
    for(int j = i + 1; j < n; j++)
      if(A[j][i]) { swap(A[i], A[j]); break; }
    int inv = Pow(A[i][i], kMod - 2);
    for(int j = 0; j < n; j++) {
      if((i == j) || !A[j][i]) continue;
      int coef = (ll)A[j][i] * inv % kMod;
      for(int k = 0; k <= n; k++)
        A[j][k] = (A[j][k] - (ll)coef * A[i][k] % kMod + kMod) % kMod;
    }
  }
  for(int i = 0; i < n; i++)
    A[i][n] = (ll)A[i][n] * Pow(A[i][i], kMod - 2) % kMod;
}

array<int, 3> id, dis;

int Id(int x, int y) {
  if(x > y) swap(x, y);
  int rk = y - x - 1;
  for(int i = 1; i < x; i++) rk += 5 - i;
  return rk;
}
void Init() {
  int tot = 0;
  for(int i = 1; i <= 5; i++)
    for(int j = i + 1; j <= 5; j++)
      for(int k = j + 1; k <= 5; k++) {
        A[tot].fill(0);
        A[tot][Id(i, j)] = A[tot][Id(i, k)] = A[tot][Id(j, k)] = 1;
        A[tot][10] = query(i, j, k), tot++;
      }
  Gauss();
  int x, y, z, d = -1;
  for(int i = 1; i <= 5; i++)
    for(int j = i + 1; j <= 5; j++) {
      int dist = A[Id(i, j)][10];
      if(dist > d) x = i, y = j, d = dist;
    }
  for(z = 1; (z == x) || (z == y); z++) ;
  id = array<int, 3> {x, y, z};
  dis[0] = A[Id(x, y)][10];
  dis[1] = A[Id(y, z)][10];
  dis[2] = A[Id(z, x)][10];
}

pair<int, int> find_diameter(int sub, int n) {
  if(n <= 4) return Special(n);
  Init();
  for(int i = 6; i <= n; i++) {
    array<int, 3> s;
    for(int j = 0; j < 3; j++) s[j] = query(i, id[j], id[(j + 1) % 3]) / 2;
    while(s[0] - dis[0] != s[2] - dis[2]) {
      rotate(begin(id), begin(id) + 1, end(id));
      rotate(begin(s), begin(s) + 1, end(s));
      rotate(begin(dis), begin(dis) + 1, end(dis));
    }
    int a, b, c, d, e;
    e = s[0] - dis[0], b = s[1] - dis[1] - e;
    int sum = (dis[0] + dis[1] + dis[2]) / 2 - b;
    a = sum - dis[1], c = sum - dis[2] + b, d = sum - dis[0] + b;
    int cur = max({dis[0], dis[1], dis[2]});
    int nwa = max({b + c + e, b + d + e, c + d});
    int nwb = max({a + b + d, b + d + e, a + e});
    int nwc = max({a + b + c, b + c + e, a + e});
    if(nwa >= cur) id[0] = i, dis[0] = b + c + e, dis[2] = b + d + e;
    else if(nwb >= cur) id[1] = i, dis[0] = a + e, dis[1] = b + d + e;
    else id[2] = i, dis[1] = b + c + e, dis[2] = a + e;
  }
  int mx = max({dis[0], dis[1], dis[2]});
  if(dis[0] == mx) return make_pair(id[0], id[1]);
  if(dis[1] == mx) return make_pair(id[1], id[2]);
  return make_pair(id[0], id[2]);
}