Shortest Wiring - Repovive Standard Round 7 | Repovive

22F. Shortest Wiring

3000 pts2s256 MB

You are given $n$ vertices. Vertex $i$ is located at coordinate $x_i$ on a line and has a required degree $d_i$ .

Choose edges between these vertices so that they form a tree and the degree of every vertex $i$ is exactly $d_i$ .

The cost of an edge connecting vertices $u$ and $v$ is $|x_u-x_v|$ . The total cost of a tree is the sum of the costs of its edges.

Construct a tree with the minimum possible total cost. If there are multiple optimal trees, you may output any of them.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le x_1 < x_2 < \cdots < x_n \le 10^9$
$1 \le d_i \le n-1$
It is guaranteed that at least one tree with the required degrees exists.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
All input values are integers.

Input

t

\left. \begin{array}{l} n \\ x_1 \quad x_2 \quad \cdots \quad x_n \\ d_1 \quad d_2 \quad \cdots \quad d_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

For each test case, output exactly $n-1$ edges of a tree with the required degrees and minimum total cost. Each line contains the indices of the two endpoints of one edge.

You may print the edges in any order and the endpoints of each edge in either order. Do not print the total cost or the number of edges.

Samples

Input

Case 1

2
1 1000000000
1 1

Case 2

4
1 2 4 7
2 1 1 2

Explanation

Case 1

The only possible tree has the edge $(1,2)$ , whose cost is $999999999$ .

Case 2

The printed edges give degrees $(2,1,1,2)$ and total cost $6+1+3=10$ . Vertices $1$ and $4$ must be adjacent, and each must be connected to one of the two leaves. The other possible assignment of the leaves has cost $6+3+5=14$ , so the printed tree is optimal.

Output

Case 1

1 2

Case 2

1 4
2 1
3 4

Input

Case 1

5
1 2 5 9 12
1 1 4 1 1

Case 2

4
2 5 8 11
1 2 2 1

Case 3

6
1 3 4 8 9 12
2 2 1 1 2 2

Explanation

Case 1

Vertex $3$ must be connected to every other vertex. This is the only possible tree, and its cost is $4+3+4+7=18$ .

Case 2

The printed tree is the path $1,2,3,4$ , with total cost $3+3+3=9$ . Every tree must connect vertices $1$ and $4$ , which alone requires a path of cost at least $|11-2|=9$ .

Case 3

The printed tree is the path $3,1,2,5,6,4$ , with total cost $3+2+6+3+4=18$ . Every valid tree is a path from vertex $3$ to vertex $4$ and must visit vertices $1$ and $6$ . Visiting vertex $1$ before vertex $6$ costs at least $3+11+4=18$ ; visiting them in the opposite order costs at least $8+11+7=26$ .

Output

Case 1

Case 2

2 3
1 2
4 3

Case 3

You are given $n$ vertices. Vertex $i$ is located at coordinate $x_i$ on a line and has a required degree $d_i$ .

Choose edges between these vertices so that they form a tree and the degree of every vertex $i$ is exactly $d_i$ .

The cost of an edge connecting vertices $u$ and $v$ is $|x_u-x_v|$ . The total cost of a tree is the sum of the costs of its edges.

Construct a tree with the minimum possible total cost. If there are multiple optimal trees, you may output any of them.

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le x_1 < x_2 < \cdots < x_n \le 10^9$
$1 \le d_i \le n-1$
It is guaranteed that at least one tree with the required degrees exists.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
All input values are integers.

t

\left. \begin{array}{l} n \\ x_1 \quad x_2 \quad \cdots \quad x_n \\ d_1 \quad d_2 \quad \cdots \quad d_n \end{array} \right\} \times t

\left. \begin{array}{l} u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

For each test case, output exactly $n-1$ edges of a tree with the required degrees and minimum total cost. Each line contains the indices of the two endpoints of one edge.

You may print the edges in any order and the endpoints of each edge in either order. Do not print the total cost or the number of edges.

The only possible tree has the edge $(1,2)$ , whose cost is $999999999$ .

Vertex $3$ must be connected to every other vertex. This is the only possible tree, and its cost is $4+3+4+7=18$ .

The printed tree is the path $1,2,3,4$ , with total cost $3+3+3=9$ . Every tree must connect vertices $1$ and $4$ , which alone requires a path of cost at least $|11-2|=9$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

22F. Shortest Wiring

Constraints

Input

Output

Samples

22F. Shortest Wiring

Constraints

Input

Output

Samples