C - Bank Accounts 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

コワスギ銀行の裏庭では、幽霊がカボチャを育てています。あなたはカボチャたちに銀行口座を開設してあげることにしました。

カボチャ用銀行口座には、開設時に名前と ID を 1 個ずつ割り当てます。ID の値を選ぶときは、まだ ID として使われていない正の整数のうち最小のものを採用します。

はじめ、カボチャ用銀行口座はひとつも開設されていません。以下の出来事が Q 回起きるので、順に処理してください。

  • カボチャがやってきて、名前 s を名乗る。
    • 名前 s が割り当てられた口座が存在する場合、その ID を出力する。
    • 名前 s が割り当てられた口座が存在しない場合、名前 s の口座を新規に 1 個開設し、その ID を出力する。

制約

  • Q は 1 以上 2 \times 10^5 以下の整数
  • 各出来事において、s は英小文字からなる長さ 1 以上 10 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

\mathrm{query}_i は i 回目の出来事を表し、以下の形式で与えられる。

s

出力

Q 行出力せよ。i 行目には、i 回目の出来事で出力するべき値を出力せよ。

入力例 1

8
pumpkin
hobak
pompoen
hobak
pumpkin
boga
boga
hobak

出力例 1

1
2
3
2
1
4
4
2

出来事は以下のように進みます。

  • 1 回目の出来事において、名前 pumpkin、ID 1 の口座を新規に開設する。
  • 2 回目の出来事において、名前 hobak、ID 2 の口座を新規に開設する。
  • 3 回目の出来事において、名前 pompoen、ID 3 の口座を新規に開設する。
  • 4 回目の出来事において、名前 hobak の口座は既にあり、その ID は 2 である。
  • 5 回目の出来事において、名前 pumpkin の口座は既にあり、その ID は 1 である。
  • 6 回目の出来事において、名前 boga、ID 4 の口座を新規に開設する。
  • 7 回目の出来事において、名前 boga の口座は既にあり、その ID は 4 である。
  • 8 回目の出来事において、名前 hobak の口座は既にあり、その ID は 2 である。

入力例 2

7
joayo
joayo
joayo
joayo
joayo
joayo
joayo

出力例 2

1
1
1
1
1
1
1

Score : 300 points

Problem Statement

In the backyard of Kowasugi Bank, ghosts are growing pumpkins. You have decided to open bank accounts for the pumpkins.

When a bank account for a pumpkin is opened, it is assigned one name and one ID. The ID is chosen as the smallest positive integer that is not yet used as an ID.

Initially, no bank accounts for pumpkins have been opened. The following event occurs Q times; process them in order.

  • A pumpkin comes and introduces itself with the name s.
    • If there is an account assigned the name s, print its ID.
    • If there is no account assigned the name s, open one new account with the name s and print its ID.

Constraints

  • Q is an integer between 1 and 2 \times 10^5, inclusive.
  • In each event, s is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

\mathrm{query}_i represents the i-th event and is given in the following format:

s

Output

Print Q lines. The i-th line should contain the value to be printed in the i-th event.

Sample Input 1

8
pumpkin
hobak
pompoen
hobak
pumpkin
boga
boga
hobak

Sample Output 1

1
2
3
2
1
4
4
2

The events proceed as follows.

  • In the 1-st event, a new account with the name pumpkin and ID 1 is opened.
  • In the 2-nd event, a new account with the name hobak and ID 2 is opened.
  • In the 3-rd event, a new account with the name pompoen and ID 3 is opened.
  • In the 4-th event, an account with the name hobak already exists, and its ID is 2.
  • In the 5-th event, an account with the name pumpkin already exists, and its ID is 1.
  • In the 6-th event, a new account with the name boga and ID 4 is opened.
  • In the 7-th event, an account with the name boga already exists, and its ID is 4.
  • In the 8-th event, an account with the name hobak already exists, and its ID is 2.

Sample Input 2

7
joayo
joayo
joayo
joayo
joayo
joayo
joayo

Sample Output 2

1
1
1
1
1
1
1