Description

给定平面上 $n$ 个具有整数坐标的点的集合，每个点都有一个对应的权重。

我们可以通过一个坐标为 $(x, y)$ 的点将平面划分为四个象限：在 $x + 0.5$ 处画一条垂直线，在 $y + 0.5$ 处画一条水平线。定义一个象限的权重为该象限内所有点的权重之和。进一步地，这种划分的不平衡度定义为四个象限权重中最大差值。

对于每个满足 $1 \leq x < n$ 的整数 $x$，求在垂直线 $x$ 上进行划分时可能的最小不平衡度。

Input Format

第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$)。

接下来的 $n$ 行，每行包含三个整数 $x_i$, $y_i$ 和 $w_i$ ($1 \leq x_i, y_i \leq n$, $1 \leq w_i \leq 10^9$) —— 分别表示第 $i$ 个点的横坐标、纵坐标和权重。

Output Format

输出仅一行，包含 $n - 1$ 个整数，依次表示每个 $x$ 对应的最小不平衡度。

4
3 2 5
4 4 2
1 4 4
2 2 1

6
4
6

Hint

• （$7$ 分）：$1 \leq n \leq 200$；
• （$17$ 分）：$1 \leq n \leq 5000$；
• （$53$ 分）：$1 \leq n \leq 100\,000$；
• （$23$ 分）：无额外限制。

翻译由 DeepSeek V3 完成