Solving multiple instances of 3SUM generated from the same set (this is a follow-up of my previous question, which uses the 3SUM' problem instead of 3SUM)

Suppose we have a list $S$ of $n$ integers.
Usually, for 3SUM, we only determine if there exist $a$,$b$,$c$ $\in S$ such that $a+b+c=0$. That's done in $O(n^2)$, and obviously the same thing can be done for $a+b+c=d$, with $d$ an integer.

Now, I use a somewhat modified version of this problem. Someone randomly picks $n$ triplets of elements of $S$, and for each of them, computes the sum of its elements. Let's call the list of these sums $Y$. That's $n$ instances of 3SUM built on the same set.

My goal is to invert one element of $Y$., i.e. is to find one element in $Y$, along with its corresponding elements in $S$. (To solve one of the possible instances of 3SUM, no matter which one)

I'm looking for a $O(n)$ solution. If we feed this solution some particular $S$ and $Y$ ,and we want to find a particular $d$ in $Y$, it would take the solution $O(n)$ attempts to find the $d$ we're looking for, thus running in $O(n^2)$, which is the 3SUM complexity.

I tried to use randomness in my solutions, without success. Someone also advised me to have a look at FFTs, but I can't see how I could use them in this case.

The best that I can do now, is to have $Y$ built with $n^{1.5}$ triplets instead of $n$, and then I can use the birthday paradox. If I pick $O(n^{1.5})$ triplets at random, I have a constant probability to find the same triplet twice. ($n^{1.5} = \sqrt{n^3}$)
It's not linear time, but here at least is an $O(n^{3/2})$ randomized solution to the problem in which you are given a set of $n$ elements together with the sums of $n$ randomly-generated triples of the elements, and you have to find a triple that matches one of the given sums.


Pick randomly two subsets $A$ of $n^{3/4}$ elements and $B$ of $n^{1/2}$ elements. With constant probability at least one of your 3SUMs is in $A+A+B$.
Compute the set $A+A$ and store it in a hash table for fast lookups.
For each pair of a value $x$ in $B$ and a target value $z$ of one of the input 3SUMs, test whether $z-x$ is one of the stored values of $A+A$, and if so whether the resulting triple(s) of numbers $A+A+B$ that sum to $z$ are distinct from each other.


I originally thought this would work equally well for an adversarially-selected set of 3SUMs (instead of the randomly-selected set in your question), but now I'm not sure sure about that part: the expected number of 3SUMs you hit with your choice of $A+A+B$ is always constant, but maybe the adversary could fix things so that you have a high probability of hitting none of them and a small probability of hitting many at once? I'm not sure this is possible but it would take more analysis than I've done so far to be certain.