# 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}+\cdots +{�}_{{�}_{�}}$), 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\le �\le 10000$
• $1\le �\le 200000$
• $1\le �\le 200000$
• $1\le {�}_{�}\le 100000$
• $1\le {�}_{�}\le {�}_{�}\le �$
• 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 :

## Problem

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

Is it possible to do so?

Note 1: Partitioning the set $�=\left\{1,2,\dots ,�\right\}$ 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\le �\le �$.

Note 2: $\mathrm{\mid }�\mathrm{\mid }$ 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 $�$.