골프

commons.wikimedia.org의 이미지

Competitive Programming Association of Iceland의 회원들은 Code Golf 대회에 참가하기로 했다. 그들은 이 대회가 경쟁 프로그래밍 문제의 가장 짧은 풀이 코드를 작성하는 사람을 가리는 대회라고 생각했지만, 안타깝게도 그렇지 않았다! 이것은 프로그래머들을 위한 골프 대회였다! 이미 등록을 마쳤기 때문에 많은 회원이 그래도 참가하기로 했다. 하지만 프로그래밍 대회일 것이라고 예상했기 때문에 점수를 기록할 종이와 연필을 가져오지 않았다. 그러나 같은 이유로 노트북은 가져왔다. 해결책은 명확하다. 골프 점수를 관리하는 프로그램을 작성해야 한다!

모든 참가자는 파에서 시작하며, 각 홀에서 각 참가자의 타수는 파보다 많거나 적은 어떤 수이다. 파는 숙련된 골퍼가 홀을 마치는 데 필요할 것으로 설계자들이 추정하여 미리 정한 타수이다. 점수는 항상 파를 기준으로 비교되며 서로 합산된다. 즉, $0$은 파를 나타내며 참가자의 점수를 바꾸지 않는다. 양수는 파를 초과한 결과를 나타내므로, $2$은 파보다 두 타 많은 것을 나타내며 참가자의 점수를 $2$만큼 증가시킨다. 음수는 파보다 적은 결과를 나타내므로, $-3$은 파보다 세 타 적은 것을 나타내며 참가자의 점수를 $3$만큼 감소시킨다. 어떤 사람이 파보다 두 타 적고, 그다음에는 한 타 많으며, 마지막에는 파를 기록했다면 총점은 $-1$이다. 목표는 가능한 한 적은 타수를 기록하는 것이므로 점수가 낮을수록 좋다.

채점

그룹 | 점수 | 제한

1 | 20 | $1 \leq n, q \leq 100$, 모두 파이다.

2 | 20 | $n = 1$, $1 \leq q \leq 100$.

3 | 20 | $1 \leq n, q \leq 100$, 모든 ? 질의에서 동점이 없다.

4 | 30 | $1 \leq n, q \leq 100$.

5 | 10 | $1 \leq n, q \leq 100 \, 000$.

입력의 첫 줄에는 두 양의 정수 $n, q$가 주어진다. 여기서 $n$은 참가자 수이고 $q$는 질의 수이다. 그다음 줄에는 공백으로 구분된 참가자들의 이름 $n$개가 주어진다. 서로 다른 두 참가자가 같은 이름을 갖는 경우는 없다. 다음에는 $q$개의 질의가 각각 한 줄에 하나씩 주어진다. 각 질의는 ! 또는 ?로 시작한다. 줄이 ?로 시작하면 그 뒤에 참가자 한 명의 이름이 주어진다. 그러면 그 참가자의 순위와 파에서 얼마나 차이 나는지를 나타내는 두 수를 한 줄에 출력해야 한다. 줄이 !로 시작하면 해당 질의는 다음 홀의 결과를 제공한다. ! 뒤에는 파를 기록하지 않은 참가자 수를 나타내는 양의 정수 $k$가 주어진다. 그다음에는 서로 다른 참가자 이름 $k$개와 각 참가자의 점수가 주어진다. 예를 들어 ! 2 Atli 3 Arnar -3는 Arnar와 Atli를 제외한 모두가 파를 기록했고, Atli는 파보다 세 타 많았으며 Arnar는 파보다 세 타 적었다는 뜻이다.

모든 이름은 영문 대문자와 소문자로만 이루어진다. 각 이름은 최대 $20$개의 문자로 이루어진다. 입력에 포함된 문자의 총개수는 최대 $1 \, 000 \, 000$개이다. 입력의 모든 점수는 적어도 $-10^9$이고 최대 $10^9$이다.

입력에서 ?로 시작하는 각 줄에 대해 해당 참가자의 순위와 파에서 얼마나 차이 나는지를 출력한다. 같은 점수를 기록한 참가자가 둘 이상이라면, 그들은 모두 그들 가운데 가장 높은 순위인 것으로 간주한다. 예를 들어 두 번째 순위부터 다섯 번째 순위까지가 모두 같은 점수라면, 이들은 모두 두 번째 순위로 간주한다.