Permutation Shift Sequence

Given a permutation $p$ of length $n$, a single "shift" operation is defined as follows: every element in $p$ is moved one position to the right, and the last element is moved to the beginning. For example, if $p = [1, 4, 2, 3]$, after one shift the new permutation will be $[3, 1, 4, 2]$.

The program should repeatedly perform the following steps in order:

1. Perform one shift operation on the current permutation $p$.
   
2. Output the permutation after the shift operation (elements separated by spaces).
   
3. Check if the last element of the permutation equals $n$. If it does, the process terminates; otherwise, repeat from step 1.
   
   Note: Strictly follow the order of operations as given in the problem statement.

inputFormat

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$), the length of the permutation.

The second line contains $n$ space-separated integers representing the permutation $p$.

outputFormat

Output each permutation obtained after performing a shift operation on a separate line. The output for each operation should display the permutation elements separated by a single space.

sample

4
1 4 2 3

3 1 4 2
2 3 1 4