蓝色，天空、海洋和你的眼睛的颜色。 绿色，自然、繁衍和生命的颜色。 紫色，代表良好的判断力，以及那些寻求精神满足的人们的颜色。 橙色，唯一一种同时也是水果名称的颜色。 黄色，笑脸的颜色。 红色，最温暖的颜色。

Rikka 喜爱所有这些颜色，但哪一种才是她最喜欢的呢？她找到了 $k$ 种不同的颜色，编号从 $1$ 到 $k$，她知道最好的颜色应该是将它们全部混合在一起后的颜色。这种最好的颜色被称为 DREAM。

Rikka 还准备了一个长度为 $10^9$ 的长条形调色板。她在调色板上指定了 $n$ 个线段。一个由两个整数 $l$ 和 $r$ ($0 \le l < r \le 10^9$) 描述的线段，表示调色板上从距离左端点 $l$ 处到距离左端点 $r$ 处的一段区域。

她将为每个指定的线段均匀地涂上她找到的这些颜色（从 $1$ 到 $k$）中的任意一种。由于这些线段可能会重叠，某些区域可能包含多种不同颜色的颜料。如果某些区域包含了她找到的所有 $k$ 种不同的颜色，那么这些区域就会混合成 DREAM。

现在，Rikka 希望你最大化调色板上所有能混合成 DREAM 的区域的总长度。你还需要提供一个可行的方案。

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示 Rikka 指定的线段数量，以及 $k$ ($1 \le k \le 2 \times 10^5$)，表示 Rikka 找到的颜色数量。

接下来的 $n$ 行，每行包含两个整数 $l$ 和 $r$ ($0 \le l < r \le 10^9$)，表示调色板上的第 $i$ 个线段。

输入保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^6$。

输出格式

对于每个测试用例，输出两行。第一行输出一个整数，表示所求区域的最大总长度。第二行输出 $n$ 个用空格分隔的整数，描述一个可行的方案，其中第 $i$ 个数字表示第 $i$ 个线段所涂的颜色。

所有可行的方案均被允许，你可以输出其中任意一个。

样例

输入 1

1
3 2
1 5
2 4
3 6

输出 1

3
1 2 2