Bạn có \(n\) xu, mỗi xu có khối lượng phân biệt.

Có hai stack (chồng) rỗng lúc ban đầu. Tại mỗi bước bạn bỏ một đồng xu vào một stack. Bạn không bao giờ lấy xu ra khỏi một chồng nào cả.

Sau mỗi lượt, bạn cần xác định chồng xu nào nặng hơn (nếu có thể chắc chắn được là stack nào nặng hơn).

Input

• Dòng đầu tiên chứa số nguyên \(n\): số lượng đồng xu. Các đồng xu được đánh số \(1,2,\dots,n\). Bạn biết rằng xu \(i\) luôn nặng hơn xu \(i-1\), nhưng không biết khối lượng chính xác của chúng.
• Sau đó là \(n\) dòng mô tả các lượt đi. Mỗi dòng chứa hai số nguyên \(c,s\): bỏ xu \(c\) vào chồng \(s\) (1: bên trái, 2: bên phải)

Output

• Sau mỗi lượt, in ra < nếu chồng bên phải nặng hơn, > nếu chồng bên trái nặng hơn, và ? nếu chúng ta không thể biết được chồng nào nặng hơn.

Constraints

• \(1 \leq n \leq 2\cdot 10^5\)

Example

3
2 1
3 2
1 1

<
?