你正在管理“Squash It”精英壁球俱乐部。俱乐部里有 $n$ 名球员，第 $i$ 名球员的俱乐部评分为 $r_i$，愉悦度为 $p_i$。

你计划以其中一名球员为领队，邀请其他几名评分较低的球员作为学员，进行一场专属训练。我们将即将到来的日子编号，明天为第 1 天，后天为第 2 天，以此类推。在得知你的计划后，每位球员都提供了一个日期区间 $[a_i, b_i]$，表示他只能在第 $a_i$ 天到第 $b_i$ 天（含）之间的某一天参加训练。

你不仅希望训练对参与者有益，还希望它尽可能令人愉快。当然，直接告诉某人因为他不够“令人愉快”而不邀请他会显得太刻薄。因此，你可以设定一个邀请者的评分上限，宣布本次训练专为低评分球员设计。

对于每一名球员 $i$，你希望找到一种组织训练的方式，使得受邀球员的总愉悦度尽可能高。你可以选择 $a_i$ 到 $b_i$ 之间的任意一天，以及任意一个低于 $r_i$ 的评分上限。然后，你会邀请所有能在选定日期参加训练且评分不超过所选上限的球员（当然，第 $i$ 名球员本人也会被邀请）。注意，你甚至可以将评分上限设为 0 —— 在这种情况下，除了领队外没有人会被邀请，但有时这可能比邀请那个粗鲁的家伙更令人愉快。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示“Squash It”俱乐部的球员人数。接下来的 $n$ 行中，每一行包含四个整数 $r_i, p_i, a_i$ 和 $b_i$ ($1 \le r_i \le 10^6$; $-10^6 \le p_i \le 10^6$; $1 \le a_i \le b_i \le 10^6$)，分别表示第 $i$ 名球员的俱乐部评分、愉悦度以及可参加训练的日期区间。

所有球员的评分互不相同。

输出格式

对于输入中的每一名球员，按输入顺序输出一行，包含当该球员被选为领队时，受邀球员可能获得的最大总愉悦度。

样例

输入 1

4
15 22 2 5
13 -7 5 8
9 -5 3 7
12 13 5 6

输出 1

30
1
-5
13

说明

在样例测试用例中，如果训练在第 5 天举行，由第一名球员担任领队，并邀请所有评分不超过 12 的球员，那么第一、第三和第四名球员将收到邀请，从而获得 30 的总愉悦度。