Wilbur is playing with a set of n points on the coordinate plane. All points have non-negative integer coordinates. Moreover, if some point ( x , y ) belongs to the set, then all points ( x ' , y ' ), such that 0 ≤ x ' ≤ x and 0 ≤ y ' ≤ y also belong to this set. Now Wilbur wants to number the points in the set he has, that is assign them distinct integer numbers from 1 to n . In order to make the numbering aesthetically pleasing , Wilbur imposes the condition that if some point ( x , y ) gets number i , then all ( x ' , y ' ) from the set, such that x ' ≥ x and y ' ≥ y must be assigned a number not less than i . For example, for a set of four points ( 0 , 0 ), ( 0 , 1 ), ( 1 , 0 ) and ( 1 , 1 ), there are two aesthetically pleasing numberings. One is 1 , 2 , 3 , 4 and another one is 1 , 3 , 2 , 4 . Wilbur's friend comes along and challenges Wilbur. For any point he defines it's special value as s ( x , y ) = y - x . Now he gives Wilbur some w 1 , w 2 ,..., w n , and asks him to find an aesthetically pleasing numbering of the points in the set, such that the point that gets number i has it's special value equal to w i , that is s ( x i , y i ) = y i - x i = w i . Now Wilbur asks you to help him with this challenge. The first line of the input consists of a single integer n ( 1 ≤ n ≤ 100 000 ) — the number of points in the set Wilbur is playing with. Next follow n lines with points descriptions. Each line contains two integers x and y ( 0 ≤ x , y ≤ 100 000 ), that give one point in Wilbur's set. It's guaranteed that all points are distinct. Also, it is guaranteed that if some point ( x , y ) is present in the input, then all points ( x ' , y ' ), such that 0 ≤ x ' ≤ x and 0 ≤ y ' ≤ y , are also present in the input. The last line of the input contains n integers. The i -th of them is w i ( - 100 000 ≤ w i ≤ 100 000 ) — the required special value of the point that gets number i in any aesthetically pleasing numbering. If there exists an aesthetically pleasan