#P18246. Guessing Game

Guessing Game

Guessing Game

题目描述

Alice 和 Bobo 在玩一个猜数游戏,你担任裁判。

在第 kk 轮,你先把整数对 (ak,bk)(a_k,b_k) 写在黑板上,Alice 和 Bobo 都能看到黑板上的所有整数对。随后,你秘密选择一个整数 ii,满足 1≤i≤k1\le i\le k,把 aia_i 告诉 Alice,把 bib_i 告诉 Bobo。

两人从 Alice 开始轮流发言:如果能够确定对方拿到的数,就说出答案;否则承认自己不知道。最先正确猜出对方数的人获胜。

两人都非常聪明且诚实。对每个 kk,请分别求出:在 i=1,2,…,ki=1,2,\ldots,k 的所有选择中,有多少个 ii 会使 Alice 获胜,有多少个 ii 会使 Bobo 获胜。

有些选择可能使两人始终无法确定答案,因此这两个数量之和不一定等于 kk。

输入格式

第一行包含一个整数 qq,表示整数对的总数。

接下来 qq 行,第 kk 行包含两个整数 ak,bka_k,b_k。

输出格式

输出 qq 行。第 kk 行包含两个整数 Ak,BkA_k,B_k,分别表示在第 kk 轮中,使 Alice 获胜和使 Bobo 获胜的 ii 的数量。

数据范围

  • 1≤q≤1061\le q\le10^6。
  • 1≤ak,bk≤1051\le a_k,b_k\le10^5。
  • 输入的所有整数对 (a1,b1),…,(aq,bq)(a_1,b_1),\ldots,(a_q,b_q) 两两不同。

样例

4
1 1
1 2
2 1
2 2
1 0
0 2
1 2
0 0