int st[N];
// 这里使用 st[0] (即 *st) 代表栈中元素数量，同时也是栈顶下标
// 压栈 ：
st[++*st] = var1;
// 取栈顶 ：
int u = st[*st];
// 弹栈 ：注意越界问题, *st == 0 时不能继续弹出
if (*st) --*st;
// 清空栈
*st = 0;

/**
	该函数实现的功能为：给定一个字符串，判断括号是否匹配
**/
bool isValid(string s) {
	stack<char> st;
    for(char c : s) {
        if(c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if(st.empty()) return false;
            char x = st.top();
            if(x == '[' && c != ']') return false;
            if(x == '(' && c != ')') return false;
            if(x == '{' && c != '}') return false;
            st.pop();
        }
    }
    return (st.empty() ? true : false);
}

stack<int> s;
// 新建两个栈 st1 和 st2
std::stack<int> st1, st2;
// 为 st1 装入 1
st1.push(1);
// 将 st1 赋值给 st2
st2 = st1;
// 输出 st2 的栈顶元素
cout << st2.top() << endl;
// 输出: 1

queue<int> q;    // 普通队列
deque<int> q;    // 双端队列(存在前后双指针)
priority_queue<int,vector<int>,greater> q;      // 优先队列

// 头文件
#include <list>  // 双向链表
#include <forward_list>   // 单向链表
//单向链表
#include <forward_list>  
std::forward_list<int> fl = {1,2,3};
fl.push_front(0);      // O(1)
fl.insert_after(fl.begin(), 42);
fl.remove(2);          // O(n)

//双向链表
#include <list>
std::list<int> lst = {1,2,3};
lst.push_back(4);
lst.insert(std::next(lst.begin()), 42);
lst.erase(lst.begin());

// 数据结构定义 ( 非嵌入式 )
struct node {
    Type data;
    struct node* next;
};
// 嵌入式
struct node {
	Type data;
	struct link_node;  // 链表管理器
}
struct link_node {
    struct link_node* pre;
    struct link_node* next;
};

// 操作定义(侵入式为例)
// 尾插
#define Add_tail(head,node) 	\
	(node)->next = (head);		\
	(node)->pre = (head)->pre;	\
	(head)->pre->next = head;	\
	(head)->pre = node;
// 头插
#define Add_head(head,node)		\
	

ListNode reverseList(ListNode head){
    ListNode pre = null;
    ListNode next = null;
    while(head != null){
        //next指针往前走
        next = head.next;
        //head下一个指针域指空
        head.next = pre;
        //pre指向head
        pre = head;
        //head指向下一个
    	head = next;
    }
}

string s,t;
for(int i = 0, j = 0; i < s.size() && j < t.size();){
	if(s[i] == t[j]) {
        ++i,++j;
    } else {
        i = i - j + 2;
        j = 0;
    }
    if(i == s.size() - 1 && j == t.size() - 1){
		// 匹配开始位置
        i - t.size();
    }
}

void dfs(int x)
{
    if (a[x] == -1) {
        return;
    }
    cout << a[x] << " ";
    dfs(2 * x + 1);
    dfs(2 * x + 2);
}

void dfs(int x)
{
    if (a[x] == -1) {
        return;
    }
    dfs(2 * x + 1);
    printf("%d ", a[x]);
    dfs(2 * x + 2);
}

void dfs(int x)
{
    if (a[x] == -1) {
        return;
    }
    dfs(2 * x + 1);
    dfs(2 * x + 2);
    printf("%d ", a[x]);
}

1、叶子结点只用出现在最下两层
2、最下层的叶子一定集中在左部连续位置
3、倒数两层若有叶子结点，一定都在右部连续位置
4、如果结点度为1，则该结点只有左孩子
5、同样结点数的二叉树，完全二叉树的深度最小

//down
void InitialHeap(int parent,int end){
    //大根堆
	int child = parent * 2 + 1;
	while(child < end){
		if(child+1 < end && a[child+1] > a[child]) child++;
		if(a[child] > a[parent]){
			swap(a[child],a[parent]);
			parent = child;   
			child = 2 * parent + 1;  
		}else{
			break;
		}
	}
}
for(int parent=n-1;parent >= 0; parent--){
		InitialHeap(parent,n);
	}

