This is a problem of a past bioinformatic contest (requires an account). My solution works but is too slow for some test cases.

### Input format

The first line of the input contains one integer $T$, $(1 leq T leq 3)$ the number of test cases. Each test case is specified by four lines.

The first line of each test case contains three integer numbers $M$, $K$, $N$.

The second line contains $M$ numbers $m_i$ − masses of metabolites $(0 < m_ile 1000)$.

The third line contains $K$ numbers $a_i$ − masses of adducts $(-1000 le a_i le 1000)$.

The fourth line contains $N$ numbers $s_i$ − masses of signals $(0 < s_ile 1000)$.

All the masses are indicated with exactly six decimal places.

## Output format

For each signal $s_i$ of each test case, print numbers $j$ and $k$ such that $s_i = m_j+a_k+Delta$, $m_j+a_k > 0$ and the absolute value of $Delta$ is smallest possible. If there are multiple numbers $j$ and $k$ with same absolute value of $Delta$ for some signal, you can print any of them.

### Sample input

```
3
2 2 5
1.000002 0.000002
0.500000 -0.500000
0.500001 0.500002 0.500003 1.000000 0.000001
2 2 5
1.000002 0.000001
0.500000 -0.500000
0.500001 0.500002 0.500003 1.000000 0.000001
5 4 7
0.000001 0.000002 0.000003 0.000004 0.000005
0.000002 0.000010 0.000001 -0.000001
0.000001 0.000002 0.000100 0.000005 0.000020 0.000010 0.000003
```

### Sample output

```
1 2
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 4
1 3
5 2
3 1
5 2
1 2
1 1
```

### Test cases

1.txt: $M,K,N≤10$

3.zip: $M,K≤1000;N≤10^5$

4.zip: $M≤10^6;K,N≤1000$

5.zip: $M,K,N≤10^4$

answers.zip: to test the solution

### Code

```
from bisect import bisect_left
from time import perf_counter as pc
# Find in arr the closest number to n
def take_closest(arr, n):
pos = bisect_left(arr, n)
if pos == 0:
return arr(0)
if pos == len(arr):
return arr(-1)
before = arr(pos - 1)
after = arr(pos)
if after - n < n - before:
return after
else:
return before
def solve(masses, adducts, signals):
totals = {}
for i, m in enumerate(masses):
for j, a in enumerate(adducts):
ma = m + a
if ma > 0:
totals(ma) = (i + 1, j + 1)
skeys = sorted(totals.keys())
for s in signals:
closest = take_closest(skeys, s)
yield totals(closest)
if __name__ == "__main__":
test_num = 3
of = open(f"out{test_num}.txt", "w")
with open(f"{test_num}.txt", "r") as f:
t0 = pc()
t = int(f.readline())
for _ in range(t):
M, K, N = map(int, f.readline().strip().split())
masses = list(map(float, f.readline().strip().split()))
adducts = list(map(float, f.readline().strip().split()))
signals = list(map(float, f.readline().strip().split()))
for j, k in solve(masses, adducts, signals):
of.write(f'{j} {k}n')
t1 = pc()
print(f"Runtime: {round(t1-t0,3)} s")
of.close()
```

**Algorithm**:

- Store all sums $m_i + a_j$ in a dictionary with indices $i,j$ as values.
- Sort
`signals`

- For each signal, find the closest number among the sorted keys of the dictionary using binary search.

**Issues**:

The solution works but is too slow for test case 4, while test case 5 takes around 10 minutes on my machine.

Any feedback is appreciated.