G. Navigation Compass
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To collect Stellar Jade for Castorice, Soy starts to find treasures and solve puzzles in his maps. As a result, he encountered a hard puzzle named Navigation Compass.

An example of the Navigation Compass, where $$$a=[6,3,3], b=[1,2,4]$$$.

The compass is a regular $$$m$$$-gon, whose vertices are labeled $$$1,2,\dots,m$$$ in a clockwise direction, and vertex $$$1$$$ is distinguished by a blue mark. The compass features $$$n$$$ concentric rings, and these concentric rings are numbered $$$1,2,\dots,n$$$ from the innermost to the outermost. For each $$$i$$$-th ring, it has $$$a_i$$$ Astral Marks and a Celestial Axis which initially points to vertex $$$b_i$$$. The quantity of Astral Marks determines the extent of its Celestial Axis's advancement when the ring is rotated. Specifically, a single rotation causes the Celestial Axis of the i-th ring to advance $$$a_i$$$ positions along the vertices of the m-gon in the clockwise direction.

Soy can perform $$$n$$$ types of operations. In the $$$i$$$-th type of operation, Soy must rotate simultaneously the $$$i$$$-th ring and $$$(i\bmod n+1)$$$-th ring once. To get the Stellar Jade, he must:

  • Determine the number of distinct vertices $$$v$$$ such that it is possible for all $$$n$$$ Celestial Axes to point to the vertex simultaneously. Let this count be $$$C$$$. Note that he is only required to calculate $$$C$$$ and doesn't need to perform operations actually in this subproblem.
  • If $$$C \gt 0$$$, he should choose one of the attainable common vertices $$$v$$$ and perform operations to make all Celestial Axes point to it. If multiple $$$v$$$ exist, any one can be chosen as the goal for the sequence. Note that he doesn't need to minimize the number of operations.

Help Soy solve the puzzle and get $$$1,600$$$ Stellar Jade!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 5\cdot10^5$$$, $$$2\le m\le 10^9$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i \lt m$$$).

The third line of each test case contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ ($$$1\le b_i \le m$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, output one integer $$$C$$$ — the number of attainable vertices.

If $$$C \gt 0$$$, output two extra lines:

  • The first line contains one integer $$$v$$$ — the attainable vertex Soy chooses.
  • The second line contains $$$n$$$ integers $$$c_1,c_2,\dots,c_n$$$ ($$$0\le c_i \lt m$$$), $$$c_i$$$ indicating Soy should perform the $$$i$$$-th operation for $$$c_i$$$ times. It can be shown that if a solution exists, a solution also exists within the given constraints.
Example
Input
3
3 6
1 2 4
6 3 3
5 12
2 4 6 8 10
1 2 3 4 5
6 11
1 1 4 5 1 4
1 9 1 9 8 10
Output
3
1
1 1 0
0
1
8
7 3 7 6 5 0
Note

In the first sample case, Soy can perform operation type $$$1$$$ once and operation type $$$2$$$ once, after which all Celestial Axes will point to vertex $$$1$$$. The change of the compass is shown in the figure below.