32159번 - 평균 구하기 스페셜 저지

$N$개의 정수가 주어질 때, 이들의 평균을 구하는 프로그램을 작성하려고 한다.

이를 위해 무한 정밀도의 실수를 저장하는 레지스터 $2\,000$개를 사용할 수 있다. 이 레지스터는 $R_{1}$, $R_{2}$, ..., $R_{2\,000}$으로 이름이 매겨져 있다.

초기에 $N$개의 정수는 $R_{1}$, $R_{2}$, $\cdots$, $R_{N}$에 저장되어 있다. 나머지 $2\,000-N$개 레지스터에는 $0$이 저장되어 있다. 당신이 할 수 있는 연산은 다음과 같다.

• $a$ $b$ $c$: $R_{c}$에 $(R_{a}+R_{b}) /2$의 값을 덮어씌운다.

$a$, $b$, $c$가 다를 필요는 없다. 예를 들어, $a=1$, $b=2$, $c=1$는 $R_{1}$과 $R_{2}$의 평균을 구한 뒤 그 값을 $R_{1}$에 저장하는 연산이다.

이 연산을 $1\,000$번 이하로 사용하여, 처음에 $R_{2\,000}$에 $R_{1}$, $R_{2}$, $\cdots$, $R_{N}$에 주어진 값의 평균을 저장하는 프로그램을 작성하고 싶다. 그러나 위 연산만으로는 정확한 평균을 구할 수 없다는 것을 증명할 수 있다. 따라서 이 문제에서는 정확한 값을 구하는 대신 절대 오차를 $10^{-9}$ 이하로 해야 한다.

처음에 $R_{1}$, $R_{2}$, $\cdots$, $R_{N}$에 저장된 수들은 모두 $0$ 이상 $10^{9}$ 이하의 정수임이 보장된다. 이 범위의 어떤 수가 들어오더라도 평균과 차이가 $10^{-9}$ 이하인 값을 구해야 한다.

첫 번째 줄에 $N$이 주어진다. ($2\le N\le 10$)

첫 번째 줄에 프로그램이 수행할 연산의 수 $M$을 출력한다. ($0\le M\le 1\,000$)

다음 $M$개의 줄에 프로그램의 연산을 나타내는 $3$개의 수 $a$, $b$, $c$를 공백을 사이에 두고 출력한다. ($1\le a,b,c\le 2\,000$)

프로그램이 $M$개의 연산을 차례대로 수행했을 때, $R_{2\,000}$에는 처음에 $R_{1}$, $R_{2}$, $\cdots$, $R_{N}$에 주어진 값의 평균과 차이가 $10^{-9}$ 이하인 값이 저장되어 있어야 한다. $M$이 최소일 필요는 없다.