← 返回题目列表

Codeforces · 547/D

D. 迈克和鱼

中文机器翻译题面 查看原题

众所周知,熊喜欢鱼。但迈克是一只奇怪的熊;他讨厌鱼!更奇怪的是他有无数条蓝色和红色的鱼。

他在平面上标记了 n 个不同的点。第 i 个点是点 (xi, yi)。他想在每个点中恰好放置一条鱼,使得每条水平或垂直线上的红色鱼和蓝色鱼的数量之差最多为 1。

他找不到执行此操作的方法!请帮助他。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 2 × 105)。

接下来n行包含点的信息,第i行包含两个整数xi和yi(1≤xi,yi≤2×105),第i个点的坐标。

保证至少有一个有效答案。

输出

将答案打印为 n 个字符“r”(表示红色)或“b”(表示蓝色)的序列,其中第 i 个字符表示第 i 个点中鱼的颜色。

示例

输入 #1

4
1 1
1 2
2 1
2 2

输出 #1

brrb

输入 #2

3
1 1
1 2
2 1

输出 #2

brr