Учёный с мировым именем Иннокентий создал n ядерных микросхем. Однако некоторые из них оказались неисправными, и он забыл, какие именно. К счастью, неисправных микросхем было строго менее половины, и теперь учёный хочет выяснить, какие же из микросхем исправны, а какие нет.

Учёный может соединить две микросхемы друг с другом, и тогда каждая из них скажет, исправна ли другая. Исправная микросхема всегда даёт верный ответ, а неисправная может дать любой ответ. Неисправные микросхемы могут давать различные ответы для одних и тех же проверок. Вам надо помочь учёному узнать, какие из микросхем исправны, причём сделать это побыстрее, ведь микросхемы всё же ядерные, и если учёный не уложится в 4n проверок, радиоактивное излучение нанесёт ему непоправимый урон.

Это интерактивная задача. Ваша программа должна общаться с программой жюри, используя для этого стандартные потоки ввода и вывода.

В самом начале вашей программе сообщается единственное число n (1 ≤ n ≤ 5000) — количество микросхем.

После этого вы можете совершить не более 4n проверок. Для этого выведите символ «?» и два различных целых числа — номера микросхем a и b, которые вы хотите соединить и проверить. Микросхемы нумеруются с единицы.

В ответ на такой запрос вам будут сообщены два символа, каждый из которых равен «+» или «-». Первый символ — это вывод микросхемы a о состоянии микросхемы b, а второй символ — вывод микросхемы b о состоянии микросхемы a. Символ «+» означает, что микросхема исправна, а «-» — что неисправна.

Как только вы определите состояния всех микросхем, выведите символ «!», затем целое число k — количество исправных микросхем, а затем k различных чисел — их номера. После этого ваша программа должна завершиться.