Extremely Good Permutations

We are given several definitions in this problem.

Definition 1. A permutation \(p_1, p_2, \ldots, p_n\) of \(\{1,2,\ldots,n\}\) is said to be good if and only if there exists an index \(k \in [1, n-1]\) such that \[ \max_{1 \le i \le k} p_i = k. \]

Definition 2. A sequence \(x_1, x_2, \ldots, x_k\) is called a swap sequence for a permutation \(p_1, p_2, \ldots, p_n\) if and only if:

• For every \(1 \le i \le k\), \(x_i\) is an integer satisfying \(1 \le x_i \le n-1\);
• If we perform, in order, the swaps exchanging the elements at positions \(x_i\) and \(x_i+1\) in \(p\) for \(i=1,2,\ldots,k\), then the resulting permutation is good.

(In particular, an empty sequence (i.e. performing no swaps) is allowed.)

Definition 3. A swap sequence \(x_1, x_2, \ldots, x_k\) is a critical swap sequence for \(p\) if and only if:

• It is a swap sequence for \(p\);
• Its length is minimum among all swap sequences for \(p\).

Define \(f(p)\) to be the number of different critical swap sequences of \(p\>.

Definition 4. A permutation \(q\) is called a terminal state for another permutation \(p\) if and only if:

• The lengths of \(p\) and \(q\) are equal;
• \(q\) is good;
• There exists a critical swap sequence \(x_1, x_2, \ldots, x_k\) for \(p\) such that, after performing the swaps (in order) on \(p\), the resulting permutation equals \(q\) (i.e. \(p_i=q_i\) for all \(1 \le i \le n\)).

Definition 5. A permutation \(p\) is called extremely good if and only if there exists exactly one permutation \(q\) which is the terminal state of \(p\>.

---

You are given a prime number \(P\) and \(q\) queries. Each query provides two integers \(n\) and \(m\). Your task is to construct any permutation \(p_1, p_2, \ldots, p_n\> of \(\{1, 2, \ldots, n\}\) that is extremely good and satisfies \[ f(p) \equiv m \pmod{P}, \] or report that no solution exists.

This problem uses a custom validator; any correct permutation that satisfies the requirements will be accepted.

inputFormat

The first line contains two integers: a prime number \(P\) and the number of queries \(q\) (i.e. the number of test cases).

Each of the next \(q\) lines contains two integers \(n\) and \(m\), representing the length of the permutation and the required residue modulo \(P\) of \(f(p)\), respectively.

It is guaranteed that \(n \ge 2\) in all queries.

outputFormat

For each query, output a single line. If a valid permutation exists, print \(n\) space-separated integers (the permutation \(p_1, p_2, \ldots, p_n\)). Otherwise, print -1 to indicate that no solution exists.

sample

7 2
5 1
5 2

1 2 3 4 5
-1

</p>