Product

Problem Description

You are given a prime $p$. For a number $a$, you need to find positive integers $x_1, x_2, \dots, x_k$ such that $\prod x_i \equiv a \pmod p$, and $\sum x_i\leq 2500$. Output any valid solution.

Input

The first line contains a prime $p (1\leq p \leq 10^{18})$, $p$ is chosen uniformly and randomly from $[0.9\times 10^{18}, 10^{18}]$. The second line contains a integer $q (1\leq q\leq 100)$. Each line of the following $q$ lines contains an integer $a (1\leq a\leq p-1)$, $a$ is chosen from $[1, p-1]$ uniformly and randomly.

Output

Output $q$ lines for each number. In each line, prine $k$ first, then $x_1, x_2, \dots, x_k$.

Sample Input

178187
3
6
100
109065

Sample Output

2 2 3
1 100
2 1000 1000

Source

2020 Multi-University Training Contest 9