XOR

Это интерактивная задача.

Жюри спрятало двоичную последовательность длины n. Вам известна только длина n.

Ваша задача — разделить эту двоичную последовательность на два подмножества так, чтобы в каждом было одинаковое количество единиц.

Вы можете использовать следующие три типа запросов:

1 i (1 ≤ i ≤ n) — выполнить операцию xor над i-м битом (можно сделать до 777 таких запросов).

2 — запросить количество единиц в последовательности (можно сделать только один такой запрос).

3 — вывести ответ (см. раздел вывода).

Ввод

Первая строка содержит одно целое число n (1 ≤ n ≤ 777) — длина скрытой двоичной последовательности. Сначала вы должны прочитать это число.

Вывод

Когда ваша программа будет готова вывести ответ, выведите две строки.

В первой строке напечатайте 3.

Во второй строке выведите n целых чисел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 2), где a[i] = 1, если i-й бит принадлежит первому подмножеству, и a[i] = 2, если второму.

После вывода ответа ваша программа должна завершиться.