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. 

He has marked *n* distinct points in the plane. *i*-th point is point (*x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub>). 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<sup class="upper-index">5</sup>).

The next *n* lines contain the information about the points, *i*-th line contains two integers *x*<sub class="lower-index">*i*</sub> and *y*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> ≤ 2 × 10<sup class="upper-index">5</sup>), the *i*-th point coordinates.

It is guaranteed that there is at least one valid answer.
def EdmondKarp(caps):
    while (find_augmenting_path(caps)):
        continue

from queue import Queue
def find_augmenting_path(caps):
    added = {}
    parents = {}
    #we do bfs
    q =  Queue()
    q.put(NEW_SOURCE)
    added[NEW_SOURCE] = True
    
    while(!q.not_empty()):
        current = q.get()
        if neighbour == NEW_SINK:
                    break
                
        for neighbour in caps[current]:
            if neighbour not in visited:
                if caps[current][neighbour] > 0:
                    q.put(neighbour)
                    parents[neighbour] = current
                    added[neighbour] = True
        
    if NEW_SINK not in parents:
        return 0
    else:
        current = NEW_SINK
        path = [currnet]
        while(current!=NEW_SOURCE):
            current = parents[current]
            path.append(current)
        
        path[::-1]
        min_on_path = min([caps[path[i]][path[i+1]] for i in range(0,len(path)-1)])
        for i in range(len(path)-1):
            caps[path[i]][path[i+1]] -= min_on_path
            caps[path[i+1]][path[i]] += min_on_path
            
        return min_on_path
        
MAX = 2 * 10 ** 5
SOURCE = 2 * 10 ** 5 + 1
SINK = - SOURCE
NEW_SOURCE = 2 * 10 ** 5 + 2
NEW_SINK = -NEW_SOURCE

from collections import defaultdict

n = int(input())

edges = []
capacities = defaultdict(lambda: defaultdict(int))
count = defaultdict(int)

for _ in range(n):
    u, v = list(map(int, input().split()))
    capacities[u][-v] = 1
    capacities[-v][u] = 0
    count[u] += 1
    count[-v] += 1
    edges.append((u, -v))

    capacities[SOURCE][u] = 0
    capacities[-v][SINK] = 0

for u in capacities:
    if u == SOURCE or u == SINK :
        continue
    if u > 0:
        # we are talking about the left part of the bipartite graph
        capacities[SOURCE][u] = (int(count[u] / 2), int((count[u] + 1) / 2))
    else:
        # right part nodes of the bipartite graph
        capacities[u][SINK] = (int(count[u] / 2), int((count[u] + 1) / 2))

        # Now we transform the graph to remove the lowerbounds

demands = defaultdict(int)

"""
#Step 1: For each edge with non zero lower bound add two new edge (S',v) and (u,T') with only upper bound (which is equal to the lower bound)
for u in capacities:
        if u<MAX:
            capacities[NEW_SOURCE][u] = capacities[SOURCE][u][0]
        else:
            capacities[u][NEW_SINK] = capacities[u][SINK][0]
"""

# Step 2: For each edge (u,v) with non zero lower bound :
#         1) remove the lower bound
#         2) replace upper bound with c′((u,v))=c((u,v))−d((u,v))
for u in capacities:
    if u == SOURCE or u == SINK:
        continue
    if u > 0:
        demands[SOURCE] += capacities[SOURCE][u][0]
        demands[u] -= capacities[SOURCE][u][0]
        capacities[SOURCE][u] = capacities[SOURCE][u][1] - capacities[SOURCE][u][0]
    else:
        demands[u] += capacities[u][SINK][0]
        demands[SINK] -= capacities[u][SINK][0]
        capacities[u][SINK] = capacities[u][SINK][1] - capacities[u][SINK][0]

# Step 3: Connect every supply node with the new source and every demand node with the new sink
for u in demands:
    if demands[u] < 0:
        capacities[NEW_SOURCE][u] = -demands[u]
    if demands[u] > 0:
        capacities[u][NEW_SINK] = demands[u]

# Step 4 : Add infinite capacity edge from T to S
capacities[SINK][SOURCE] = 2 ** 32

# Step 5 : compute max flow on transformed graph
FordFulkerson(capacities)

# Step 6 check if all the capacities of the NEW_SOURCE are 0
valid = all([capacities[NEW_SOURCE][v] == 0 for v in capacities[NEW_SOURCE]])

if valid:
    print("".join(["r" if capacities[u][v] == 0 else "b" for u, v in edges]))
else:
    print("This should never happen since we now there is one answer")