50161. Memory Game

I'm a slow walker, but I never walk backwards.

Task Description

Let us play memory game. We are given a sequence of $N$ cards laid face down of values between 1 and 100. The cards are indexed form left ($0$) to right ($N - 1$). There will be $N$ turns for memory game. In the $i$-th turn, we will flip the $i$-th card face up. If the value of the card has appeared in a previous turn, then we flip the card of the same value and dispose of these two cards; if not, then we turn it face down and remember the value and its position in mind.

Now write a program to simulate memory game. For each turn, output the index of the card you will flip in a line, and if you turn up the second card of the same value, output the index of the second card and the value on the card.

The following image is when the sequence is $(1, 9, 5, 1, 8, 9, 8, 1, 9, 4, 5)$. You can see the result in sample output.

samplesample

Input Format

The first line contains a positive integer $N$. The second line contains $N$ integers between 1 and 100, which represent the numbers on the cards.

  • $0 \lt N \leq 10^{5}$

Output Format

There are $N$ lines in the output for $N$ turns. If we only flip one card in a turn, then output the index of the card. If we flip two cards of the same value, then output the two indice of the cards in the order you flip them, and the value of the card.

Subtask

  • 30 points: $N$ is no greater than $10^{3}$.
  • 70 points: $N$ is no greater than $10^{5}$.

Sample Input

11
1 9 5 1 8 9 8 1 9 4 5

Sample Output

0
1
2
3 0 1
4
5 1 9
6 4 8
7
8
9
10 2 5

Hint

Since the value of a card is between 1 and 100, you can use an array to remember what values you have seen, where they have appeared in the original sequence.

Discussion