547_D. Mike and Fish
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. 

<image>

He has marked n distinct points in the plane. i-th point is point (xi, yi). 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.

Input

The first line of input contains integer n (1 ≤ n ≤ 2 × 105).

The next n lines contain the information about the points, i-th line contains two integers xi and yi (1 ≤ xi, yi ≤ 2 × 105), the i-th point coordinates.

It is guaranteed that there is at least one valid answer.

Output

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.

Examples

Input

4
1 1
1 2
2 1
2 2


Output

brrb


Input

3
1 1
1 2
2 1


Output

brr
```python
n = int(input())
edges = []
from collections import defaultdict

edges_dico = {}
count = defaultdict(int)
graph = defaultdict(lambda: defaultdict(int))
edges = []
for _ in range(n):
    u, v = map(int, input().split())
    count[u] += 1
    count[-v] += 1
    graph[u][-v] = 1
    graph[-v][u] = 1
    edges.append((u, -v))
    edges_dico[(u, -v)] = True

# we need to transform the graph to do find an eulerian circuit
odds = []
for u in count:
    if count[u] % 2 == 1:
        odds.append(u)

A = 2 * 10 ** 6 + 1
B = 2 * 10 ** 6 + 2
for u in odds:
    if u > 0:
        graph[A][u] = 1
        graph[u][A] = 1
        count[A] += 1
    else:
        graph[B][u] = 1
        graph[u][B] = 1
        count[B] += 1

if count[A] % 2 == 1:
    graph[A][B] = 1
    graph[B][A] = 1

# Now we do kind of hierholtzer...
i = 0
import sys

count_deleted = 0
j = 0
nodes = graph.keys()
for u in nodes:
    current = u
    color = "r"
    while True:
        color = "b" if color == "r" else "r"
        end = True
        edge_to_delete = None
        for neighbour in graph[current]:
            if graph[current][neighbour] == 1:
                edge_to_delete = (current, neighbour)
                if (neighbour, current) in edges_dico:
                    edges_dico[(neighbour, current)] = color
                if (current, neighbour) in edges_dico:
                    edges_dico[(current, neighbour)] = color

                count_deleted += 1
                current = neighbour
                end = False
                break
        if end:
            break
        else:
            u, v = edge_to_delete
            del graph[u][v]
            del graph[v][u]
print("".join([edges_dico[edge] for edge in edges]))
```