Алиса и Боб стали королями в королевствах на множестве натуральных чисел. Подданными Алисы являются все натуральные числа, которые делятся на 3 без остатка, а все остальные числа стали подданными Боба. Алиса дружит с Бобом, и они хотят, чтобы их подданные тоже дружили между собой. Они разбили все числа на пары, причем ii-тое по порядку число из королевства Алисы будет дружить с ii-тым по порядку числом из королевства Боба. Вам задан набор из nn чисел. Напишите программу для нахождения друга каждого из чисел. Первые 10 чисел из королевства Алисы — это \{3,6,9,12,15,18,21,24,27,30,\ldots\}{3,6,9,12,15,18,21,24,27,30,…} Первые 10 чисел из королевства Боба —это \{1,2,4,5,7,8,10,11,13,14,\ldots\}{1,2,4,5,7,8,10,11,13,14,…}. Таким образом, парами друзей являются (3,1)(3,1) (6,2)(6,2) (9,4)(9,4) и так далее.

Формат входных данных
На вход в первой строке подается натуральное число nn — количество чисел в наборе. 1\leq n\leq 10^51≤n≤10
5
. Во второй строке через пробел подается nn натуральных чисел a_1,a_2,\ldots,a_na
1

,a
2

,…,a
n

. Числа не превосходят 10^{18}10
18
. Обратите внимание, что для хранения таких чисел в программе на С++ вам потребуется тип long long. В программе на PascalABC такой тип называется Int64.

Формат выходных данных
Программа должна вывести через пробел nn натуральных чисел b_1,b_2,\ldots,b_nb
1

,b
2

,…,b
n

. Число b_ib
i

должно быть другом числа a_ia
i

.

Если вы программируете на Python, то заменить перенос строки на пробел в функции print можно при именованного параметра end, например print(a,end=' ').

Методика проверки
Программа проверяется на 20 тестах. Прохождение каждого теста оценивается в Тест из условия задачи при проверке не используется. В первых 5 тестах n\leq10n≤10, a_i\leq 1000a
i

≤1000. В следующих пяти тестах n\leq 10^5n≤10
5
, a_i\leq 10^6a
i

≤10
6
. В последних 10 тестах a_i\leq10^{18}a
i

≤10
18
.

Sample Input:
10
1 2 3 4 5 6 7 8 9 10

Sample Output:
3 6 1 9 12 2 15 18 4 21

Напишите программу

языки на выбор
C#
Java
Python
Pascal