题目描述

圆滑博士放假了，他打算坐火车出去旅游。

一列火车有 $n$ 节车箱，第 $i$ 节车箱有一种颜色 $col_i$ 。圆滑博士想知道，对于每一节车箱 $x$，有多少对 $(i,j)$ 满足 $i<x$ 且 $j>x$ 且 $col_i=col_j$。且圆滑博士还有另一个对颜色范围的约束，要求 $l_x\leq col_i\leq r_x$。

输入格式

第一行一个正整数 $n(1\leq n\leq 5\times 10^5)$。

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

输出格式

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

样例

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

0 3 4 3 0 

数据范围

对于 $50\%$ 的数据，$n\leq 5000$。

对于 $100\%$ 的数据，满足输入中的约束。