Alice 和 Bobo 正在进行一场引人入胜的游戏，而你有幸担任裁判。

在第 $k$ 轮中，你会在黑板上写下一对整数 $(a_k, b_k)$，Alice 和 Bobo 都能清楚地看到。一旦他们看到这些数字，你将秘密选择一个整数 $1 \le i \le k$，并将 $a_i$ 给 Alice，将 $b_i$ 给 Bobo。游戏由 Alice 先手，Alice 和 Bobo 轮流进行，他们可以选择声称自己知道对方的数字，或者承认自己不知道答案。第一个正确猜出对方数字的玩家将赢得游戏！

两位玩家都极其聪明且诚实，这使得游戏更加扣人心弦。当你观察他们的互动时，不禁会想：在第 $k$ 轮中，有多少个 $i$ 的取值使得 Alice 获胜，又有多少个 $i$ 的取值使得 Bobo 获胜？

第一行包含一个整数 $q$ ($1 \le q \le 10^6$)，表示整数对的总数。 接下来的 $q$ 行，每行包含一对整数 $(a_k, b_k)$ ($1 \le a_k, b_k \le 10^5$)。 保证 $(a_1, b_1), (a_2, b_2), \dots, (a_q, b_q)$ 两两不同。

输出 $q$ 行。在第 $k$ 行，输出两个整数 $A_k$ 和 $B_k$，分别表示在第 $k$ 轮中 Alice 获胜的 $i$ 的个数和 Bobo 获胜的 $i$ 的个数。

样例

输入格式 1

4
1 1
1 2
2 1
2 2

输出格式 1

1 0
0 2
1 2
0 0