假设您正在使用某些音频流服务。该服务拥有 $$$n$$$ 活跃用户和 $$$10^9$$$ 用户可以收听的曲目。用户可以喜欢曲目,并且根据喜欢,服务应该向他们推荐新曲目。
曲目编号从 $$$1$$$ 到 $$$10^9$$$。事实证明,跟踪第 $$$i$$$ 个用户的点赞形成了一个分段 $$$[l_i, r_i]$$$。
假设用户 $$$j$$$ 是用户 $$$i$$$ ($$$j \neq i$$$) 的预测器,如果用户 $$$j$$$ 喜欢第 $$$i$$$ 个用户喜欢的所有曲目(也可能还有其他一些曲目)。
另外,假设如果第 $$$i$$$ 个用户尚未喜欢某首曲目,但第 $$$i$$$ 个用户的每个预测者都喜欢该曲目,则强烈推荐该曲目给用户 $$$i$$$。
计算每个用户$$$i$$$的强烈推荐曲目数量。如果用户没有任何预测变量,则为该用户打印 $$$0$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是 $$$t$$$ 案例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 用户数量。
接下来的 $$$n$$$ 行每行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$) — 第 $$$i$$$ 个用户喜欢的曲目片段。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数,其中第 $$$i$$$ 个整数是第 $$$i$$$ 个用户强烈推荐的曲目数量(或 $$$0$$$,如果该用户没有任何预测变量)。
示例
输入 #1
4 3 3 8 2 5 4 5 2 42 42 1 1000000000 3 42 42 1 1000000000 42 42 6 1 10 3 10 3 7 5 7 4 4 1 2
输出 #1
0 0 1 999999999 0 0 0 0 0 2 3 2 4 8
注意
在第一个测试用例中:
- 第一个用户没有预测器;
- 第二个用户没有预测器;
- 第三个用户有两个预测变量:用户 $$$1$$$ 和 $$$2$$$;只有曲目 $$$3$$$ 被他们俩喜欢,而第三个用户不喜欢。
在第二个测试用例中,第二个用户是第一个用户的预测者。因此,除了 $$$42$$$ 之外,所有曲目均强烈推荐给第一个用户。
在第三个测试用例中,第一个用户有两个预测变量:用户 $$$2$$$ 和 $$$3$$$,但是没有他们喜欢而第一个用户自己不喜欢的曲目。