Weighing the stones

Seunghyun picked up $N$ stones and lined them up from the lightest to the heaviest. No two stones weigh the same. The lightest stone has rank 1, the second lightest has rank 2, and the heaviest has rank $N$.

Seunghyun puts the stones on a two pan balance one at a time. The order of the stones and the pan each stone goes on are fixed in advance. He never tells you the actual weights, only the ranks.

Write a program that decides which way the balance tips after each stone is placed. Every weight is positive, and a stone of higher rank is heavier than a stone of lower rank. Any assignment of weights that respects those two conditions is possible. The balance tips toward pan 1 only if pan 1 is heavier under every possible assignment, and the same rule holds for pan 2. If the result depends on the assignment, or the two pans can weigh the same, the heavier side is not certain.

The first line has the number of stones $N$ ($1 \le N \le 100000$). Each of the next $N$ lines has two integers $R$ ($1 \le R \le N$) and $S$ ($1 \le S \le 2$). $R$ is the rank of the stone being placed and $S$ is the number of the pan it goes on. All values of $R$ are different, so each rank from $1$ to $N$ appears exactly once.

Print one line for each stone as it is placed. Print > if pan 1 is heavier, < if pan 2 is heavier, and ? if you cannot be sure which side is heavier.