Maximum Permutation Sum

Problem

You are given an array $�$ of size $�$ . The array will be used to perform $�$ queries, where each query is comprised of a pair of integers, denoted by $�_{�}$ and $�_{�}$ .

Before the queries are executed, you are allowed to rearrange the elements in array $�$ as desired.

Next, an integer variable $�$ is initialized to 0. For each of the $�$ -th queries, calculate the sum of elements from $�_{�_{�}}$ through $�_{�_{�}}$ inclusive (i.e. $�_{�_{�}} + �_{�_{�} + 1} + \dots + �_{�_{�}}$ ), and add this sum to $�$ .

The objective of this problem is to find an arrangement of array $�$ that maximizes the final value of $�$ after all $�$ queries have been processed.

If there are multiple possible arrangements of $�$ which achieve this maximum value, you can output any.

Input Format

The first line of input will contain a single integer $�$ , denoting the number of test cases.
Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers $�$ and $�$ — the length of array and number of queries, respectively.
- The next line contains $�$ space-separated integers denoting the elements of the array.
- The next $�$ lines describe the queries. The $�$ -th of these $�$ lines contains two space-separated integers $�_{�}$ and $�_{�}$ , describing the range for the $�$ -th query.

Output Format

For each test case, output on a new line the maximum possible value of $�$ . And in the next line, output the rearranged array $�$ , which achieves that maximum possible value.

Constraints

$1 \leq � \leq 10000$
$1 \leq � \leq 200000$
$1 \leq � \leq 200000$
$1 \leq �_{�} \leq 100000$
$1 \leq �_{�} \leq �_{�} \leq �$
The sum of $�$ over all test cases won't exceed $2 \cdot 1 0^{5}$
The sum of $�$ over all test cases won't exceed $2 \cdot 1 0^{5}$

The solution will be updated Soon :

Chef ODD

Problem

You want to partition the set $� = {1, 2, \dots, �}$ into $�$ sets $�_{1}, �_{2}, \dots, �_{�}$ , such that $∣ �_{�} ∣ \geq 2$ , and the sum of elements in each $�_{�}$ is odd.

Is it possible to do so?

Note 1: Partitioning the set $� = {1, 2, \dots, �}$ into $�$ sets $�_{1}, �_{2}, \dots, �_{�}$ means that every element of $�$ should be in exactly one of the sets $�_{1}, �_{2}, \dots, �_{�}$ , and $�_{�} \subseteq �$ , for all $1 \leq � \leq �$ .

Note 2: $∣ � ∣$ denotes the number of elements in the set $�$ .

Input Format

The first line of input will contain a single integer $�$ , denoting the number of test cases.
The first line and only line of each test case contains two space-separated integers, $�$ and $�$ .