To solve this problem, we define and compute auxiliary arrays \(f(n)\) and \(g(n)\) as follows.

Define \(f(n)\) as the number of indices \(i\) such that \(A_i = n\) (i.e., \(f(n)\) is a frequency array). We can compute \(f(1), f(2), \dots, f(X)\) in \(\mathrm{O}(N + X)\) time.

Define \(g(n)\) as the number of integer pairs \((i, j)\) satisfying \(A_i + A_j = n\), where \(i \lt j\). There is a relationship between \(f(n)\) and \(g(n)\) given by:

\[g(n) = \frac{\left(\sum_{k=1}^{n-1} f(k) f(n - k)\right) - \left(f\left(\frac{n}{2}\right) \text{ if } n \bmod 2 = 0 \text{ else } 0\right)}{2}\]

Thus, we can compute \(g(1), g(2), \dots, g(X)\) via convolution in \(\mathrm{O}(X \log X)\) time.

• Note that the values of the elements after convolution can be up to \(10^{12}\), so the usual convolution modulo \(998244353\) is not enough. In C++, it is easy to use the convolution_ll function from ACL. In environments without convolution_ll, we can choose two moduli larger than \(10^8\) that allow long FFTs, perform convolutions under each modulus, and then reconstruct the desired values using Garner’s algorithm (CRT: Chinese Remainder Theorem). We have also verified that using complex FFT-based convolution yields accurate results for the given test cases, although without appropriate error estimation.

Now, consider the problem of finding an integer \(s\) \((1 \leq s \leq N)\) satisfying the following condition:

• There exists an integer pair \((t, u)\) \((1 \leq t \lt u \leq N)\) satisfying all of the following:
  • \(s \neq t\), \(s \neq u\)
  • \(A_s + A_t + A_u = X\)

If we can find such an \(s\), we can find the required \((i, j, k)\) in \(\mathrm{O}(N + X)\) time using \(f(n)\) (details omitted). If no such \(s\) exists, then there is no solution. Thus, solving the problem of finding such an \(s\) suffices.

We search all \(s\) in the range \(1 \leq s \leq N\). For a fixed \(s\), the number of integer pairs \((t, u)\) satisfying \(1 \leq t \lt u \leq N\), \(s \neq t\), \(s \neq u\), and \(A_s + A_t + A_u = X\) can be expressed using \(f(n)\) and \(g(n)\) as:

\[g(X - A_s) - \left( f(X - 2 A_s) - (1 \text{ if } X = 3 A_s \text{ else } 0 )\right).\]

(Details omitted. Also, we assume \(f(n) = 0\) for \(n \leq 0\).) Thus, by computing the above expression, we can determine in \(\mathrm{O}(1)\) time whether \(s\) satisfies the condition, so we can find such an \(s\) in \(\mathrm{O}(N)\) time.

Therefore, we can solve this problem in a total of \(\mathrm{O}(N + X \log X)\) time, which is sufficiently fast.