Migrated from Lutece 1634 记得小苹初见，两重心字罗衣

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

二维平面上有$n$个点.
你需要将每个点染成红色或蓝色.
请设计一种染色方案能够使得每一行和每一列的红色的点的数量与蓝色的点的数量之差都不超过$1$.

Input

第一行一个整数$n\left (1 \leq n \leq 200000 \right )$,表示有$n$个点.
接下来$n$行，每行两个整数$x,y\left (1 \leq x,y \leq 200000 \right )$,表示第$i$个点的坐标. 保证输入至少存在一个可行解.

Output

输出一行，一共$n$个字母，第$i$个字母表示第$i$个点的颜色. 如果是红色，输出字母$r$;如果是蓝色，输出字母$b$.

Samples

3
1 1
1 2
2 1

brr

Resources

2017 UESTC Training for Graph Theory