Optimal Swap Game

You are given two integers \(t\) and \(n\), and a permutation \(a_1, a_2, \dots, a_n\) of length \(n\). Two players take turns to perform the following operation exactly \(t\) times in total (each operation counts as one move):

• Select two indices \(1 \le i, j \le n\) (they may be equal) and swap \(a_i\) with \(a_j\).

The first player (moving first) wants the final permutation to be lexicographically as small as possible, while the second player wants it to be as large as possible. Assuming both players play optimally, determine the final permutation.

Note: When comparing two permutations \(x\) and \(y\), the lexicographical order is defined in the usual way: the first index at which they differ determines the order.

Game insight: Because a swap can exchange any two elements and both players are fully rational, the key observation is that only one move effectively matters – the move which sets the element at index 1, the most significant position in lex order. More specifically:

• If \(t = 0\), no move is made and the final permutation is the initial permutation.
• If \(t \ge 1\):
• If \(t\) is odd, the first player (minimizer) has the final move. In that move, the minimizer can swap the element at index 1 with the minimum element in the permutation. (If index 1 already holds the minimum element, no effective change occurs.)
• If \(t\) is even, the second player (maximizer) has the final move. In that move, the maximizer can swap the element at index 1 with the maximum element in the permutation. (If index 1 already holds the maximum element, no effective change occurs.)

Thus, under optimal play, the final permutation is obtained by performing exactly one effective swap on index 1:

• If \(t = 0\): output the permutation as is.
• If \(t > 0\) and odd: swap \(a_1\) with \(a_k\), where \(a_k\) is the minimum element in the permutation.
• If \(t > 0\) and even: swap \(a_1\) with \(a_k\), where \(a_k\) is the maximum element in the permutation.

Print the resulting permutation.

inputFormat

The first line contains two integers \(t\) and \(n\) (\(0 \le t \le 10^9\), \(1 \le n \le 10^5\)).

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), representing a permutation of \(\{1, 2, \dots, n\}\).

outputFormat

Output the final permutation in a single line with \(n\) space-separated integers.

sample

1 3
3 1 2

1 3 2