题目描述

学校举办了一场足球乱斗比赛！共有 $2n$ 个班级，每个班级都派出了一支球队，从 $0$ 到 $2n - 1$ 编号。

现在就要进行最终决战了！决战有 $n$ 次比赛，第 $i$ 次是第 $a _ i$ 队和第 $b _ i$ 队比赛。保证每个队伍恰好进行一次比赛。而在决战之前，第 $i$ 个队伍已经有了 $p _ i$ 的积分。决赛中，一场比赛可能是平局也可能不是。如果不是平局，胜出者得 $3$ 分，失败者不得分；如果是平局，双方各得 $1$ 分。

比赛结束后，队伍按照积分排名。如果有多个队伍同分，那这些队伍的排名都是同分的最高排名。

现在请求出每个队伍能得到的最高排名是多少。

输入格式

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

第二行 $2n$ 个非负整数表示 $p _ 0, p _ 1, \cdots, p _ {2n - 1}$。

接下来 $n$ 行，第 $i$ 行两个非负整数表示 $a _ i$ 和 $b _ i$。

保证 $a _ i$ 和 $b _ i$ 不重不漏的覆盖了 $0, 1, \cdots, 2n - 1$。

输出格式

一行 $2n$ 个整数表示每个队伍的最高排名。

样例

样例输入 1

2
2 2 5 0 
3 2
1 0

样例输出 1

1 1 1 2 

样例输入/输出 2

见下发文件 football2.in/ans。该样例满足测试点 $3\sim 5$ 的限制。

样例输入/输出 3

见下发文件 football3.in/ans。该样例满足测试点 $10$ 的限制。

数据范围与提示

本题共 $10$ 个测试点，每个测试点 $10$ 分。

对于所有数据，$1 \le n \le 10 ^ 5$，$0 \le p _ i \le 5\times 10 ^ 5$。