G. The Lost Graph
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Student Vladislav is taking programming exam. He hasn't prepared properly and had a bad luck to get a question about some complicated graph algorithm that will be definitely useless for him for the rest of his life. He quickly asked his groupmate a cheatsheet and discovered the following pseudocode there:


function dfs(v)
begin
    visited[v] := true
    print("in " + v)
    for k := 1 : n do
    begin
        if adjacent(v, k) and not visited[k] do
        begin
            dfs(k)
        end
    end
    print("out " + v)
end

Vladislav manually executed the algorithm on the connected undirected graph just drawn by him. Unfortunately, he was very nervous and ate the piece of paper where this graph was drawn, but he has to show the graph to his teacher. Help Vladislav to restore the graph. It must be done as soon as possible, so the restored graph should contain the minimal possible number of edges.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of vertices in the graph.

It's followed by the execution result of the algorithm completely useless for Vladislav. It consists of 2n lines «in x» or «out x» where x is the number of vertex (1 ≤ x ≤ n).

It's guaranteed that all vertices from 1 to n exist in the graph, and that the input really specifies the execution result of the algorithm on some existing graph.

Output

Output (n - 1) lines, two numbers on each line — the numbers of vertices connected by edges. You can output the pairs of vertices and the vertices in pairs in any order.

Examples
Input
2
in 1
in 2
out 2
out 1
Output
1 2
Input
4
in 4
in 2
out 2
in 3
in 1
out 1
out 3
out 4
Output
1 3
2 4
3 4