Có \(n\) trạm xăng được đánh số từ \(1\) đến \(n\) trên đường vành đai (có thể đi lại giữa hai trạm xăng \(i\) và \(i + 1\) cũng như trạm xăng \(1\) và \(n\)). Bạn cần xuất phát ở một trạm xăng bất kỳ, đi qua tất cả các trạm xăng theo hướng chiều kim đồng hồ hoặc ngược chiều kim đồng hồ rồi quay lại địa điểm xuất phát. Ban đầu xe của bạn không có xăng. Ở trạm xăng thứ \(i\) bạn có thể đổ thêm \(p_i\) lít xăng, mỗi lít xăng sẽ giúp bạn di chuyển \(1\) ki-lô-mét. Với mỗi trạm xăng, hãy xác định xem, nếu xuất phát ở trạm xăng đó thì có thể hoàn thành được hành trình không.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai gồm hai số nguyên \(p_i\) và \(r_i\), lần lượt là lượng xăng ở trạm thứ \(i\) và khoảng cách tới trạm xăng tiếp theo, bất kể di chuyển theo hướng nào.

Dữ liệu ra

• In ra \(n\) dòng, ở dòng thứ \(i\) in ra TAK nếu có thể xuất phát ở trạm thứ \(i\) và hoàn thành hành trình, ngược lại in ra NIE.

Giới hạn:

• \(1 \le n \le 10^6\).
• \(0 \le p_i, d_i \le 2 \times 10^9\).

Input 1

5
3 1
1 2
5 2
0 1
5 4

Output 1

TAK
NIE
TAK
NIE
TAK