//堆的up
void upHeap(int index){
    while(heap[index] > heap[(index-1) / 2]) {
        swap(heap[index],heap[(index-1) / 2]);
        index = (index - 1) / 2;
    }
}

priority_queue<int> a1; // 大根堆
priority_queue<int, vector<int>, greater<int>> a2; // 小根堆
int main(){
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (a2.empty() || x > a2.top()) {
            a2.push(x);
        } else {
            a1.push(x);
        }
        while (a2.size() > k) {
            a1.push(a2.top());
            a2.pop();
        }
        while (a2.size() < k && !a1.empty()) {
            a2.push(a1.top());
            a1.pop();
        }
    }
    printf("%d ", a2.top());
    a2.pop();
    return 0;
}

         (4)
         /  \
       (2)   (6)
      /   \  /  \
    (1)  (3)(5) (8)
                  \
                  (9)

 (4)     /* BF = -2，不合法值 */                 (6)                    
   \                       进行调整             /  \
     (6)                     ==>              (4)  (8) 
     /  \                                       \
    (5) (8)                                      (5) 

   (4)                                        (6)                    
  /   \                                       /  \
(3)    (6)                  ==>              (4)   (8) 
       /  \                                 / \
      (5) (8)                             (3)  (5)
          / \  // 若在此处插入结点，|BF| >= 2，则需要进行调整，正常4节点要变为6的左孩子，但和原本5冲突，因此冲突的左孩子变为右孩子，如右图

     (6)                                    (3)                    
    /   \                                  /    \
  (3)    (8)             ==>             (4)     (6) 
  / \		                                     / \    
(4)  (5)						        	 (5) (8)
/ \
// 若在此处插入结点，|BF| >= 2 ，则需要进行调整，正常6节点需要右旋变为3的右孩子，但原本的3存在右孩子，因此冲突的右孩子要变为左孩子，如右图

     	  (8)                                     (8)                            (5)
         /   \                                   /   \                          /   \
        (3)   (9)                               (5)   (9)                     (3)    (8)
       /  \               ===>                 /  \          ===>            /  \    /  \
     (2)  (5)                                (3)  (6)                      (2)  (4) (6)  (9)
          / \                                / \                                / \
        (4) (6)                            (2) (4)                                 
        / \    /* 在此处插入结点 */             / \

    (3)                                         (3)                                    (5)  
   /    \                                      /  \                                   /   \
(1)     (7)                 ==>              (1)   (5)          ==>                 (3)    (7) 
        /  \                                       /  \                            /  \    /  \
      (5)  (8)                                   (4)  (7)                        (1)  (4) (6)  (8)
      /  \                                       / \  /  \                            / \  
    (4)  (6)                                         (6) (8)
    / \  
   // 若在此处插入结点

     (3)  /* BF=-2 */                           (3)
	/  \     							    /   \
   (1)  (6)  /* BF=-2 (调整该结点)*/          (1)  (7)
          \              ==>                      /  \ 
           (7)                                   (6)  (9)
             \
              (9)

// 构建一棵 AVL [ 14 9 5 17 11 12 7 19 16 27]
       (11)
	 /    \
    (7)    (17)
   /  \    /   \
  (5) (9) (14) (19)
          /  \     \
         (12) (16)  (27) 

       (11)                                   (11)  /* (11)BF=-2 失衡RR型 */       (17)
	 /    \                                 /     \                              /     \
    (7)    (17) /* (7)BF=-2 失衡RL型 */   (8)      (17)                         (11)     (19)
      \    /   \            ==>          /  \      /   \                       /   \     /   \
      (9) (14) (19)                     (7) (9)  (14)  (19)    ==>            (8)  (14) (16)  (27)
      /    /    /  \                              /    /  \                  /  \  /            \
    (8)  (12) (16)  (27)                        (12) (16)  (27)            (7) (9)(12)         (23)  
                    /                                      /
                   (23)                                   (23)

       (7)B								(7)R  /* cur，当前为根节点再次变色为 B*/
      /   \                               /   \
    (5)R   (8)R          ===>           (5)B   (8)B
    /                                   /
  (1)R /* 插入结点 cur */              (7)R

// RR型举例
       (7)B                                (9)B
          \                               /   \
           (9)R             ===>        (7)R   (12)R
             \
              (12)R  /*插入结点cur */

