Italian brainrot

캐릭터들 사이에 아무 전체 순서를 하나 정한다. 예를 들어 입력으로 주어진 순서가 앞선 캐릭터가 항상 이긴다고 정하자.

그러면 캐릭터 $B$가 캐릭터 $A$를 이겼다는 것은 $B$가 $A$보다 입력에서 앞에 있다는 뜻이다. 또한 캐릭터 $C$가 캐릭터 $B$를 이겼다면 $C$는 $B$보다 입력에서 앞에 있다. 따라서 $C$는 $A$보다도 입력에서 앞에 있으므로, $C$는 $A$를 이긴다.

즉 입력 순서대로 앞선 캐릭터를 출력하면 항상 조건을 만족한다.

각 이름에 입력 순서 번호를 저장해 두고, 각 질의마다 번호가 작은 이름을 출력하면 된다. 같은 이름이 두 번 주어졌다면 그 이름을 출력한다.

시간 복잡도는 $O(L + Q)$이다. 여기서 $L$은 입력으로 주어진 캐릭터 이름 길이의 합이다.