// ❌ 溢出示例：
int a = 1e9, b = 1e9;
cout << a + b;     // 溢出（结果 > INT_MAX）
cout << a * 2;     // 溢出
cout << a * a;     // 灾难性溢出

// ❌ 比较时溢出：
if (a * b > 1e18) ...  // a*b 本身可能已经溢出了！

// ✅ 安全版本：
cout << (long long)a + b;
cout << (long long)a * 2;
cout << (long long)a * a;
if ((long long)a * b > (long long)1e18) ...  // 用 long long 比较

// 查找第一个 A[i] >= target 的下标（lower_bound 行为）：

// ❌ 错误：常见二分查找写法错误
int lo = 0, hi = n - 1;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (A[mid] < target) lo = mid;      // BUG：应为 lo = mid + 1
    else hi = mid - 1;                   // BUG：应为 hi = mid
}

// ✅ 正确：标准 lower_bound 模板
int lo = 0, hi = n;  // hi = n（而非 n-1），以允许"未找到"的情况
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (A[mid] < target) lo = mid + 1;  // target 在 [mid+1, hi]
    else hi = mid;                       // target 在 [lo, mid]
}
// lo = hi = 第一个 A[i] >= target 的下标；lo=n 表示未找到

// ❌ 常见错误：循环多跑或少跑一次
for (int i = 1; i < n; i++) ...    // 若本意是 i=0 到 n-1，则漏了 i=0
for (int i = 0; i <= n-1; i++) ... // 正确但写法混乱；推荐 i < n

// DP 表格填充：注意递推是否访问了 i-1
// ❌ 如果 dp[i] 用到 dp[i-1]，而 i 从 0 开始，则 dp[-1] 未定义！
for (int i = 0; i <= n; i++) {
    dp[i] = dp[i-1] + ...;  // BUG：i=0 时访问 dp[-1]！
}

// ✅ 从 i=1 开始，或单独初始化 dp[0] 作为边界条件
dp[0] = BASE_CASE;
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i-1] + ...;  // 安全：dp[i-1] 始终有效
}

// ❌ 错误：dp 数组未初始化
int dp[1005][1005];  // 在 C++ 中包含垃圾值！
// dp[i][j] 可能因上一个测试用例或操作系统内存而非零

// ✅ 正确方式：
// 方式一：memset（按字节填充，用 0 或 0x3f 模拟正无穷）
memset(dp, 0, sizeof(dp));          // 全部置 0
memset(dp, 0x3f, sizeof(dp));       // 置为 ~1.06e9（适合用作 int 的"无穷大"）

// 方式二：vector 显式初始化
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

// 方式三：fill
fill(dp, dp + n, 0);

// ⚠️ 警告：memset(dp, -1, sizeof(dp)) 将每个字节置为 0xFF
// 对 int：0xFFFFFFFF = -1（可用于"未访问"标记）
// 对 long long：0xFFFFFFFFFFFFFFFF = -1（同样有效）
// 但 memset(dp, 1, sizeof(dp)) 得到 0x01010101 = 16843009，而不是 1！

// C++ 中全局数组默认初始化为零
// 局部（栈）数组则不会初始化

int globalArr[100005];     // ✅ 初始化为 0
int globalDP[1005][1005];  // ✅ 初始化为 0

int main() {
    int localArr[1000];    // ❌ 未初始化（含垃圾值）
    int localDP[100][100]; // ❌ 未初始化
    
    // 建议：将大数组声明为全局变量，既避免栈溢出又保证初始化
}

// C++ 默认栈大小通常为 1~8 MB
// 递归层数过深会超出限制 → 运行时错误（段错误）

// ❌ 危险：在深度为 10^5 的树上递归 DFS
void dfs(int u) { dfs(children[u]); }  // 长链场景下会栈溢出！

// ✅ 解法一：用显式栈改写为迭代
void dfs_iterative(int start) {
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        for (int v : children[u]) st.push(v);
    }
}

// ✅ 解法二：增大栈大小（平台相关，竞赛评测机通常允许）
// Linux 下编译并运行：ulimit -s unlimited && ./sol

// 经验法则：
// 递归深度 ≤ ~10^4：通常安全
// 递归深度 ~10^5：有风险，考虑迭代
// 递归深度 ~10^6：几乎必定栈溢出 → 必须用迭代

// 当题目要求输出 mod 10^9+7 时：
const int MOD = 1e9 + 7;

// ❌ 错误：忘记取模，long long 溢出
long long dp = 1;
for (int i = 0; i < n; i++) dp *= A[i];  // ~18 次大数乘法后溢出！

// ❌ 错误：减法下溢（结果为负的模）
long long ans = (a - b) % MOD;  // a < b 时，C++ 返回负数！

// ✅ 正确：减法取模前加上 MOD
long long ans = ((a - b) % MOD + MOD) % MOD;  // 保证非负

// ❌ 错误：DP 中忘记对中间值取模
dp[i][j] = dp[i-1][j] + dp[i][j-1];  // 迭代次数多时可能溢出

// ✅ 正确：每次加法后立即取模
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;

