该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

乐乐小朋友正在玩一个小球装箱的游戏。现有 N 个小球（编号为 1 到 N），每个小球有两种颜色之一（红色或绿色），且每个小球上标有一个数字。存在两个不同的球箱 A 和 B，乐乐需要将所有小球放入这两个球箱，并满足以下三个条件：

1. 每个球箱中球的数量相同（由于 N 为偶数，因此每个球箱各放 N/2 个小球）；
2. 球箱 A 中的任意一个球上的数字不小于球箱 B 中的任意一个球上的数字；
3. 若红色小球与绿色小球上的数字相同，则红色小球优先放入球箱 A（红色用 0 表示，绿色用 1 表示）。

装箱完成后，请求出球箱 A 和 B 中红色小球、绿色小球各自的数量。

输入格式

输入共 N+1 行：

• 第 1 行：一个整数 N（2 ≤ N ≤ 100000，保证 N 为偶数），表示小球总数；
• 第 2 到第 N+1 行：每行两个整数 Mi 和 Pi（1 ≤ Mi ≤ 20000，Pi 是 0 或 1），其中 Mi 是第 i 个小球上的数字，Pi 表示颜色（0 为红色，1 为绿色）。

输出格式

输出共 2 行：

• 第 1 行：两个整数，分别表示球箱 A 中红色小球、绿色小球的数量；
• 第 2 行：两个整数，分别表示球箱 B 中红色小球、绿色小球的数量。

样例输入1

6
1 1
3 0
2 1
4 1
6 0
5 0

样例输出1

2 1
1 2

样例输入2

8
2 1
2 0
2 0
4 1
2 0
5 1
8 1
1 1

样例输出2

1 3
2 2

样例解释

样例1解释

1. 排序过程：根据规则对小球排序（第一关键字：Mi 降序；第二关键字：Pi 升序，红色优先），排序后小球顺序为： (6, 0) → (5, 0) → (4, 1) → (3, 0) → (2, 1) → (1, 1)
2. 划分球箱：N=6，每个球箱放 3 个小球。取排序后前 3 个放入 A，剩余 3 个放入 B：
   • 球箱 A：(6,0)（红色）、(5,0)（红色）、(4,1)（绿色）→ 红色 2 个，绿色 1 个；
   • 球箱 B：(3,0)（红色）、(2,1)（绿色）、(1,1)（绿色）→ 红色 1 个，绿色 2 个。
3. 条件验证：A 中数字（6、5、4）均不小于 B 中数字（3、2、1），满足条件2；无相同数字的红绿球冲突，条件3自然满足。

样例2解释

1. 排序过程：按规则排序后小球顺序为： (8, 1) → (5, 1) → (4, 1) → (2, 0) → (2, 0) → (2, 0) → (2, 1) → (1, 1)
2. 划分球箱：N=8，每个球箱放 4 个小球。取排序后前 4 个放入 A，剩余 4 个放入 B：
   • 球箱 A：(8,1)（绿色）、(5,1)（绿色）、(4,1)（绿色）、(2,0)（红色）→ 红色 1 个，绿色 3 个；
   • 球箱 B：(2,0)（红色）、(2,0)（红色）、(2,1)（绿色）、(1,1)（绿色）→ 红色 2 个，绿色 2 个。
3. 条件3验证：数字为 2 的小球中，红色（Pi=0）优先进入 A，因此 A 含 1 个红色 2 号球，B 含 2 个红色 2 号球和 1 个绿色 2 号球，满足条件3。

数据范围