Babushka Bajtmiła 正在举办一场派对！派对的主菜是她著名的波兰饺子（pierogi）。

派对上会有 $n$ 个盘子，Babushka 计划在第 $i$ 个盘子上放置恰好 $p_i$ 个饺子（所有的 $p_i$ 值各不相同）。虽然这项任务对一位老太太来说似乎太重了，但 Bajtmiła 迎接了挑战，并几乎立刻准备好了所有需要的饺子，分装在 $n$ 个盘子中，共有 $(p_1, \dots, p_n)$ 个饺子。接着，Bajtmiła 将这些盘子分发了出去。然而，她很快意识到，虽然她把数字搞对了，但她弄乱了盘子的顺序。

Bajtmiła 已经很累了，她只愿意执行一种操作：她可以选择编号为 $i$ 和 $j$ 的两个盘子，并交换这两个盘子上的饺子数量。换句话说，如果盘子 $i$ 上有 $x$ 个饺子，盘子 $j$ 上有 $y$ 个饺子，那么在这次操作后，盘子 $i$ 上将有 $y$ 个饺子，盘子 $j$ 上将有 $x$ 个饺子。执行这样一次操作需要恰好 $|x - y| + C$ 秒的时间——其中 $C$ 秒用于寻找合适的勺子，每移动一个饺子需要 1 秒。

派对很快就要开始了！现在，Bajtmiła 不允许你在厨房里乱动，但她信任你的算法能力。她请求你找到一个操作序列来恢复饺子数量的期望顺序，并且必须以最短的时间完成。你能帮助 Bajtmiła 吗？

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \leqslant z \leqslant 1000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个数字 $n$ 和 $C$ ($1 \leqslant n \leqslant 200\,000, 1 \leqslant C \leqslant 10^9$)，其含义如上所述。

接下来的 $n$ 行描述了连续的盘子。第 $i$ 行包含两个数字 $a_i$ 和 $p_i$ ($1 \leqslant a_i, p_i \leqslant 10^9$)，分别表示第 $i$ 个盘子上当前的饺子数量和期望的饺子数量。

在每个测试用例中，数字 $a_i$ 各不相同。此外，集合 $\{a_1, a_2, \dots, a_n\}$ 和 $\{p_1, p_2, \dots, p_n\}$ 是相同的。

所有测试用例中 $n$ 的总和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，你的输出必须符合以下描述：

在第一行，打印两个整数 $S$ 和 $K$ —— 分别表示总耗时和你的方案中的操作次数。

接下来的 $K$ 行应描述你的方案。在第 $k$ 行打印两个数字 $x_k$ 和 $y_k$，表示你方案中的第 $k$ 次操作交换了第 $x_k$ 个盘子和第 $y_k$ 个盘子上的饺子数量。

在执行完你方案中的所有操作后，第 $i$ 个盘子必须恰好包含 $p_i$ 个饺子。

样例

输入 1

1
4 2
2 4
3 2
1 1
4 3

输出 1

6 2
2 1
4 1

说明

序列 $(2, 3, 1, 4)$ 应变为序列 $(4, 2, 1, 3)$。我们首先对前两个盘子执行操作，得到序列 $(3, 2, 1, 4)$，耗时为 $|3 - 2| + 2 = 3$。第二次也是最后一次操作交换了第一个和第四个盘子上的饺子，得到期望的序列 $(4, 2, 1, 3)$。该操作的耗时为 $|3 - 4| + 2 = 3$，总耗时为 $6$，这是可能的最小值。