题目描述

MJZ 是一名喜欢旅游的同学，在来到驻马店王国时，坐上了颜色多样的火车。

MJZ 同学在车上，车上有 $n$ 个车厢，每一个车厢有一种颜色。

他想知道对于每一个正整数 $x \in [1,\ n]$ ，集合 $\{ (i,\ x,\ j)\ |\ i < x < j,\ l_x \le col_i = col_j \le r_x \}$ 中包含多少个元素。

换句话说，就是要求每一个车厢两边有多少对颜色相同的车厢，并且这一对车厢的颜色要在 $l_x$ 到 $r_x$ 之间。其中 $col_i$ 代表 $i$ 号车厢的颜色， $l_x,\ r_x$ 代表颜色的限制。

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个三元组，每个三元组包括三个正整数 $(col_i,\ l_i,\ r_i)$ ，输入中没有括号，这 $3n$ 个正整数之间均只用空格隔开，详见样例。

输出格式

输出一行 $n$ 个非负整数代表答案。

样例

样例输入

5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

样例输出

0 3 4 3 0

数据范围与提示

$1 \le n \le 5 \cdot 10^5$

$1 \le col_i,\ l_i,\ r_i \le 5 \cdot 10^5$