// LR型举例 
       (7)B                                (5)                        (5)B
      /    \             /* 旋转后*/      /   \      /*染色后 */     /    \
     (3)R   [NULL]B        ====>        (3)   (7)    ===>          (3)R    (7)R
       \
        (5)R  /* 插入结点cur */   

// 删黑色结点，兄弟为黑(兄弟孩子至少一红)，LL型
	    (7)B                  (7)B                        (5)B
	   /    \                 /   \                       /    \
      (5)B   [双黑]   ==>   (5)B   [双黑]    ==>        (2)B    (7)B
     /   \                 /   \                              /   \
    (2)R   (6)R          (2)B   (6)R                         (6)R  [空结点]

// 删黑结点，兄弟为黑(兄弟孩子至少一红) LR型
       (7)B 								    (7)B                          (6)R
      /   \       /*兄孩染色父亲，父亲变黑*/       /   \      /* LR旋转*/        /    \
    (5)B   [双黑]     ==>                       (5)B   [双黑]   ==>            (5)B   (7)B
       \                                         \                                      \
       (6)R    							       (6)R                                  [NULL]单黑

// 删黑结点，兄弟为黑，兄弟孩子均为黑（兄弟变红，双黑上移）
           (15)B                          (15)B                             (18)B    
          /     \        /*双黑上移*/    /     \       /*RR型+染色*/        /     \
       (8)B       (18)B        ===>   (8)[双黑] (18)B     ==>            (15)B     (27)B
      /   \      /   \               /          /   \                   /   \      /    \          
    (6)B [双黑] (17)B (27)R        (6)R       (17)B  (27)R            (8)B  (17)B (25)B  (34)B
                      /  \                           /  \            /
                    (25)B  (34)B                  (25)B  (34)B      (6)R

// 删除黑结点，兄弟为红：兄父变色，父亲朝双黑旋转，保持双黑继续调整
         (18)B                  (18)R                     (15)B                  (15)B
        /     \                /     \                   /     \                /    \
      (15)R   [双黑]   ==>   (15)B   [双黑]   ===>     (9)B    (18)R   ===>   (9)B    (18)R 
     /    \                 /    \                            /    \                  /
   (9)B   (17)B           (9)B   (17)B                      (17)B  [双黑]           (17)R

int spot1,spot2,val;
int matrix[500][500];
//带权有向图
for(int i=1;i<=n;i++){
    cin >> spot1 >> spot2 >> val;
    matrix[spot1][spot2] = val;
}

//1、有向图
//遍历每个点的时候，里面都存有长度为n的链表
list<list<int>> graph;  //无权图
//空间上一开始链表都是空的，不占用空间，随着边的增加，空间开始增加

list<list<int[]>> graph; //带权图
相当于每次增加边时，都增加一个小数组，第一个值为要去的点，第二个值为权值
    
//2、无向图 == 特殊的有向图
将值加入对称的两条边，和邻接矩阵类似

//建图操作 -- 邻接表
struct Edge{
    int u,v,val;
    Egde *nex;
}epool[10001];
struct node{
    Edge *fir;  //出边链表的第一条边
}nodes[10001];
int k = 1; //从下标1的点开始记录
void add(int u,int v,int val){
    epool[k].u = u;
    epool[k].v = v;
    epool[k].val = val;
    epool[u].nex = nodes[u].fir;    //在一个点对应多条边时，指向之前插入的边的地址
    nodes[u].fir = &epool[k];     //更新边的地址，准备为下一条边赋值
    k++;
}
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> epool[i].u >> epool[i].v >> epool[i].val;
        add(u,v,val);
        //无向图
        add(v,u,val);
    }
    //遍历图
    Edge *e = &epool[id]; 遍历哪个顶点指向的边集
    while(e != nullptr) {
        cout << ......
        e = e->nex;
    }
}

int head[N]; // 存储以i为起点的所有边的起始位置
int cnt = 0; // 记录边的数量
struct node {
	int to;    // 第i条边的终点
    int w;     // 第i条边的权值
    int nxt;   // 与第i条边相连的下一条边的位置
}edge[N];   //边数组

int add(int u,int v,int w){
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt++; 
}

void dfs(){
	// 递归出口
    // 枚举调用自身，遍历所有情况
}

