Song Yong 可以非常快地解决任何数学问题。 他的兄弟 Choe Kwang 有 $N$ 个空珠宝店，可以存放昂贵的珠宝。 一天，Choe 从珠宝店带来了 $N$ 颗珠宝。 Choe 会将所有珠宝存放到店里，每家店只存一颗珠宝。 所有的珠宝都有 4 个数字：店号 $p$、到达该店的时间 $t$，以及另外 2 个特征值 $a$ 和 $b$。 我们将珠宝表示为 $(p, t, a, b)$。 当新珠宝 $(p, t, a, b)$ 到达时，Choe 必须为这颗新珠宝找到最匹配的珠宝。 最匹配的珠宝 $(p_1, t_1, a_1, b_1)$ 必须满足以下条件： 1. 它必须在新珠宝到达之前到达，即 $t_1 < t$。 2. 它的店号必须小于 $p$，即 $p_1 < p$。 3. “匹配效果”必须最大。“匹配效果”定义为 $a_1 * a + b_1 * b$。

Choe 愿意将珠宝的匹配效果写在对应商店的门上。 Choe 指示 Song Yong 计算并写下所有商店门上的数字。 请帮助 Song Yong。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 100000$)，表示珠宝店的数量。 接下来有 $N$ 行。 第 $p$ 行包含三个整数 $t, a, b$，表示这颗珠宝是 $(p, t, a, b)$。($1 \le t \le 1000000000, 1 \le a, b \le 1000000$) 保证没有两颗珠宝是同时到达的。

输出格式

输出 $N$ 个整数。 第 $p$ 个数字是写在第 $p$ 号门上的数字。

样例

输入 1

3
1 1 1
2 2 2
3 3 3

输出 1

0
4
12