题目描述

在一条坐标范围为 $1$ 至 $2n$ 的数轴上有 $n$ 条线段。

现给定正整数 $k$，对于每一条线段，你需要求出：在删除该线段后，再添加至多一条线段，数轴上最多有多少个整点恰好被 $k$ 条线段覆盖。

注意你添加的线段的左右端点也应在区间 $[1,2n]$ 内。

输入格式

本题有多组数据。第一行一个正整数 $T\ (1\le T\le10^4)$，表示数据组数。

对于每组数据：

第一行两个正整数 $n,k\ (1\le n\le2\times10^5,1\le k\le n)$。

接下来 $n$ 行，第 $i$ 行两个正整数 $l_i,r_i\ (1\le l_i\le r_i\le 2n)$，表示第 $i$ 条线段的左端点和右端点。

保证 $T$ 组数据中 $n$ 的和不超过 $2\times10^5$。

输出格式

对于每组数据：

输出 $n$ 行，第 $i$ 行表示删除第 $i$ 条线段的答案。

3
3 2
1 3
2 3
2 6
3 2
1 3
3 3
3 6
2 1
1 1
3 3

5
5
3
4
5
3
3
4