Parallel Chords - Repovive Premier Round 5 | Repovive

13C. Parallel Chords

1500 pts2s256 MB

There are $n$ positions on a circle, numbered from $0$ to $n-1$ in clockwise order. The positions are equally spaced.

Exactly $d$ of these positions contain a point. You are given the sorted array $a_1, a_2, \ldots, a_d$ of these positions.

Find two line segments such that:

each endpoint of each segment is one of the given points;
the four endpoints are all distinct;
the two segments are parallel.

If there is no such pair of segments, report that it is impossible.

Constraints

$1 \le t \le 10^4$
$1 \le d \le n$
$1 \le n \le 5 \times 10^5$
The sum of $n$ over all test cases is at most $5 \times 10^5$
$0 \le a_1 < a_2 < \cdots < a_d < n$

Input

t

\left. \begin{array}{l} n \quad d \\ a_1 \quad a_2 \quad \cdots \quad a_d \end{array} \right\} \times t

Output

For each test case, output the answer in one line.

If there is no valid pair of segments, output $-1$ .

Otherwise, output four distinct integers $x_1, y_1, x_2, y_2$ , meaning that the segment with endpoints $x_1$ and $y_1$ is parallel to the segment with endpoints $x_2$ and $y_2$ .

Each of these four positions must be one of the given points.

If there are multiple valid answers, you may output any of them.

\left. \begin{array}{l} -1 \quad \text{or} \quad x_1 \quad y_1 \quad x_2 \quad y_2 \end{array} \right\} \times t

Samples

Input

Case 1

4 4
0 1 2 3

Case 2

5 3
0 1 3

Case 3

6 4
0 1 3 4

Case 4

8 5
0 1 2 4 6

Case 5

7 4
0 1 2 4

Explanation

Case 1

All four points are available. Pair $(0,1)$ gives sum $1$ , and $(2,3)$ also gives sum $1$ — the chords $(0,1)$ and $(2,3)$ are parallel.

Case 2

Only three points are available. The three pairwise sums are $1$ , $3$ , and $4$ — all distinct, so no two chords can be parallel.

Case 3

Points $\{0,1,3,4\}$ . Pair $(0,1)$ and $(3,4)$ both have sum $1$ — the chords $(0,1)$ and $(3,4)$ are parallel.

Case 4

Points $\{0,1,2,4,6\}$ . Pair $(0,6)$ has sum $6$ , and $(2,4)$ also has sum $6$ — those two chords are parallel.

Case 5

Points $\{0,1,2,4\}$ . The six pairwise sums are $1,2,4,3,5,6$ — all distinct modulo $7$ , so no parallel chords exist.

Output

Case 1

0 1 2 3

Case 2

-1

Case 3

0 1 3 4

Case 4

0 6 2 4

Case 5

-1

There are $n$ positions on a circle, numbered from $0$ to $n-1$ in clockwise order. The positions are equally spaced.

Exactly $d$ of these positions contain a point. You are given the sorted array $a_1, a_2, \ldots, a_d$ of these positions.

Find two line segments such that:

each endpoint of each segment is one of the given points;
the four endpoints are all distinct;
the two segments are parallel.

If there is no such pair of segments, report that it is impossible.

$1 \le t \le 10^4$
$1 \le d \le n$
$1 \le n \le 5 \times 10^5$
The sum of $n$ over all test cases is at most $5 \times 10^5$
$0 \le a_1 < a_2 < \cdots < a_d < n$

t

\left. \begin{array}{l} n \quad d \\ a_1 \quad a_2 \quad \cdots \quad a_d \end{array} \right\} \times t

For each test case, output the answer in one line.

If there is no valid pair of segments, output $-1$ .

Otherwise, output four distinct integers $x_1, y_1, x_2, y_2$ , meaning that the segment with endpoints $x_1$ and $y_1$ is parallel to the segment with endpoints $x_2$ and $y_2$ .

Each of these four positions must be one of the given points.

If there are multiple valid answers, you may output any of them.

\left. \begin{array}{l} -1 \quad \text{or} \quad x_1 \quad y_1 \quad x_2 \quad y_2 \end{array} \right\} \times t

All four points are available. Pair $(0,1)$ gives sum $1$ , and $(2,3)$ also gives sum $1$ — the chords $(0,1)$ and $(2,3)$ are parallel.

Only three points are available. The three pairwise sums are $1$ , $3$ , and $4$ — all distinct, so no two chords can be parallel.

Points $\{0,1,3,4\}$ . Pair $(0,1)$ and $(3,4)$ both have sum $1$ — the chords $(0,1)$ and $(3,4)$ are parallel.

Points $\{0,1,2,4,6\}$ . Pair $(0,6)$ has sum $6$ , and $(2,4)$ also has sum $6$ — those two chords are parallel.

Points $\{0,1,2,4\}$ . The six pairwise sums are $1,2,4,3,5,6$ — all distinct modulo $7$ , so no parallel chords exist.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

13C. Parallel Chords

Constraints

Input

Output

Samples

13C. Parallel Chords

Constraints

Input

Output

Samples