// 哈希函数  
H（key） =  key % p  ；p： 最大容量
eg:
以一个最大容量p = 7 的数组为例 a[0-6]
给出一组数据  a = [4,88,12,48,34,56]
H(a[i]) = ... ;  // 将算出的逻辑值放在对应数组下标下
H(4) = 4 % 7 = 4;
H(88) = 88 % 7 = 4;  // 哈希值相同时称为哈希冲突
//开放地址法
若哈希冲突，去其他空的地址下插入冲突的key
//邻接表法
在冲突的哈希地址下，建立一个链表

// 数据 = 地址  （较为浪费空间 数据最大需要开多大数组）

basic_string substr(size_type pos = 0, size_type count = npos) const;

// c++ 风格的函数，归属 <string>，可以指定输入方式，如 cin  标准输入等
// 形式 (1)：使用默认分隔符 '\n'
istream& getline(istream& is, string& str);
// 形式 (2)：显式指定分隔符 delim
istream& getline(istream& is, string& str, char delim);

//基础拼接
string s="";
s = s + "abc";   // s="abc"
//1、字符串切割   s.substr(p,n) :表示从s[p]开始往后截取n个字符,n可省略表示截取到最后
string s1("hello world!");
cout<<s1.substr(6,5);

//2、字符串查找   s.find(b,p) : 表示在字符串s中从p开始向后查找字符串b
//找到返回b的首字符地址，否则返回-1，p可省略表示从头开始查找
int p=s1.find(s2);

//3、字符串翻转  reverse(s.begin(),s.end());
string s2("abc");
cba;  // 输出

//4、插入字符
string s("ade");
s.insert(1,"bc");

int num = stoi(s);  // 将字符串转换成数值类型数据
reverse(s.begin(),s.end());  // 倒置字符串

#include<iostream>
#include<vector>
typedef struct{
	char company_name[100];
    double pizza_d;
    double pizza_weight;
}Piza;
int main(){
    vector<int> vi(4,10); //第一个参数申请的数组长度，第二个参数每个位置的元素赋初值10
    vector<int> vii(vi.begin(),vi.end());
    //1、添加元素
    vi.push_back(值);  //向vi[0] 赋值，尾插
    vi.insert(vi.begin(),4,2);  // 从vi开始的位置插入4个2
    //2、删除元素
    vi.pop_back()    //删除最后一个元素
    vi.erase(vi.begin()+i,vi.begin()+j)  //删除区间[i,j-1] 元素
	//3、访问元素
    vi.front() //访问第一个元素
    vi.back()  //访问最后一个元素
    //4、查找函数
    find(vi.begin(),vi.end(),x)  //x为需要查找的值
    }
    vector<Piza> arr(5);   //利用vector容器技术申请的结构体数组
// resize
// 1. 将容器大小调整为 count
void resize(size_type count);

// 2. 将容器大小调整为 count，新增的元素初始化为 val
void resize(size_type count, const value_type& val);

// v.unique(st, end);  工作机制
// 注：unique必须在整体有序的情况下使用
vector<int> a1;
a1 = [1, 2, 2, 3, 3, 5];  // 使用前
a1 = [1, 2, 3, 5, x, x];  // 使用后，返回值指针指向倒数第二个数，x(从这个数往后都变成无效值)
// 配合 v.erase(st,end);  删除左闭右开 [st , end) 元素
a1.erase(unique(a1.begin(),a1.end() ), a1.end());

//创建二维数组
vector<vector<int>> matrix(3,vector<int>(3)) //创建3*3矩阵
for(int i=0;i<matrix.size();i++){    //二维vector行长度
    for(int j=0;j<matrix[i].size();j++) //获取二维vector的列长度
}

//1、复制与赋值
    //一个vector被赋值或复制时，会创建一个新对象，将所有元素深拷贝，对新vector修改不影响原来的vector
    vector<int> vec1 = {1,2,3};
	vector<int> vec2 = vec1;  //深拷贝
	vector<int> vec3 = move(vec1) //利用move(c++11开始)不用进行深拷贝，直接赋值
}
//2、查找最大元素
	int maxn = vec1.max_size();

//3、去重操作
vector<int> vec = {1,1,2,3,3,4};
vec.erase(unique(vec.begin(),vec.end()),vec.end());