// ✅ 正确的模意义快速幂：
long long modpow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;  // ← 每次乘法后取模！
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// ❌ BFS：忘记在入队之前标记已访问
// 这会导致同一节点被处理多次！
queue<int> q;
q.push(src);
while (!q.empty()) {
    int u = q.front(); q.pop();
    visited[u] = true;  // ❌ 出队后才标记 → 同一节点可能多次入队
    for (int v : adj[u]) if (!visited[v]) q.push(v);
}

// ✅ 正确：入队时立即标记已访问
visited[src] = true;
queue<int> q;
q.push(src);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;  // ✅ 入队前标记
            q.push(v);
        }
    }
}

// ❌ DFS：多个测试用例之间忘记重置 visited
// 多测问题中，每次测试用例开始前必须重新初始化 visited[]！
memset(visited, false, sizeof(visited));

// ❌ Dijkstra：距离数组用 int 而非 long long
int dist[MAXN];  // ❌ 边权最大 10^9 时，累加后溢出！
long long dist[MAXN];  // ✅

// ❌ 错误：大量输入时未加 ios_base::sync_with_stdio(false)
// 不加此行，cin/cout 与 C 标准 I/O 同步 → 速度极慢！
// N = 10^6 的输入量下，可能是 AC 与 TLE 的差距。

// ✅ 每道竞赛题的 main() 开头都应加上：
ios_base::sync_with_stdio(false);
cin.tie(NULL);

// ❌ 错误：使用 endl（每行都刷新缓冲区 → 很慢）
for (int i = 0; i < n; i++) cout << ans[i] << endl;  // 慢！

// ✅ 正确：用 "\n" 代替
for (int i = 0; i < n; i++) cout << ans[i] << "\n";  // 快

// ❌ 错误：关闭同步后混用 cin 与 scanf/printf
ios_base::sync_with_stdio(false);
scanf("%d", &n);  // BUG：解除同步后混用 C 和 C++ I/O！

// ✅ 正确：选一种方式并坚持使用
// 要么只用 cin/cout，要么只用 scanf/printf

// USACO 文件 I/O（有时题目要求）：
freopen("problem.in", "r", stdin);
freopen("problem.out", "w", stdout);
// 加上这两行后，cin/cout 会自动读写文件

// 网格 BFS：边界检查差一错误
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// ❌ 错误（实际上下面这种写法是正确的——只是确保四个条件都写到）
for (int d = 0; d < 4; d++) {
    int nx = x + dx[d], ny = y + dy[d];
    if (nx >= 0 && ny >= 0 && nx < n && ny < m) // ✅ 这个边界检查是正确的！
    // 确保四个条件都写全
}

// ❌ 错误：弄混行列（转置了行和列）
// 若网格是 N 行 × M 列：
// A[row][col]：row 取值 0..N-1，col 取值 0..M-1
// 边界条件：row < N，col < M（不能写成 row < M！）

// ❌ 错误：多源 BFS 计算距离时，同一格子被多次访问（忘记距离检查）
if (!visited[nx][ny]) {  // ✅ 只访问未访问的格子
    visited[nx][ny] = true;
    dist[nx][ny] = dist[x][y] + 1;
    q.push({nx, ny});
}

// ❌ 错误：0/1 背包内层循环方向错了
// 必须从高到低遍历容量，防止物品被重复使用！
for (int i = 0; i < n; i++) {
    for (int j = W; j >= weight[i]; j--) {  // ✅ 从高到低
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
// 若从低到高遍历：
for (int j = weight[i]; j <= W; j++) {  // ❌ 从低到高 = 完全背包！
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}

// ❌ 错误：LIS 二分查找时混淆 upper_bound 与 lower_bound
// 严格递增 LIS：用 lower_bound（找第一个 >= x 的位置，替换）
// 非严格递减 LIS：用 upper_bound（找第一个 > x 的位置，替换）
auto it = lower_bound(tails.begin(), tails.end(), x);  // 严格递增
auto it = upper_bound(tails.begin(), tails.end(), x);  // 非严格递减

// ❌ 错误：忘记初始化边界条件
// dp[0] 或 dp[i][0] 或 dp[0][j] 必须在主循环之前显式赋值
dp[0][0] = 0;  // 始终初始化边界条件！

// 常见的 MLE 原因：

// ❌ 数组过大
int dp[10005][10005];  // = 10^8 个 int = 400MB → 超出典型的 256MB 限制！

// 计算方式：N × M × sizeof(类型) 字节
// int：4 字节，long long：8 字节
// 256MB = 256 × 10^6 字节
// int 数组最多约 6400 万个元素
// long long 数组最多约 3200 万个元素

// ✅ 一维 DP 的空间优化：
// 若 dp[i] 只依赖 dp[i-1]，使用滚动数组：
vector<long long> dp(2, 0);  // dp[cur] 和 dp[prev]
for (int i = 0; i < n; i++) {
    dp[1 - cur] = f(dp[cur]);  // 在 0 和 1 之间交替
    cur = 1 - cur;
}

// ✅ 二维 DP 的空间优化（背包类）：
// 若 dp[i][j] 只依赖 dp[i-1][...]，只保留两行
vector<int> prev_row(W+1, 0), curr_row(W+1, 0);