Problem Statement

This is an interactive task. Please note that these are not beginner questions.

If you are a beginner, try the AtCoder Beginners Selection!

There are N balls labeled with the first N uppercase letters. The balls have pairwise distinct weights.

You are allowed to ask at most Q queries. In each query, you can compare the weights of two balls (see Input/Output section for details).

Sort the balls in the ascending order of their weights.

Constraints

• (N, Q) = (26, 1000), (26, 100), or (5, 7).

Partial Score

There are three testsets. Each testset is worth 100 points.

• In testset 1, N = 26 and Q = 1000.
• In testset 2, N = 26 and Q = 100.
• In testset 3, N = 5 and Q = 7.

Input and Output

First, you are given N and Q from Standard Input in the following format:

N Q

Then, you start asking queries (at most Q times). Each query must be printed to Standard Output in the following format:

? c_1 c_2

Here each of c_1 and c_2 must be one of the first N uppercase letters, and c_1 and c_2 must be distinct.

Then, you are given the answer to the query from Standard Input in the following format:

ans

Here ans is either < or >. When ans is <, the ball c_2 is heavier than the ball c_1, and otherwise the ball c_1 is heavier than the ball c_2.

Finally, you must print the answer to Standard Output in the following format:

! ans

Here ans must be a string of length N, and it must contain each of the first N uppercase letters once. It must represent the weights of the balls in the ascending order.

Judgement

• After each output, you must flush Standard Output. Otherwise you may get TLE.
• After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
• When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA).

Sample Code

Here is a sample solution for 100 points. The code is obtainable for partial points, so submitting it will result in a WA.

#include <cstdio>
#include <string>

using namespace std;

int main(void){
  int N,Q,i,j;

  scanf("%d%d", &N, &Q);

  string s;
  for(i=0;i<N;i++) s += (char)('A' + i);

  for(i=0;i<N;i++) for(j=0;j<N-1;j++){
    printf("? %c %c\n", s[j], s[j+1]);
    fflush(stdout);
    char ans;
    scanf(" %c", &ans);
    if(ans == '>') swap(s[j], s[j+1]);
  }

  printf("! %s\n", s.c_str());
  fflush(stdout);

  return 0;
}

Sample

In this sample N = 3, Q = 10, and the answer is BAC.