CF2042D Recommendations

Suppose you are working in some audio streaming service. The service has $ n $ active users and $ 10^9 $ tracks users can listen to. Users can like tracks and, based on likes, the service should recommend them new tracks. Tracks are numbered from $ 1 $ to $ 10^9 $ . It turned out that tracks the $ i $ -th user likes form a segment $ [l_i, r_i] $ . Let's say that the user $ j $ is a predictor for user $ i $ ( $ j \neq i $ ) if user $ j $ likes all tracks the $ i $ -th user likes (and, possibly, some other tracks too). Also, let's say that a track is strongly recommended for user $ i $ if the track is not liked by the $ i $ -th user yet, but it is liked by every predictor for the $ i $ -th user. Calculate the number of strongly recommended tracks for each user $ i $ . If a user doesn't have any predictors, then print $ 0 $ for that user.

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Next, $ t $ cases follow. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of users. The next $ n $ lines contain two integers $ l_i $ and $ r_i $ per line ( $ 1 \le l_i \le r_i \le 10^9 $ ) — the segment of tracks the $ i $ -th user likes. Additional constraint on the input: the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

For each test case, print $ n $ integers, where the $ i $ -th integer is the number of strongly recommended tracks for the $ i $ -th user (or $ 0 $ , if that user doesn't have any predictors).

In the first test case: - the first user has no predictors; - the second user has no predictors; - the third user has two predictors: users $ 1 $ and $ 2 $ ; only track $ 3 $ is liked by both of them and not liked by the third user. In the second test case, the second user is a predictor for the first user. Therefore, all tracks, except $ 42 $ , are strongly recommended for the first user. In the third test case, the first user has two predictors: users $ 2 $ and $ 3 $ , but there is no track that is liked by them and not liked by the first user himself.