Perfect Trio

Perfect Trio

Time limit: 1 s.
Memory limit: 256 MB

Three friends are playing a coordination game called “Perfect Trio”.

They are given a list of celebrities, where the \(i\)-th celebrity has exactly \(A_i\) followers. To win the game, they must choose exactly three distinct celebrities such that the sum of their follower counts is exactly \(S\).

Determine whether such a trio exists. If it does, output any valid three follower counts. Otherwise, output \(-1\).

Input

The first line contains two integers \(N\) and \(S\) — the number of celebrities and the target total number of followers.

The second line contains \(N\) integers \(A_1, A_2, \ldots, A_N\), where \(A_i\) is the follower count of the \(i\)-th celebrity.

It is guaranteed that \(3 \le N \le 10000\) and \(0 \le A_i, S \le 7 \cdot 10^8\).

Output

If there exist three distinct celebrities whose follower counts sum to \(S\), print any three such values.

Otherwise, print \(-1\).

Scoring

Subtask Additional constraints Points
\(1\) \(N = 3\) \(7\)
\(2\) \(N = 4\) \(8\)
\(3\) \(N = 5\) \(9\)
\(4\) \(N \le 100\) \(26\)
\(5\) \(N \le 10000\), \(S \le 100000\) \(31\)
\(6\) \(N \le 10000\), \(S \le 7 \cdot 10^8\) \(19\)

Examples

Input

3 6
1 2 3

Output

1 2 3

Input

6 1000
182 587 952 374 39 741

Output

39 374 587

Note

In the sample, the three chosen follower counts are \(374\), \(39\), and \(587\). Their sum is \[374 + 39 + 587 = 1000.\]

Note that:

  • the three chosen celebrities must be distinct;
  • if there are multiple valid answers, you may print any of them;
  • the values may be printed in any order.
Solution

Sort the follower counts. Fix the first celebrity at position \(i\), then use two pointers to find two later values whose sum is \(S-A_i\).

If the current sum is too small, move the left pointer right. If it is too large, move the right pointer left. The three array positions are always distinct, even when some follower counts are equal.

The complexity is \(O(N^2)\) time and \(O(1)\) extra memory apart from the sorted array.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long target;
    cin >> n >> target;

    vector<long long> a(n);
    for (long long& value : a) {
        cin >> value;
    }
    sort(a.begin(), a.end());

    for (int i = 0; i < n - 2; i++) {
        int left = i + 1;
        int right = n - 1;

        while (left < right) {
            long long sum = a[i] + a[left] + a[right];
            if (sum == target) {
                cout << a[i] << ' ' << a[left] << ' ' << a[right] << '\n';
                return 0;
            }
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

    cout << -1 << '\n';
}