//4、二分查找
//在这个区间上查找>=value的数,返回的是一个指针（迭代器）
lower_bound(起始位置,结束位置,value);
vector<int> vec = {3,7,2,9,11,8,15};
sort(vec.begin(),vec.end());
int t = lower_bound(vec.begin(),vec.end(),7); //查找第一个>=7的数
int t1 = upper_bound(vec.begin(),vec.end(),7); // 查找第一个 >7 的数

vector<int> ans;
auto last = find(ans.rbegin(),ans.front());  // 从尾部到头部查找第一个=ans.front() 的元素
// last 为反向迭代器，查找到的最末尾的元素
last.base()   // 将反向迭代器转为正向迭代器
// 公式 last = last.base - 1 即 last.base 迭代器指向原来迭代器后面一个元素

#include<algorithm>   //包含sort函数的头文件
typedef struct
{
    int a,b;
}node;
node pre[3];
bool cmp(int x,int y){
	return x>y;
}

bool copm(const node &x,const node &y){
    return x.a>x.a;
}

int main()
{
    int arr[5]={5,2,4,1,3};
	//第一个参数要排序的数组首地址，第二个参数要排序的数组尾地址，第三个参数，排序的方式
	sort(arr,arr+4,...) ;
    sort(arr+1,arr+4,cmp);   //按照  x>y的值来进行排序
    sort(pre,pre+3,comp);    //结构体数组 按其中某个成员之间的大小排序
}

//语法1:作为结构体的成员函数（常用）,左操作数是 this，右操作数是参数
返回类型  类名::operator 运算符 (参数列表)const{   // const 代表操作不改变他原本的值
    对应运算符的操作
}

struct node{
    int a,b;
    int idx;
    bool f;
    bool operator<(const node& x) const {    // A& x 引用传参，避免拷贝，const代表只读
        if(a == x.a) {           // 末尾的const 表示不会修改this指向的对象
            return b > x.b;
        }
        return a < x.a;
    }
};

//结构体当作类，在c++中结构体默认是公有的
struct node{
    void operator()(int a,int b){
        return a>b;
    }
}
int main(){
    int a= 1,b=2;
    node();//是一个匿名对象 ，定义一个对象
    node val;
    val(2,2);    //调用重载函数
    //还可以 这样调用
    node()(a,b);    前面是一个匿名对象调用该重载函数
}

int gcd(int a,int b){
    return a%b?b%(a%b):b;
} //__gcd();

int lcm(int a,int b){
    return a/gcd(a,b)*b;    //原式 = a*b/gcd(a,b);  但是a*b可能出界
}

#include<bits/stdc++.h>
#include<stack>
int main(){
    stack<数据类型> stk;
    stk.push(x);    //压入栈
    
    //必须保证栈非空，否则会报错（RE）runtime error
    stk.pop();     //将栈顶弹出
    stk.empty()    //判断栈是否为空,不为空返回true，否则返回false
    
    int T = stk.top();   //返回栈顶的元素，返回类型取决于定义类型 
    
    for(int i=1;i<=5;i++) stk.push(i);   
    while(!stk.empty()){   
        cout<<stk.top();    //将栈顶元素取出
        stk.pop();        //取出后，将栈顶元素出栈
    }    
    结果：54321
    return 0;
}

#include<bits/stdc++.h>
#include<queue>
int main(){
	queue<int> q;
    q.push(值)   //将值插入队列中
    q.pop()     //将队列中 队头元素出队（移除队头元素），并不输出
    q.front()   //返回队头元素，但不移除
    q.back()    //返回队尾元素，不移除
    q.empty()   //判断队列是否为空,不为空返回true，否则返回false
    for(int i=1;i<=5;i++){
		q.push(i);
    }    
    cout<<q.front();
    q.pop();
    cout<<q.front();
	//输出：12    
        
    ***
    //用队列将2个以上元素打包为一个元素
    queue< pair<int,int> > q; 或者 typedef pair<int,int> P; queue<P> q;
    //x = q.front().first   存储坐标x
    //y = q.front().second  存储坐标y
    ***
        
    将元素存入队列
    q.push(make_pair(x,y)); 或者  q.push({x,y});
}

