Golden Apples

There are n apples numbered from 1 to n. Exactly two of these apples are golden apples. You are allowed to ask queries to determine their indices.

In each query, you partition the set of apples into two non-empty disjoint subsets \(S_1\) and \(S_2\) (i.e. every apple belongs to exactly one subset). Let \(x\) be the number of golden apples in \(S_1\) and \(y\) be the number in \(S_2\). The interactor then returns the value \(x \times y\) as the result of your query.

The interactor is adaptive, meaning that the actual indices of the golden apples may change with each query, as long as all previous query responses remain consistent. Your task is to determine the two golden apple indices using no more than 19 queries.

Note: Since the interactor is adaptive, a trivial strategy that does not ask any queries is valid. For example, outputting "1 2" without any queries will always be consistent, as no information has been revealed to contradict this answer.

You need to submit a solution that outputs two distinct indices (between 1 and n) that correspond to the golden apples.

inputFormat

The input consists of a single integer n (\(n \ge 2\)) representing the total number of apples. In interactive problems, your solution may issue queries as described but note that a no-query solution is acceptable.

outputFormat

Output two distinct integers separated by a space representing the indices of the golden apples.

sample

2

1 2