Two-sum problem with $n$ iterations

Question

Preamble:

The famous two-sum problem asks for an algorithm to determine if a given integer $s$ is the sum of two integers in a given ordered list $L$. If $n$ is the size of $L$, this can be solved in $O(n)$ with a clever use of pointers as follows:

i = 0
j = n-1
found = false

while (!found and i<=n-1 and j >= 0):
   S = L[i] + L[j]
   if s > S:
      i += 1
   elif s < S:
      j -= 1
   else
      found = true

if found:
   print(L[i],L[j])

A trivial variation of this problem asks to find if a given integer $s$ is the sum of two integers, one from an ordered list $L$ and another from an ordered list $M$. If both lists have the same size, $n$, it is also solved in $O(n)$ by changing all instances of L[j] by M[j] in the code.

Note that since the size of the input is $n+1$ in the first case, and $2n+1$ in the variation, no algorithm can do any better than $O(n)$.

New variation:

Assume now that three ordered lists of size $n$ are given, $L, M, N$ and we are told that every element in $N$ is the sum of an element in $L$ and an element in $M$ in a one-to-one way. That is, if $n_1 = l_1 + m_1$ and $n_2 = l_2 + m_2$ then $l_1 \neq l_2$ and $m_1 \neq m_2$. Since the size of all lists is $n$, that means that each element in $L$ and in $M$ participates exactly once in a sum to produce an element in $N$. We are asked to find all $n$ triplets $(l_i,m_j,n_k)\in L\times M\times N$ such that $l_i + m_j = n_k$.

We could, of course, use the variation problem in the preamble to treat each element of $N$, and thus, solve this new variation in $O(n^2)$. We could delete each $l_i$ and $m_j$ from $L$ and $M$ as we find them to improve marginally our run time (though still in $O(n)$, of course).

Question:

Could we do any better than $O(n^2)$? Does the extra one-to-one property allows for some clever way to discard possibilities and thus achieve something like $O(n\log n)$?