Jack found N stones and arranged them in order of increasing mass. The masses of all stones are different. The lightest stone was number 1, the next ≤ 2 and so on, the heaviest one was numbered N.
Jack has a scale and decided to put all the stones on it in some order. The order in which he will place the stones is known, and which stone will land on which bowl.
Your task — determine the state of the scales after adding each stone. The exact weights of the stones are not known — only their numbers are given.
Input
The first line contains the integer N (1 N ≤ 100000).
Each of the next N lines contains two integers: R (1 ≤ R ≤ N) and S (1 ≤ S ≤ 2). R is the number of the stone that will be placed on the bowl S. All Rs will be different.
Imprint
Output N lines - one for each stone. If bowl 1 is heavier after adding the corresponding stone, print “<”. If side 2 is heavier, print “>”. If it is impossible to determine what state the scales will be in, print “?”.
Examples
| # |
Input |
Output |
| 1 |
5
1 2
3 1
2 1
4 2
5 1 |
<
>
>
?
>
|