D. Where were you 14 years ago?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

After the war in T-Land ended, the people were divided into three groups:

  • The fighters who liberated the country, called Thowwar, denoted by the letter T.
  • The supporters of the previous regime despite all of its crimes, called Floul, denoted by the letter F.
  • People with no opinion or clear identity, called Mkaw3, denoted by the letter M.

There are $$$n$$$ people in the waiting room. Your task is to determine the type of every person.

Fortunately, you can ask Abu Dujana for help. He is able to identify people's apparent identities by simply looking at them.

You may perform the following operation any number of times:

  • Choose exactly $$$k$$$ ($$$2 \le k \le n$$$) people and send them into Abu Dujana's inspection room.
  • Their behavior is as follows:
    • Every Thowwar remains a Thowwar.
    • Every Floul remains a Floul.
    • If a Mkaw3 does not find any Thowwar inside the room, they feel safe and return to their original nature as a Floul.
    • Otherwise, if there is at least one Thowwar in the room, every Mkaw3 immediately starts singing "Labat Labat" and successfully fools Abu Dujana into thinking they are a Thowwar.

Formally, let the chosen group contain $$$T$$$ Thowwar, $$$F$$$ Floul, and $$$M$$$ Mkaw3. Abu Dujana returns a single integer:

  • If $$$T = 0$$$, Abu Dujana returns $$$0$$$.
  • Otherwise, Abu Dujana returns $$$T + M$$$.

Determine the type of every person while using at most 812 operations (in honor of 8/12, T-Land Liberation Day).

It is guaranteed that among the $$$n$$$ people there is at least one Thowwar, at least one Floul and at least one Mkaw3.

Input

The first line contains a single integer $$$n$$$ ($$$3 \le n \le 400$$$) — the number of people.

Interaction

The first line of the input contains a single integer $$$n$$$ ($$$3 \le n \le 400$$$) — the number of people.

To ask a query, print a line in the following format:


? k i1 i2 ... ik

where $$$2 \le k \le n$$$, all indices are distinct, and $$$1 \le i_j \le n$$$.

After printing a query, flush the output and read a single integer $$$x$$$.

Suppose the chosen group contains:

  • $$$T$$$ Thowwar,
  • $$$F$$$ Floul,
  • $$$M$$$ Mkaw3een.

The interactor responds as follows:

  • If $$$T = 0$$$, it returns $$$0$$$.
  • Otherwise, it returns $$$T + M$$$.

You may ask at most 812 queries.

When you have determined the type of every person, print


! s

where $$$s$$$ is a string of length $$$n$$$, and the $$$i$$$-th character is:

  • T if the $$$i$$$-th person is a Thowwar;
  • F if the $$$i$$$-th person is a Floul;
  • M if the $$$i$$$-th person is a Mkaw3.

After printing the answer, terminate your program immediately.

Your program will receive the verdict Wrong Answer if it asks more than $$$812$$$ queries or prints an invalid query.

Remember to flush the output after every query. For example, use:

  • fflush(stdout) in C/C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python;
  • flush(output) in Pascal.
Example
Input
5
FMTMF

3	

0

0

1
Output
? 5 1 2 3 4 5

? 3 1 2 5
	
? 2 1 5
	
? 2 3 5
	
! FMTMF
Note

In the sample, there are $$$n = 5$$$ people. The hidden identities are FMTMF (Persons $$$1$$$ and $$$5$$$ are Floul, Persons $$$2$$$ and $$$4$$$ are Mkaw3, and Person $$$3$$$ is Thowwar).

The interaction proceeds as follows:

  • Query 1 (? 5 1 2 3 4 5): You send everyone to the room. The group contains $$$1$$$ Thowwar (Person $$$3$$$), $$$2$$$ Floul (Persons $$$1$$$ and $$$5$$$), and $$$2$$$ Mkaw3 (Persons $$$2$$$ and $$$4$$$). Because there is at least one Thowwar present ($$$T = 1$$$), the Mkaw3 people act like Thowwar. Abu Dujana returns $$$T + M = 1 + 2 = 3$$$.
  • Query 2 (? 3 1 2 5): You send persons $$$1$$$, $$$2$$$, and $$$5$$$ to the room. The group contains $$$2$$$ Floul and $$$1$$$ Mkaw3. Since there are absolutely no Thowwar present ($$$T = 0$$$), the Mkaw3 person feels safe and acts like a Floul. Abu Dujana returns $$$0$$$.
  • Query 3 (? 2 1 5): You send persons $$$1$$$ and $$$5$$$. Both are Floul ($$$T = 0$$$). Abu Dujana returns $$$0$$$.
  • Query 4 (? 2 3 5): You send persons $$$3$$$ and $$$5$$$. The group contains $$$1$$$ Thowwar and $$$1$$$ Floul. There are no Mkaw3 ($$$M = 0$$$). Abu Dujana returns $$$T + M = 1 + 0 = 1$$$.
  • Final Answer (! FMTMF): Having deduced the correct types, you print the final string.