Bajtazar 决定整理他的房间！

但他整理得并不顺利。他在整理过程中遇到的问题之一是书架上 $n$ 本书的摆放。书架上有 $n$ 个位置，编号从 $1$ 到 $n$，每个位置上恰好有一本书。我们将书编号为 $1$ 到 $n$，使得最终书 $1$ 应该在位置 $1$，书 $2$ 在位置 $2$，以此类推。Bajtazar 可以快速计算出当前摆放方式下的逆序对数量。

逆序对是指一对不同的位置 $i$ 和 $j$，满足 $i < j$，且位置 $i$ 上的书 $p_i$ 与位置 $j$ 上的书 $p_j$ 满足 $p_i > p_j$。

你的任务是帮助 Bajtazar 整理书架上的书。你最多可以执行 $m$ 次操作。一次操作包括选择任意两个位置（可以是同一个位置），交换它们当前所在的书，然后从 Bajtazar 那里获取当前摆放方式下的逆序对数量。在你完成所有交换后，书架上的书应该是有序的，即按 $1, 2, \dots, n$ 的顺序排列。

交互

这是一个交互式题目。你需要编写一个程序，对 Bajtazar 的书进行操作，使得最后书是有序的。在本题中，与评测程序的通信可以通过库或标准输入输出进行。你可以选择你喜欢的选项。

不要同时使用这两种方法。

选项 1：使用库进行通信

C++ 程序开头必须包含：

#include "porlib.h"

库提供以下函数： int DajN() – 返回书的数量 $n$。 int Zamiana(int a, int b) – 交换位置 $a$ 和 $b$ 上的书（$1 \le a, b \le n$）；函数返回交换后的逆序对数量。当该函数返回 $0$ 时，说明书已排好序，你的程序应结束运行，不再调用库函数。

Python 程序开头必须包含：

from porlib import DajN, Zamiana

库提供以下函数： DajN() – 返回书的数量 $n$。 Zamiana(a : int, b : int) – 交换位置 $a$ 和 $b$ 上的书（$1 \le a, b \le n$）；函数返回交换后的逆序对数量。当该函数返回 $0$ 时，说明书已排好序，你的程序应结束运行，不再调用库函数。

一般信息 库函数可以以任意顺序调用，返回书的数量 $n$ 的函数可以多次调用。使用任何带有非法参数的函数都将导致“错误答案”判决。同样，从标准输入读取或向标准输出写入也可能导致“错误答案”判决。

选项 2：通过标准输入/输出进行通信

在标准输入的第一行将包含一个整数 $n$，表示书的数量。随后，评测程序等待两个整数 $a$ 和 $b$，表示要交换的位置；你需要将它们输出到标准输出，用单个空格分隔并以换行符结束。然后，你需要从标准输入读取一个整数，表示交换后的逆序对数量。

当你读取到 $0$ 时，说明书已排好序，你的程序应结束运行，不再与标准输入输出进行交互。

C++，流式输入/输出 需要包含相应的头文件（#include <iostream>）。在输出每一行时，必须使用 std::endl。通信起始示例：

std::cin >> n;
std::cout << a << ' ' << b << std::endl;
std::cin >> number_of_inversions;

C++，通过 stdio 进行输入/输出 需要包含相应的头文件（#include <cstdio>）。在输出每一行后，必须调用 fflush(stdout)。通信起始示例：

scanf("%d", &n);
printf("%d %d\n", a, b);
fflush(stdout);
scanf("%lld", &number_of_inversions);

Python 在输出每一行后，必须使用 flush=True。通信起始示例：

n = int(input())
print(f"{a} {b}", flush=True)
number_of_inversions = int(input())

样例

输入格式 1

6
6
3
2
1
0

输出格式 1

1 2
1 2
2 3
6 5

说明

假设书的初始摆放是 $1, 3, 2, 4, 6, 5$，交换次数限制为 $m = 1000$。

子任务

你可以假设在每个测试中，书架上书的初始顺序是预先确定的，之后才处理对书的操作。