409065: GYM103428 K Tiny Stars

Even though they are tiny now, they will be shiny shooting stars someday.

It is every newbie's dream to be a grandmaster in algorithm contests, including Zayin. So it is your task to encourage him.

Zayin is solving a problem. He is given an integer $$$n$$$ where $$$n$$$ is an odd prime. Simultaneously there is an undirected graph with $$$n-1$$$ vertexes, labeled from $$$1$$$ to $$$n-1$$$, and a parameter $$$a\in[1,n)$$$. For every vertex $$$i$$$, Zayin has to assign an edge for it from one of the two options:

• add an edge between $$$i$$$ and $$$\frac ia \bmod n$$$. The time cost of it is $$$1$$$ due to the calculation of multiplying $$$a^{-1} \bmod n$$$.
• add an edge between $$$i$$$ and $$$\frac ai \bmod n$$$. The time cost of it is $$$\lceil \log_2 n \rceil$$$ due to the calculation of the inverse of $$$i$$$.

$$$a$$$ is not shown to Zayin until he has decided the way to assign edges. After that, Zayin runs his naive algorithm on the graph. For every connected component with size $$$s$$$, the time cost is $$$s^2$$$.

If the total time cost is less or equal than $$$12n$$$, the algorithm will be accepted.

You are to help Zayin in the following ways:

1. You give him an oracle sequence $$$oracle_1,\cdots,oracle_{n-1}$$$ where each $$$oracle_i \in \{0,1\}$$$ represents the option to choose for vertex $$$i$$$, i.e. if $$$oracle_i=0$$$, he links $$$i$$$ and $$$\frac ia \bmod n$$$, otherwise he links $$$i$$$ and $$$\frac ai \bmod n$$$.
2. Then the judge will randomly generate 20 parameters $$$a_1,\cdots,a_{20}$$$. The algorithm passes the test case if it is accepted on some $$$a_i$$$ of them. Notice that Zayin uses the same oracle for every $$$a$$$.

The only line contains an integer $$$n$$$. ($$$3 \le n \le 10^4$$$, $$$n$$$ is an odd prime.)

The only line contains $$$n-1$$$ integers $$$oracle_1,\cdots,oracle_{n-1}$$$, representing your oracle sequence.

5

0 0 0 0