Cantor Set Fractions

Alice, the mathematician, is fascinated by real numbers between \(0\) and \(1\). She uses a sequence of filters to construct the Cantor set. The construction is as follows:

• For each positive integer \(k\), consider the interval \([0, 1]\) and divide it into \(3^k\) equal parts. This gives \(3^k+1\) points and \(3^k\) intervals.
• The \(k\)-th filter covers the \((3i-1)\)-th interval for every valid integer \(i\) (i.e. the 2^nd, 5^th, 8^th intervals, etc.). Note that the endpoints of these intervals are not removed.

The process of applying all these filters to \([0,1]\) removes many numbers; the remaining numbers form the Cantor set. A classic characterization of the Cantor set is that a number \(x\) in \([0,1]\) belongs to the Cantor set if and only if it has a ternary (base-3) representation that avoids the digit \(1\). (Note: if there is ambiguity in representation, one can always choose a representation that does not include \(1\), since endpoints remain.)

Given an integer \(N\), consider the fractions of the form \(\frac{x}{N}\) where \(x\) is an integer in \([0, N]\). Your task is to output all fractions \(\frac{x}{N}\) that are in the Cantor set, in increasing order. Each fraction should be printed in the format x/N.

inputFormat

The input consists of a single line containing one integer \(N\) (where \(N \ge 1\)).

outputFormat

Output a single line containing all fractions \(\frac{x}{N}\) that are in the Cantor set, in increasing order, separated by a single space. Every fraction is represented as x/N.

sample

1

0/1 1/1