C. 3SUM Closuretime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a of length n. The array is called 3SUM-closed if for all distinct indices i, j, k, the sum a_i + a_j + a_k is an element of the array. More formally, a is 3SUM-closed if for all integers 1 \leq i < j < k \leq n, there exists some integer 1 \leq l \leq n such that a_i + a_j + a_k = a_l.Determine if a is 3SUM-closed.InputThe first line contains an integer t (1 \leq t \leq 1000) — the number of test cases.The first line of each test case contains an integer n (3 \leq n \leq 2 \cdot 10^5) — the length of the array.The second line of each test case contains n integers a_1, a_2, \dots, a_n (-10^9 \leq a_i \leq 10^9) — the elements of the array.It is guaranteed that the sum of n across all test cases does not exceed 2 \cdot 10^5.OutputFor each test case, output "YES" (without quotes) if a is 3SUM-closed and "NO" (without quotes) otherwise.You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).ExampleInput
43-1 0 151 -2 -2 1 -360 0 0 0 0 04-1 2 -3 4Output
YES
NO
YES
NO
NoteIn the first test case, there is only one triple where i=1, j=2, k=3. In this case, a_1 + a_2 + a_3 = 0, which is an element of the array (a_2 = 0), so the array is 3SUM-closed.In the second test case, a_1 + a_4 + a_5 = -1, which is not an element of the array. Therefore, the array is not 3SUM-closed.In the third test case, a_i + a_j + a_k = 0 for all distinct i, j, k, and 0 is an element of the array, so the array is 3SUM-closed.
43-1 0 151 -2 -2 1 -360 0 0 0 0 04-1 2 -3 4
YES NO YES NO 
['brute force', 'data structures', '*1300']