화성 여행

Byteazar가 화성에 있는 우주 정거장들을 둘러보기로 했다. 화성의 모든 우주 정거장은 하나의 원 둘레 위에 놓여 있다. Byteazar는 그중 한 정거장에 착륙한 뒤, 특수 연료로 움직이는 특별한 이동 수단을 타고 원 둘레를 따라 이동한다. 이 연료 $1$리터로 정확히 $1$미터를 이동할 수 있다.

각 정거장에는 서로 다른 양의 연료가 비축되어 있다. Byteazar는 현재 있는 정거장에서 연료를 보급할 수 있지만, 그 정거장에 있는 양보다 많이 가져갈 수는 없다(연료 탱크의 용량은 무제한이다). 보급한 연료로 다음 정거장까지 도달할 수 있어야 한다.

Byteazar는 모든 정거장을 방문할 수 있도록 어느 정거장에 착륙할지 정해야 한다. 여행이 끝나면 처음 착륙한 정거장으로 다시 돌아와야 한다. 여행 내내 Byteazar는 원 둘레를 따라 이동하며, 두 방향 중 한 방향을 골라 그 방향으로만 계속 이동한다.

다음을 수행하는 프로그램을 작성하라:

• 표준 입력에서 정거장의 수, 정거장 사이의 거리, 각 정거장에 비축된 연료의 양을 읽는다,
• 각 정거장에 대해 그 정거장에서 출발하여 자유롭게 고른 한 방향으로 이동해 모든 정거장을 방문하고 다시 착륙 지점으로 돌아올 수 있는지 판정한다,
• 결과를 표준 출력에 기록한다.

첫째 줄에 우주 정거장의 수 $N$ ($3 \le N \le 1{,}000{,}000$)이 주어진다. 정거장은 $1$번부터 $N$번까지 번호가 매겨져 있다.

이어지는 $N$개의 줄에 각 정거장과 정거장 사이 거리에 대한 정보가 주어진다. $(i+1)$번째 줄에는 두 정수 $p_i$와 $d_i$ ($p_i \ge 0$, $d_i > 0$)가 주어진다. $p_i$는 $i$번 정거장에 비축된 연료의 양(리터)이고, $d_i$는 $i$번 정거장과 $(i+1)$번 정거장 사이의 거리(미터)이다(단, $d_N$은 $N$번 정거장과 $1$번 정거장 사이의 거리이다).

비축된 연료의 총합과 모든 정거장 사이 거리의 총합은 각각 $2{,}000{,}000{,}000$을 넘지 않는다.

$N$개의 줄을 출력한다. $i$번째 줄에는 Byteazar가 $i$번 정거장에 착륙할 수 있으면 TAK(폴란드어로 '예')를, 그렇지 않으면 NIE(폴란드어로 '아니오')를 출력한다.