Это интерактивная задача.
Yui девочка, которая очень любит играть в маджонг.
У нее есть таинственный набор, который состоит из нескольких плиток (этот набор может быть пустым). Каждая плитка содержит целое число от \(1\) до \(n\) и не больше, чем \(n\) плиток в множестве имеют одинаковое значение. Таким образом, в множество содержит не больше, чем \(n^2\) плиток.
Вы хотите узнать, какие числа написаны на плитках в множестве. Для этого Yui хочет сыграть с вами в игру.
Давайте назовем множество, состоящее из трех плиток равной тройкой, если значения на плитках одинаковые. Например, \(\{2,\,2,\,2\}\) это равная тройка, а \(\{2,\,3,\,3\}\) нет.
Давайте назовем множество, состоящее из трех плиток последовательной тройкой, если значения на плитках последовательные целые числа. Например, \(\{2,\,3,\,4\}\) это последовательная тройка, а \(\{1,\,3,\,5\}\) нет.
Сначала, Yui называет вам количество подмножеств плиток, которые являются равными тройками и количество подмножеств плиток, которые являются последовательными тройками в ее множестве плиток. После этого, вы можете добавить плитку с целым числом от \(1\) до \(n\) в множество не более, чем \(n\) раз. Каждый раз добавляя плитку, в ответ вы получите количество подмножеств плиток в текущем множестве плиток, которые являются равными тройками и количество подмножеств плиток в текущем множестве плиток, которые являются последовательными тройками.
Обратите внимание, что любые две различные плитки с одинаковым значением считаются различными. Другими словами, в множестве \(\{1,\,1,\,2,\,2,\,3\}\) вы можете найти \(4\) подмножества \(\{1,\,2,\,3\}\).
Угадайте количество плиток в изначальном множестве с числом \(i\) для всех целых чисел \(i\) от \(1\) до \(n\).
Выходные данные
Когда ваша программа будет готова ответить, выведите строку в формате «! \(a_1\) \(a_2\) \(\ldots\) \(a_n\)» (\(0 \le a_i \le n\)), где \(a_i\) будет равно количеству плиток в изначальном множестве с числом \(i\).
Протокол взаимодействия
Для того, чтобы добавить плитку в множество, выведите строку в формате «+ \(x\)» (\(1 \le x \le n\)), где \(x\) равно числу, которое будет на плитке, которую вы добавляете. В ответ вы должны считать два целых числа, равных количеству подмножеств плиток, которые являются равными тройками и количеству подмножеств плиток, которые являются последовательными тройками в текущем множестве плиток.
После вывода строки с запросом добавления плитки или строки с ответом не забывайте сбрасывать буфер вывода. Иначе ваше решение получит вердикт Idleness limit exceeded.
Для того, чтобы сделать это, используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascall;
- stdout.flush() в Python;
- обратитесь к документации для остальных языков.
Вы получите вердикт Wrong answer, если вы добавите больше, чем \(n\) плиток в множество.
Взломы
Для того, чтобы сделать взлом, вы должны предоставить тест в следующем формате:
В первой строке находится единственное целое число \(n\) (\(4 \le n \le 100\)).
Во второй строке находится \(n\) целых чисел \(a_1,a_2,\ldots,a_n\) (\(0 \le a_i \le n\)) — \(a_i\) равно количеству плиток с числом \(i\) в множестве.
Примечание
В первом тесте, изначальное множество плиток \(\{1, 1, 2, 3, 3, 3, 5, 5\}\). Оно содержит одну равную тройку \(\{3, 3, 3\}\) и шесть последовательных троек, которые все равны \(\{1, 2, 3\}\). После добавления в множество плитки со значением \(1\) множество плиток станет \(\{1, 1, 1, 2, 3, 3, 3, 5, 5\}\) и будет содержать две равные тройки \(\{1, 1, 1\}\), \(\{3, 3, 3\}\) и девять последовательных троек, которые все равны \(\{1, 2, 3\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 6
2 9
5 12
5 24
6 24
|
+ 1
+ 1
+ 2
+ 5
! 2 1 3 0 2
|