006 - 友人管理

問題文

花子さんにはn人の友達がいる。

花子さんは友達があまりに多いために友達にそれぞれ固有のIDと友達ランクをつけて管理している。

しかし、IDと友達ランクのリストにうっかりコーヒーをこぼしてしまった。

あなたには、花子さんの記憶から友達リストを復元してほしい。

また、花子さんが友達について思い出す手がかりになるかもしれないので彼女の質問にはできるだけ答えてほしい。

入力と出力

入力は標準入力から受け取り、出力は標準出力へ出力すること。

n
query1
  ...
  ...
"quit"

1行目に花子さんの友達の数nが与えられる。

その後、花子さんから思い出した情報や質問がクエリという形で与えられる。

入力の終わりは"quit"で示す。

クエリの形式は以下のとおりである。

remember a b

クエリが"remember"という文字列で始まるなら、花子さんがID a の友達ランクが b だと思い出したことを示す。

ID a

クエリが"ID"という文字列で始まるなら、花子さんがID a の友達ランクを尋ねていることを示す。

このクエリが与えられた場合、該当する友達のランクを1行に出力せよ。

質問時点でそのような友達がリストに無い場合、"unknown"と出力せよ。

rank b

クエリが"rank"という文字列で始まるなら、花子さんが友達ランク b のIDを尋ねていることを示す。

このクエリが与えられた場合、該当する友達のIDを1行に出力せよ。

質問時点でそのような友達がリストに無い場合、"unknown"と出力せよ。

制約

• 1 ≦ n ≦ 10⁶
• 1 ≦ a ≦ n
• 1 ≦ b ≦ n
• 他の友達と同じIDまたはランクを持つ友達は存在しない。
• 入力される値はすべて整数である。

クエリは最大で10⁴回与えられる。

入出力例

入力例1

5
ID 1
remember 1 2
ID 1
quit

出力例1

unknown
2

最初、ID 1 の友達のランクを聞かれているが、この時点でリストに無いので"unknown"を出力している

その後、花子さんがID 1 のランクが2であることを思い出したので、次に同じ質問をされたときには"2"を出力している。

入力例2

5
remember 2 5
remember 5 1
remember 3 2
rank 2
rank 3
ID 3
ID 2
remember 4 3
ID 4
quit

出力例2

3
unknown
2
5
3