<p>Alice and Bob have a different total number of candies. You are given two integer arrays <code>aliceSizes</code> and <code>bobSizes</code> where <code>aliceSizes[i]</code> is the number of candies of the <code>i<sup>th</sup></code> box of candy that Alice has and <code>bobSizes[j]</code> is the number of candies of the <code>j<sup>th</sup></code> box of candy that Bob has.</p>

<p>Since they are friends, they would like to exchange one candy box each so that after the exchange, they both have the same total amount of candy. The total amount of candy a person has is the sum of the number of candies in each box they have.</p>

<p>Return a<em>n integer array </em><code>answer</code><em> where </em><code>answer[0]</code><em> is the number of candies in the box that Alice must exchange, and </em><code>answer[1]</code><em> is the number of candies in the box that Bob must exchange</em>. If there are multiple answers, you may <strong>return any</strong> one of them. It is guaranteed that at least one answer exists.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> aliceSizes = [1,1], bobSizes = [2,2]
<strong>Output:</strong> [1,2]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> aliceSizes = [1,2], bobSizes = [2,3]
<strong>Output:</strong> [1,2]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> aliceSizes = [2], bobSizes = [1,3]
<strong>Output:</strong> [2,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= aliceSizes.length, bobSizes.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= aliceSizes[i], bobSizes[j] &lt;= 10<sup>5</sup></code></li>
	<li>Alice and Bob have a different total number of candies.</li>
	<li>There will be at least one valid answer for the given input.</li>
</ul>

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;

inline namespace skyly {
    /* default c++ template for problem solving */
#ifdef LOCAL_DEBUG
    #include <dbg.h>
#else
    #define dbg(...) 77
#endif

    #define rep(i, n_rep) for (decay_t<decltype(n_rep)> i = 0; i < (n_rep); ++i)
    #define ffor(i, begin_i, end_i) for (decay_t<decltype(end_i)> i = (begin_i); i < (end_i); ++i)
    #define rfor(i, begin_i, end_i) for (decay_t<decltype(end_i)> i = (end_i) - 1; i >= (begin_i); --i)
    #define sz(x) int((x).size())
    #define all(x) begin(x), end(x)
    #define rall(x) rbegin(x), rend(x)
    #define each(x, lst) for (auto& x : lst)
    #define eachp(x, y, lst) for (auto& [x, y] : lst)

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

    using I = int64_t;
    using U = uint64_t;
    using F = long double;
    using S = string;
    template <class T1, class T2> using P = pair<T1, T2>;
    template <class T> using V = vector<T>;
    template <class T, class Cmp = less<T>> using Set = tree<T, null_type, Cmp, rb_tree_tag, tree_order_statistics_node_update>;
    template <class T1, class T2, class Cmp = less<T1>> using Map = tree<T1, T2, Cmp, rb_tree_tag, tree_order_statistics_node_update>;
    template<class T, class Cmp = less<T>> using pqueue = std::priority_queue<T, vector<T>, Cmp>;
    template<class T, class Cmp = less<T>> using Heap = __gnu_pbds::priority_queue<T, Cmp>;

    struct CustomHash {
        static U splitmix64(U x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }
        size_t operator()(U x) const noexcept {
            static const U FIXED_RANDOM = rng();
            return splitmix64(x + FIXED_RANDOM);
        }
        template<typename T> size_t operator()(const P<T, T>& x) const {
            return (*this)(U(x.first)) ^ ((*this)(U(x.second)) >> 1);
        }
    };
    template <class T> using HashSet = gp_hash_table<T, null_type, CustomHash>;
    template <class T1, class T2> using HashMap = gp_hash_table<T1, T2, CustomHash>;

    template <typename T, T val = T(), typename... Args>
    auto make_vector(size_t x, Args... arr) {
        if constexpr (sizeof...(arr) == 0) return V<T>(x, val);
        else return vector(x, make_vector<T, val>(arr...));
    }

    inline namespace misc_defines {
        constexpr auto ssort = ranges::sort;
        template <typename T> using nlim = numeric_limits<T>;
        template <typename T, typename F = less<T>> void sort_unique(V<T>& v, F f = F()) { sort(all(v), f); v.resize(unique(all(v)) - begin(v)); }
        template <typename T> constexpr T sum(const V<T>& v) { return v.empty() ? T(0) : accumulate(v.cbegin(), v.cend(), T(0)); }
        template <typename T> constexpr bool chmax(T& a, const T& b) noexcept { return b > a ? a = b, true : false; }
        template <typename T> constexpr bool chmin(T& a, const T& b) noexcept { return b < a ? a = b, true : false; }
        template <typename T> constexpr T has_bit(T x, int i) noexcept { return x & (T(1) << i); }
        template <typename T> constexpr int log2_floor(T x) noexcept { static_assert(is_integral_v<T>);
            if (x <= T(0)) return -1;
            if constexpr (nlim<T>::digits <= nlim<unsigned int>::digits) return nlim<unsigned int>::digits - __builtin_clz(x) - 1;
            else return nlim<U>::digits - __builtin_clzll(x) - 1;
        }
        template <typename T> constexpr int log2_ceil(T x) noexcept { return log2_floor(x - 1) + 1; }
        constexpr F PI = numbers::pi_v<F>;
        constexpr int F_OUTPUT_PRECISION = 20;
    }
}
/* main part of the solution starts from here */

inline namespace solution_space {
/* begin */
bool to_init = true;

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& va, vector<int>& vb) {
        set<int> bset(all(vb));
        int dif = (sum(vb) - sum(va)) / 2;
        each (x, va) {
            if (int y = x + dif; bset.contains(y)) return {x, y};
        }
        return {};
    }
};
/*  end  */
}

#ifdef LOCAL_DEBUG
int main() {
    dbg("Ready to go...");
    Solution s;
    dbg("Program finished normally.");
    return 0;
}
#endif
53200