A. United We Stand
constructive algorithms; math; number theory
Given an array \(a\) of length \(n\), containing integers. And there are two initially empty arrays \(b\) and \(c\). You need to add each element of array \(a\) to exactly one of the arrays \(b\) or \(c\), in order to satisfy the following conditions: Both arrays \(b\) and \(c\) are non-empty. More formally, let \(l_b\) be the length of array \(b\), and \(l_c\) be the length of array \(c\). Then \(l_b, l_c \ge 1\). For any two indices \(i\) and \(j\) (\(1 \le i \le l_b, 1 \le j \le l_c\)), \(c_j\) is not a divisor of \(b_i\). Output the arrays \(b\) and \(c\) that can be obtained, or output \(-1\) if they do not exist.
Each test consists of multiple test cases. The first line contains a single integer \(t\) (\(1 \le t \le 500\)) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer \(n\) (\(2 \le n \le 100\)) — the length of array \(a\).The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — the elements of array \(a\).
For each test case, output a single integer \(-1\) if a solution does not exist.Otherwise, in the first line, output two integers \(l_b\) and \(l_c\) — the lengths of arrays \(b\) and \(c\) respectively.In the second line, output \(l_b\) integers \(b_1, b_2, \ldots, b_{l_b}\) — the elements of array \(b\).In the third line, output \(l_c\) integers \(c_1, c_2, \ldots, c_{l_c}\) — the elements of array \(c\).If there are multiple solutions, output any of them. You can output the elements of the arrays in any order.
In the first test case, a solution does not exist.In the second test case, we can obtain \(b = [1, 3, 5]\) and \(c = [2, 4]\). Then elements \(2\) and \(4\) do not divide elements \(1, 3\) and \(5\).In the fifth test case, we can obtain \(b = [4, 8, 4]\) and \(c = [12, 12]\).