Bracket

Subin has disliked for a long time that the UCPC contest format is the same as ICPC's. So as soon as he became president of Jeondae Pro Yeon, he announced that he would turn UCPC into a tournament-style contest that differs from ICPC.

The new UCPC process Subin designed works as follows.

1. Find the smallest power of 2 that is greater than or equal to the number of teams, and line up that many empty slots in a row.
2. Assign the teams to the slots appropriately. Two or more teams may not be assigned to the same slot.
3. Pair the slots two at a time from the front. If both slots in a pair have a team assigned, the two teams play a match, and the slot of the losing team is removed. Otherwise, no match is played, and one of the empty slots is removed.
4. Repeat step 3 until one team remains. The last remaining team becomes the champion.

When Subin tried assigning teams one by one from the front slot, he found that the bracket would be unfair. For example, when 5 teams enter, the team in the first slot must win three matches to become champion, but the team in the fifth slot only has to win one match.

Unfair bracket and fair bracket

Subin wants the team that must play the most matches to win the title and the team that must play the fewest matches to win it to differ by at most one match. If several arrangements satisfy this, he wants the one where the slot numbers of the assigned teams, sorted in descending order, form the lexicographically smallest sequence. In other words, a better arrangement has a smaller slot number for the team placed last.

The first line contains an integer N (1 ≤ N ≤ 1,000,000), the number of teams that entered the contest.

Print one line with the arrangement Subin wants. The length of the string must equal the number of slots. Use # for a slot with a team and . for an empty slot.