// queue的底层容器是deque，但可以更改为list(queue也可以使用list)
queue<int,deque<int>> q;  <==> queue<int,list<int>> q; 

//deque操作
deque<int> dq;
1、dq.push_front(值);    //  首插
2、dq.push_back(值);     // 尾插
3、dq.pop_front();      // 删除队头元素
4、dq.pop_back();       // 删除队尾元素
dq.front();         //获取队头元素
dq.back();         //获取队尾元素
dq.size();     //计算元素个数
dq.empty();    //判空

priority_queue<int> que;  //默认大顶堆
que.size();
que.push(x);   //插入x
que.pop();     //删除优先级最高的元素

que.top();     //访问优先级最高的元素，堆顶元素
que.empty();  //判空

//第一个参数表示存储的参数类型
//第二个参数表示所用的容器
//第三个参数是(仿函数) 比较方法  less<int> 大顶堆    greater<int> 小顶堆
priority_queue<int,vector<int>, greater<int>> que;

struct node{
    int x,y;
    bool operator < (const node &b) const{
        return this->x < b.x;    //重载小于号less，大的数还是优先级高；若重载大于号，小的数优先级高
    }
};
priority_queue<node> que;
que1.push({1,2});
que1.push({9,-1});

while(!que.empty()){
	cout<< que.top().x << endl;
    que.pop();
}

#include<set>
set<int> p;
p.empty();
p.size();
p.insert(value);
p.erase(value);

#include<set>
multiset<int,greater<int>> ms; // 指定降序
ms.insert(x);    // 插入
ms.erase(x);     // 删除
// 遍历，访问，不允许 ms[i] 取值
for(auto i = ms.begin(); i != ms.end(); ++i){
    cout<< i << " ";      // 迭代器实现访问
}
for(auto& i : ms){  cout<< ms << " ";}
//二分查找
ms.lower_bound(v);  //第一个 >= 元素的迭代器
ms.upper_bound(v);  // 第一个 > 元素的迭代器
// 只有当 v 大于容器中所有元素时，返回 end() 迭代器

#include<bits/stdc++.h>  || #include<map>
map<T_key,T_value> m;
// map : 基于红黑树实现，按键排序，查找效率平均O(logn)
// 自定义类型需要比较时，重载小于号
struct node{
    int x,;
    bool operator < (const node &u) const{
        return x == u.x ? y < u.y : x < u.x;
    }
}
map<node,int> mp;
//常用操作
insert({key,value})
erase(key)
find(key)
operator[key] //返回指定的键值
count(key)   // mp.count(key) 访问该键所映射值的次数   
size()    //键值对数
clear()  empty()  begin() end()

//查找key是否存在
map<int,int> mp;
if(mp.find(key) != mp.end()) cout<<mp[key]<<'\n';
if(mp.count(key))  cout<<mp[key]<<'\n';

//遍历map
for(auto &i : mp) {
    cout<< i.first << " " << i.second << '\n';
}
for(auto &[key,val] : mp) {
    cout<< key << " " << val <<'\n';
}

// unordered_map 基于哈希表实现的map集合容器
// 元素无序，查找性能平均O(1)，应用于需要快速查找，无序
// 头文件 #include<unordered_map>
unordred_map<string,int> mp;
mp.insert({"Alice",25});   // 增加键值对
mp.emplace("David",32);    //增加，效率更高
mp["Char"]=28;       // 若存在键修改，不存在插入

// 删除
mp.erase("Alice");
// 遍历
for(auto it = mp.begin(); it != mp.end(); ++it){
	cout<<it->first<<" "<< it->second <<endl;
}
mp.empty()     // 判空
mp.size()     // 键的数量

using node = tuple<ll, int, int>;
 // 建图时
vector<node> e;
// 取值
node a;
get<0>(a);  // 取第1个元素
// 对 tuple 排序，lambda表达式
sort(e.begin(),e.end(),
    [](const node& x,const node& y){
		return get<0>(x) < get(0).y;   // <第n个元素>从0索引开始            
    }
);

//用法
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
    //令a[i] = i;
    int tot = n;   //所有全排列的数量
    
    do{
    	for(int i=1;i<=tot;i++){
    		cout<<a[i]<<" ";
		}
		cout<<endl;
	}while(next_permutation(a+1,a+n+1)); 
    return 0;
}