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.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

13C. Parallel Chords

Constraints

Input

Output

Samples

13C. Parallel Chords

Constraints

Input

Output

Samples