好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：POI 2004

John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 $n$ 个车站，按顺时针编号 $1$ 到 $n$。每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。

任务：判断以每个车站为起点能否按条件成功周游一周（顺时针和逆时针都要考虑）。

---

输入格式

第一行是一个整数 $n$，表示环形公路上的车站数；

接下来 $n$ 行，每行两个整数 $p_i, d_i$，分别表示第 $i$ 号车站的存油量（升）和第 $i$ 号车站到下一站的距离（千米）。

注意：第 $n$ 站的下一站是第 $1$ 站（环形）。

---

输出格式

输出共 $n$ 行，如果从第 $i$ 号车站出发，一直按顺时针（或逆时针）方向行驶，能够成功周游一圈，则在第 $i$ 行输出 TAK，否则输出 NIE。

---

样例

样例输入

5
3 1
1 2
5 2
0 1
5 4

样例输出

TAK
NIE
TAK
NIE
TAK

样例解释

车站数据（$p_i, d_i$）：

1. (3,1)
2. (1,2)
3. (5,2)
4. (0,1)
5. (5,4)

顺时针判断：

设 $a_i = p_i - d_i$（表示从 $i$ 站到 $i+1$ 站油量的净变化）。

环形前缀和 $s_i = a_1 + a_2 + \dots + a_i$（对 $n$ 取模意义下累加，但这里我们做的是环形扫描）。

条件：从 $i$ 出发顺时针可行当且仅当 $\forall j \in [i, i+n-1]$，$s_j - s_{i-1} \ge 0$，即最小前缀和 $\ge 0$。

用单调队列维护窗口最小值即可。

逆时针同理，但需要反转方向并重新计算 $a_i$。

最终每个站如果顺时针或逆时针有一个可行，输出 TAK，否则 NIE。

样例结果：

• 站1：可行
• 站2：不可行
• 站3：可行
• 站4：不可行
• 站5：可行

---

数据范围

对于全部数据：

• $3 \le n \le 10^6$
• $0 \le p_i \le 2\times 10^9$
• $0 < d_i \le 2\times 10^9$

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题需要分别判断 顺时针 和 逆时针 两个方向。

步骤：

1. 顺时针：

• 令 $a_i = p_i - d_i$；
• 构造长度为 $2n$ 的序列 $b = [a_1, a_2, \dots, a_n, a_1, a_2, \dots, a_n]$；
• 计算前缀和 $s_0=0, s_i = s_{i-1} + b_i$（$i$ 从 $1$ 到 $2n$）；
• 对于起点 $i$（$1 \le i \le n$），需要检查 $s_{i}, s_{i+1}, \dots, s_{i+n-1}$ 是否都 $\ge s_{i-1}$，即 $\min_{j \in [i, i+n-1]} s_j \ge s_{i-1}$。
• 可以用单调队列维护窗口 $[i, i+n-1]$ 的 $s_j$ 最小值。

2. 逆时针：

• 逆时针时，从 $i$ 出发先到 $i-1$ 站，再到 $i-2$，以此类推。
• 重新定义 $a'_i = p_i - d_{i-1}$，其中 $d_0 = d_n$（因为第 $1$ 站的前一站是第 $n$ 站）；
• 类似顺时针，构造 $2n$ 的序列并求前缀和，用单调队列判断。

3. 合并：

• 如果 $i$ 顺时针或逆时针有一个可行，则输出 TAK，否则 NIE。

复杂度：$O(n)$。

注意：由于 $n$ 很大，需要高效输入输出，使用 scanf/printf 或关闭同步的 cin/cout。