有 $n$ 名学生正在 Shilish 教授的课堂上玩“独裁者游戏”。 该游戏包含 $n \cdot (n - 1)$ 轮，对于每一对有序的人 $(i, j)$（其中 $i \neq j$）各进行一轮。 给定一个正整数 $s$。在每一轮中，如果两人达成一致，则 $s$ 枚硬币将在人 $i$ 和人 $j$ 之间分配。在针对一对 $(i, j)$ 的轮次中，玩家 $i$ 是提议者，玩家 $j$ 是响应者。玩家 $i$ 应向玩家 $j$ 提议一个整数数量的硬币 $c$ ($0 \le c \le s$) 让其拿走。如果 $j$ 同意，则在本轮中玩家 $i$ 获得 $s - c$ 枚硬币，玩家 $j$ 获得 $c$ 枚硬币。否则，两名玩家均获得 0 枚硬币。游戏结束时，每位玩家的得分是该玩家在游戏过程中获得的所有硬币总数。

所有玩家决定遵循以下策略：每位玩家 $i$ 选择一个整数 $a_i$ ($0 \le a_i \le s$)。在玩家 $i$ 参与的每一轮中（无论担任什么角色），如果达成一致，他们希望从这笔交易中至少获得 $a_i$ 枚硬币。因此，如果达成一致的条件得到满足，他们会提议一定数量的硬币并同意一定数量的硬币。数字 $a_1, a_2, \dots, a_n$ 在游戏开始前对所有人已知，并将被玩家用于做出最优提议，以在游戏结束时获得最高得分。在每一轮中，提议者都会尝试达成一致（如果可能的话）。

玩家 $i$ 比其他玩家更早获得了关于数组 $a$ 的信息。为了获得更高的分数，他们可以将 $a_i$ 的值更改为 $0$ 到 $s$ 之间的任何其他整数。注意，只有玩家 $i$ 会更改他们的值。如果该值选择得当，他们能获得的最高分数是多少？获得该最高分数的选择方案数是多少？请找出所有玩家 $i$ 的答案。注意，你需要独立地为每位玩家计算这些答案。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。 测试用例描述如下。 每个测试用例的第一行包含两个整数 $n, s$ ($1 \le n \le 5 \cdot 10^5, 1 \le s \le 10^{12}$)，分别表示玩家人数和每轮使用的硬币数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le s$)。 保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，打印 $n$ 行。在第 $i$ 行打印两个整数：玩家 $i$ 可以实现的最高得分，以及选择 $a_i$ 以获得该最高得分的方案数。

样例

样例输入 1

5
1 1000000000000
0
3 6
3 5 6
5 100
45 30 70 55 45
4 6
6 2 6 6
4 5
5 0 3 0

样例输出 1

0 1000000000001
2 1
6 1
6 2
320 1
305 1
405 1
345 1
320 1
8 1
0 7
8 1
8 1
20 1
11 1
20 1
11 1