There is a device in Inazuma, like the picture shows. It contains some stones(placed in a line) and each stone has one to three gleamy petals on it. If one stone is knocked, the gleamy petals on it and the adjacent stone(if has) will change as follow:

• 1->2

• 2->3

• 3->1

When the numbers of gleamy petals on each stone come to equal, an exquisite treasure box will appear as reward.

luckly, the scholars in Sumeru(The Kingdom of Wisdom) created a machine which can run various codes(include c++, java and so on). The traveller recorded the number of gleamy petals on each stone and came to Sumeru to get solution by the machine.

However, the traveller doesn't know how to write code. Can you help to write a program which can tell the traveller how to make all the stones have the same number of the gleamy petals?

输入描述:

The first line is a single integer —the number of stones.

The second line contains n integers  representing the number of bright petals on each stone in order.

The input is guaranteed to have a solution.

输出描述:

A line contains n integers  representing the knock times of each stone in order.

If there are more than one answer, output the answer had the minimum total knock times. If there are still more than one answer had the minimum total knock times, output the answer had the minimum lexicographical order of them.

3
2 3 1

1 0 2