Mike and Fish

题意翻译

大家都知道,熊爱鱼。但是迈克是一只奇怪的熊,他讨厌鱼!更奇怪的是,他有无数的蓝色和红色的鱼。 他在平面上标出了$n$ 个不同的点。第$i$ 个是点$(x_i,y_i)$ 。他想在每一点都放一条鱼,使得每一条水平线或垂直线上的红鱼和蓝鱼的数量相差最多1。 他不能找到一种方式来执行,所以请你帮助他。 输入的第一行包含整数$n(1 \le n \le 2 \times 10^{5})$ 。 接下来的$n$ 行包含的每个点的信息,第$i$ 行包含两个整数$x_i$ 和$y_i$ ,($1 \le x_i,y_i \le 2 \times 10^{5}$ ),表示第$i$ 个点的坐标。 保证至少有一个符合题意的答案。 将答案输出为n个字符`r`(红色)或`b`(蓝色)的序列,其中第$i$ 个字符表示$i$ 点中的“鱼”的颜色。 Translated by @frankchenfu

题目描述

As everyone knows, bears love fish. But Mike is a strange bear; He hates fish! The even more strange thing about him is he has an infinite number of blue and red fish. ![](https://cdn.luogu.org/upload/vjudge_pic/CF547D/031dc6fdab66492c31079b30a48004c3918930a2.png)He has marked $ n $ distinct points in the plane. $ i $ -th point is point $ (x_{i},y_{i}) $ . He wants to put exactly one fish in each of these points such that the difference between the number of red fish and the blue fish on each horizontal or vertical line is at most 1. He can't find a way to perform that! Please help him.

输入输出格式

输入格式


The first line of input contains integer $ n $ ( $ 1<=n<=2×10^{5} $ ). The next $ n $ lines contain the information about the points, $ i $ -th line contains two integers $ x_{i} $ and $ y_{i} $ ( $ 1<=x_{i},y_{i}<=2×10^{5} $ ), the $ i $ -th point coordinates. It is guaranteed that there is at least one valid answer.

输出格式


Print the answer as a sequence of $ n $ characters 'r' (for red) or 'b' (for blue) where $ i $ -th character denotes the color of the fish in the $ i $ -th point.

输入输出样例

输入样例 #1

4
1 1
1 2
2 1
2 2

输出样例 #1

brrb

输入样例 #2

3
1 1
1 2
2 1

输出样例 #2

brr