Robot Knowledge Independence and Career Classification

In the year 3030, Macsy is deploying a line of robots on Mars. At second $1$, robot $1$ is landed on Mars. Robot $1$ is special: it is the only one that can manufacture other robots and its knowledge is always independent of the rest. At second $2$, robot $1$ produces robot $2$, at second $3$ it produces robot $3$, and so on – at second $m$, robot $m$ is produced. Immediately upon being created, every robot starts working.

For every robot with number $m$ ($m\ge2$), it goes to work immediately, but every robot $j$ (with $j\ge2$) rests every $j$ seconds after its birth (that is, robot $j$ rests at seconds which are multiples of $j$, with the first rest at time $2j$). When a robot is resting at the moment a new robot is born, its memory is transferred to the new robot. In other words, when robot $m$ is created (at second $m$), every robot $j$ with $2\le j<m$ that satisfies \[ m\ \%\ j=0 \] (that is, $j$ divides $m$) is considered a teacher of robot $m$. Note that robot $1$ never becomes a teacher and its knowledge is always independent of any other robot.

The independence number of a robot is defined as the number of robots with smaller indices whose knowledge is independent of that robot. Two robots are said to have independent knowledge if they do not have a direct teacher‐student relation and they do not share any common teacher. It can be shown that under these rules the independence number of a robot $x$ is exactly \(\varphi(x)\) (Euler's totient function) for \(x>1\) (with the convention that robot $1$ has an independence number of $0$).

Each newly manufactured robot is assigned one of three careers according to its number $m$ as follows. Let the odd‐part of $m$ be the factorization into odd primes. If and only if $m$ can be written as a product of distinct odd primes and nothing else (i.e. no factor $2$ and no repeated factor) and the number of factors is even, then robot $m$ is a politician (for example, $15=3\times5$). Otherwise, if $m$ is an odd prime or if $m$ can be written as a product of distinct odd primes with an odd number of factors, then robot $m$ is a soldier (for example, $3$ or $165=3\times5\times11$). All other cases result in a scholar (for example, $2$, $6$, or $9$).

When robot $m$ is born, it wants to know the sum of independence numbers (i.e. \(\varphi(\cdot)\)) of itself and of all of its teachers, grouped by career. More precisely, let \[ S=\{m\}\cup\{d:\; 2\le d<m \text{ and } d\mid m\}\n\] be the set consisting of robot $m$ and all its teachers. For each career (politician, soldier, scholar), compute the sum of the independence numbers \(\varphi(x)\) for all $x\in S$ of that career. Since these sums can be huge, output each sum modulo 10000.

Note: Macsy has already done the odd prime factorization for $m$. The input includes $m$ and then the distinct odd prime factors of $m$ (if any), which you may use to determine the career of robot $m$. However, note that you must compute the career for every relevant robot in $S$.

Career Determination Summary

• If robot number $m$ has any factor 2 or if the factorization of $m$ (ignoring powers) does not match $m$ exactly then it is a scholar.
• If $m$ is odd and can be written as a product of distinct odd primes only and the number of such primes is even, then it is a politician.
• If $m$ is odd and either $m$ is an odd prime or it can be written as a product of distinct odd primes with an odd number of factors, then it is a soldier.

Input/Output example:

For example, if m is 6, the divisors (excluding 1) are {2, 3, 6}.
We have: \(\varphi(2)=1\), \(\varphi(3)=2\), \(\varphi(6)=2\).
Robot 2: 2 is even → scholar.
Robot 3: 3 is an odd prime → soldier.
Robot 6: 6 has a factor 2 → scholar.
Thus, the answer would be: politician: 0, soldier: 2, scholar: (1+2)=3.

inputFormat

The input consists of:

1. A line containing the integer m ($1 \le m \le 10^6$).
2. A line containing an integer k (the number of distinct odd prime factors of m; may be 0).
3. If k > 0, a line with k distinct odd primes (space‐separated) which are the odd prime factors of m.

outputFormat

Output three space‐separated integers: the sum modulo 10000 of independence numbers \(\varphi(x)\) for all robots in set \(S = \{m\}\cup\{d : 2 \le d < m \text{ and } d\mid m\}\) that are politicians, soldiers, and scholars respectively.

sample

6
1
3

0 2 3