몸값

이것은 대화형 문제이다.

Balder가 살해된 뒤, Odin은 그를 죽은 자들의 세계 Helheim에서 Asgard로 데려오기로 했다. Odin은 자신의 말 Sleipnir를 Hermod에게 주고, 죽음의 여신 Hel에게 가서 Balder의 몸값을 제안하라고 했다. Hel은 세상의 모든 것과 모든 존재가 Balder를 애도하면 그를 풀어 주겠다고 했다. 이 조건은 이행할 수 없었기에, Hermod와 Hel은 다른 몸값 액수를 의논했다.

Hermod는 세상에 도시 $n$개가 있고, 그곳에 사는 모든 사람이 Balder를 애도할 준비가 되어 있다고 말했다. 도시 $i$의 인구를 $a_i$라고 하자. Hermod는 어느 도시의 인구도 밝히지 않았다. 대신 질문 몇 개에는 답하겠다고 했다. 질문은 다음과 같다. $a_{i_1} \times a_{i_2} \times \ldots \times a_{i_k}$의 곱을 알려 달라. 여기서 $i_1, \ldots, i_k$는 이 도시들 가운데 일부의 서로 다른 번호이다. 질문은 최대 $n$개까지 할 수 있다.

죽은 자들의 여왕을 도와 각 도시에 사는 사람 수를 알아내라.

각 질문 뒤에 심사 프로그램이 돌려주는 수는 매우 클 수 있다.

프로그램이 올바르게 동작하려면 출력할 때마다 다음 작업을 해야 한다.

• Pascal: flush(output);
• C/C++: fflush(stdout);
• Java: System.out.flush();
• Python: sys.stdout.flush();

또한 출력한 줄마다 끝에 줄바꿈을 넣어야 한다.