B'Polycarp has invited n friends to celebrate the New Year. During the celebration, he decided to take a group photo of all his friends. Each friend can stand or lie on the side. Each friend is characterized by two values h_i (their height) and w_i (their width). On the photo the i -th friend will occupy a rectangle h_i x w_i (if they are standing) or w_i x h_i (if they are lying on the side). The j -th friend can be placed in front of the i -th friend on the photo if his rectangle is lower and narrower than the rectangle of the i -th friend. Formally, at least one of the following conditions must be fulfilled: For example, if n = 3 , h=[3,5,3] and w=[4,4,3] , then: In other cases, the person in the foreground will overlap the person in the background. Help Polycarp for each i find any j , such that the j -th friend can be located in front of the i -th friend (i.e. at least one of the conditions above is fulfilled). Please note that you do not need to find the arrangement of all people for a group photo. You just need to find for each friend i any other friend j who can be located in front of him. Think about it as you need to solve n separate independent subproblems. The first line contains one integer t ( 1 <= q t <= q 10^4 ) -- the number of test cases. Then t test cases follow. The first line of each test case contains one integer n ( 1 <= q n <= q 2 cdot 10^5 ) -- the number of friends. This is followed by n lines, each of which contains a description of the corresponding friend. Each friend is described by two integers h_i and w_i ( 1 <= q h_i, w_i <= q 10^9 ) -- height and width of the i -th friend, respectively. It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10^5 . For each test case output n integers on a separate line, where the'...