407709: GYM102878 K Number Puzzle

K. Number Puzzletime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive problem!

Lancern is a cryptography master, he never uses name+birthday combination as his password, instead, he uses a randomly generated number. To avoid forgetting his password, he stores his password in a number puzzle, in which, there is a $$$n\times m$$$ jigsaw, but with $$$n \times m + 1$$$ pieces of blocks, each has a number on it, among them, $$$n \times m$$$ pieces can constitute the jigsaw, and the number on the extra piece is Lancern's password. Let's use $$$a_{i,j}$$$ to represent the number of the piece on the $$$ith$$$ row and $$$jth$$$ column of the jigsaw, it is satisfied:

• $$$a_{1,j} < a_{i,j}$$$, for all $$$i = 2, \dots, n$$$ and $$$j = 1, \dots, m$$$
• $$$a_{i,j} < a_{k,j+1}$$$, for all $$$i, k = 1, \dots, n$$$ and $$$j = 1, \dots, m - 1$$$

Today, Lancern forgets his password again, but he is too busy to solve this puzzle. He really needs the password, so could you help him to solve the puzzle?

At the beginning, you will be given $$$k = n \times m + 1$$$ distinct numbers, represent the jigsaw pieces. Each time, you can use one of the following queries to check:

• $$$r\ x\ y$$$: whether the piece with number $$$x$$$ and the piece with number $$$y$$$ is horizontally adjacency.
• $$$c\ x\ y$$$: whether the piece with number $$$x$$$ and the piece with number $$$y$$$ is vertically adjacency.
• $$$!\ x$$$: confirm $$$x$$$ is the password.

After each query, you can use

• fflush(stdout) in C/C++
• cout.flush() in C++
• System.out.flush() in Java

to flush the output stream.

For each "$$$r\ x\ y$$$" and "$$$c\ x\ y$$$" query, you will get a "yes" or "no" as input. The number of "$$$r\ x\ y$$$" and "$$$c\ x\ y$$$" queries you made can't exceed $$$2k$$$. After you confirm the answer using "$$$!\ x$$$" query, you have to terminate your program immediately after you flush the output stream.

Input

Use standard input to read the initial input and the responses to the queries.

The input contains an integer $$$k$$$ $$$\left(k = n \times m + 1, 2\le n\le m\le 100\right)$$$, and $$$k$$$ integers $$$a_i$$$ $$$\left(0\le a_i\le 10^9\right)$$$ at the begining, and reponses "yes" and "no" to your queries.

The testing system will allow you to read the response on the query only after your program print the query for the system and perform a flush operation.

Interaction

To make the queries your program must use standard output.

Your program must print the "$$$r\ x\ y$$$", "$$$c\ x\ y$$$" and "! x" queries, each query per line. After printing each line your program must perform operation flush.

Each $$$x$$$ and $$$y$$$ in your queries must exist in $$$a_i$$$ in the initial input.

ExampleInput

10
0 1 2 3 4 5 6 7 8 9

no

yes

yes

no

no

no

yes

yes

yes

yes

no

yes

Output

r 0 1

c 0 2

r 0 3

r 3 4

c 3 5

r 3 6

r 3 7

c 3 4

r 2 4

c 1 2

r 1 5

r 1 6

! 5

Note

In the example, the origin jigsaw is

$$$$$$ \begin{matrix} 0 & 3 & 7\\ 2 & 4 & 9\\ 1 & 6 & 8 \end{matrix} $$$$$$

The extra number is 5.