Grafo das somas

Este problema é interativo. Se você nunca tiver visto um problema assim antes, cheque o guia de problemas interativos.

Existe uma permutação¹ escondida $p$ de tamanho $n$ e um grafo não-direcionado com $n$ vértices e, inicialmente, nenhuma aresta.

Dois tipos de operação podem ser feitas nesse grafo:

Escolha um $x$ inteiro tal que $2 \leq x \leq 2n$ . Para todo o par de vértices $(i, j)$ em que $i + j = x$ , será adicionada uma aresta.
Pergunte para o par $(i, j)$ , $1 \leq i, j \leq n$ , qual é o menor caminho em arestas entre os vértices $p_i$ e $p_j$ . Se não houver nenhum caminho entre $p_i$ e $p_j$ a resposta será $-1$ , caso contrário a resposta será a menor distância entre $p_i$ e $p_j$

Usando no máximo $2n$ operações (de ambos os tipos) descubra duas possíveis permutações $p$ , a sua resposta será considerada correta se ao menos uma das suas duas respostas for a permutação certa. É permitido responder duas permutações iguais.

1 - Uma permutação de tamanho $n$ é um vetor de tamanho $n$ que contém os números de $1$ a $n$ em uma ordem arbitrária. Por exemplo, os vetores $[1, 2, 3, 4]$ e $[5, 3, 1, 2, 4]$ são permutações (de tamanho $4$ e $5$ , respectivamente) porém os vetores $[1, 2, 2]$ e $[2, 3, 4, 5]$ não são permutações.

Entrada

A primeira linha contém um inteiro $t$ ( $1 \leq t \leq 100$ ) que indica a quantidade de casos de teste.

A primeira linha de cada caso de teste apresenta um inteiro $n$ ( $2 \leq n \leq 10^3$ ), o tamanho da permutação e quantidade de vérices do grafo.

É garantido que a soma dos $n$ de todos os casos de teste não excede $10^3$

Interação

A interação para cada caso começa ao ler o inteiro $n$ .

Depois, faça no máximo $2n$ operações:

Para fazer uma operação do tipo 1, imprima "+ $x$ " (sem as aspas). Então leia um inteiro $1$ ou $-2$ . Se o inteiro lido for $1$ , a sua operação foi válida, caso contrário seu código deve terminar a execução imediatamente para receber o veredito de Resposta Errada.
Para fazer uma operação de tipo 2, imprima "? $i$ $j$ " (também sem as aspas). Em seguida, leia a resposta da operação. Caso a resposta lida tenha $-2$ , o seu código fez uma operação inválida ou ultrapassou o limite de operações e, portanto, deve a execução deve cessar de imediato para receber Resposta Errada.

Para responder quais são as permutações, imprima "! $p_{1,1}$ $p_{1,2}$ ... $p_{1,n}$ $p_{2,1}$ $p_{2,2}$ ... $p_{2,n}$ " (de novo, sem as aspas), os dois vetores imprimidos devem ser permutações, mesmo que a primeira permutação esteja correta. Seu código deve então ler um inteiro $1$ ou $-2$ , se o inteiro for $-2$ , a resposta estava errada e o seu código deve retornar para receber o veredito Resposta Errada. Senão, a resposta estava correta e seu código deve seguir para o próximo caso de teste. Responder as permutações não conta como uma operação.

Exemplo

Para submeter sua solução use esse link