E. Inverse Knapsack
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For his number theory homework, Busy Beaver is given $$$T$$$ pairs of a large prime $$$p$$$ and an integer $$$x$$$. For each pair, Busy Beaver needs to find a subset of $$$\{1,\frac 12,\frac 13,\cdots,\frac 1{5000}\}$$$ of size at most $$$S$$$ whose sum is equal to $$$x$$$ modulo $$$p$$$. Can you help him find such subsets?

A rational number $$$\frac ab$$$ is equal to $$$x$$$ modulo $$$p$$$ if $$$a \equiv bx \pmod p$$$.

Input

The first line contains two integers $$$T$$$ and $$$S$$$ ($$$1 \le T \le 1000$$$, $$$150 \le S \le 5000$$$), indicating the number of testcases and the maximum size of the subset.

Each of the next $$$T$$$ lines contains two integers $$$p$$$ and $$$x$$$ ($$$10^8 \le p \le 10^{18}$$$, $$$0 \le x \le p-1$$$), where $$$p$$$ is prime.

Output

For each testcase, output one line indicating the answer. Start with some integer $$$k$$$ ($$$0 \le k \le S$$$), indicating the size of the subset, and then follow with $$$k$$$ distinct integers $$$a_1,\dots,a_k$$$ in increasing order ($$$1 \le a_1 \lt a_2 \lt \dots \lt a_k \le 5000$$$).

Your output should satisfy $$$\frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_k} \equiv x \pmod p$$$.

It can be proven that for all $$$p$$$, $$$x$$$ satisfying the input constraints, such a subset always exists.

Scoring
  • ($$$10$$$ points) $$$T \le 10$$$, $$$p \le 10^9$$$.
  • ($$$20$$$ points) $$$T \le 10$$$, $$$p \le 10^{15}$$$, $$$S = 5000$$$.
  • ($$$30$$$ points) $$$S = 5000$$$.
  • ($$$40$$$ points) No additional constraints.
Example
Input
4 150
998244353 0
1000000007 1
1000000007 500000004
1000000007 642833014
Output
0
1 1
1 2
3 1 19 2025
Note

In the first test case, the empty subset sums to $$$x = 0$$$ modulo $$$p = 998244353$$$.

In the second test case, $$$\frac{1}{1} \equiv 1 \pmod {1000000007}$$$.

In the third test case, $$$\frac{1}{2} \equiv 500000004 \pmod {1000000007}$$$.

In the fourth test case, $$$\frac{1}{1} + \frac{1}{19} + \frac{1}{2025} \equiv 642833014 \pmod {1000000007}$$$.