Problem: For given a sequence $A = \\{a_0, a_1, ..., a_{n-1}\\}$, print the previous permutation and the next permutation in lexicographic order.

Constraints

* $1 \leq n \leq 9$
* $a_i$ consist of $1, 2, ..., n$

Input

A sequence is given in the following format.


$n$
$a_0 \; a_1 \; ... \; a_{n-1}$


Output

Print the previous permutation, the given sequence and the next permutation in the 1st, 2nd and 3rd lines respectively. Separate adjacency elements by a space character. Note that if there is no permutation, print nothing in the corresponding line.

Examples

Input

3
2 1 3


Output

1 3 2
2 1 3
2 3 1


Input

3
3 2 1


Output

3 1 2
3 2 1

Solution (in CPP):

Solution:
//https://cpprefjp.github.io/reference/algorithm/prev_permutation.html ->prev_permutation
//https://cpprefjp.github.io/reference/algorithm/next_permutation.html ->next_permutation


#include<iostream>
#include<vector>
#include<algorithm>

int main(){
    std::vector<int> num;
    
    int n;
    std::cin>>n;

    int num_buf;
    for(int i=0;i<n;i++){
        std::cin>>num_buf;
        num.push_back(num_buf);
    }

    bool op;

    op=std::prev_permutation(num.begin(),num.end());
    for(int i=0;i<n;i++){
        if(op==true){
            if(i!=n-1){
                std::cout<<num[i]<<" "<<std::flush;
            }else{
                std::cout<<num[i]<<std::endl;
            }
            
        }else if(op==false){
            break;
        } 
    }

    op=std::next_permutation(num.begin(),num.end());
    for(int i=0;i<n;i++){
        if(i!=n-1){
            std::cout<<num[i]<<" "<<std::flush;
        }else{
            std::cout<<num[i]<<std::endl;
        }
        
        
    }

    op=std::next_permutation(num.begin(),num.end());
    for(int i=0;i<n;i++){
        if(op==true){
            if(i!=n-1){
                std::cout<<num[i]<<" "<<std::flush;
            }else{
                std::cout<<num[i]<<std::endl;
            }
        }else if(op==false){
            break;
        }
    }

    return 0;

}