xy — IATI junior
Task type: batch | Time limit: 0.2 s | Memory limit: 256 MB | Difficulty: 14
Algorithms: number theory, graph theory, mathematics, topological sort, directed acyclic graph, prefix sum

# XV INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS

**Task 6. XY** 0.5 s. 256 MB

Kaloyan was preparing an exam for his students and found the following problem to be pretty interesting. He wrote two numbers $X$ and $Y$ and wants to find a sequence of integers where the sum of every $X$ consecutive elements (in the sequence) is strictly positive while the sum of every $Y$ consecutive elements is strictly negative.

Kaloyan found out that this sequence cannot be infinitely long. He tried to find a sequence of maximum possible length with the described property. However, it turns out to be rather difficult problem for Kaloyan. Help him by writing a program XY that finds the maximum length of such a sequence. You should find the answers to $Q$ such pairs $X$ and $Y$. Additionally, you have to find a maximal sequence only for the first query.

### Input

The only line of the standard input contains one number $Q$ - the number of queries. Each of the following $Q$ lines contains two numbers - $X$ and $Y$.

### Output

On the first line of the standard output you should print $Q$ numbers - $N_1, N_2, ..., N_Q$, separated with intervals, where $N_i$ is the answer for the $i^{th}$ query. On the second line you should print $N_1$ integers separated with intervals - a sequence with the desired property for the first query.

### Constraints

*   $1 \le X, Y \le 100\ 000$
*   $1 \le Q \le 100\ 000$

### Subtasks

| Subtask | Points | Required subtasks | Additional constraints                      |
| :------ | :----- | :---------------- | :------------------------------------------ |
| 1       | 0      | -                 | The example.                                |
| 2       | 3      | -                 | For every query: $X = Y$                    |
| 3       | 4      | 2                 | For every query: $X$ divides $Y$ or $Y$ divides $X$ |
| 4       | 9      | -                 | $X, Y \le 5, Q = 1$                         |
| 5       | 12     | -                 | $|X - Y| = 1$                               |
| 6       | 15     | 4                 | $X, Y, Q \le 100$                           |
| 7       | 15     | 4, 6              | $X, Y, Q \le 10000$                         |
| 8       | 35     | 1 - 7             | No additional constraints.                  |

*The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.*

![](_page_1_Picture_1.jpeg)

### Example

| Input | Output          |
| :---- | :-------------- |
| 3     | 6 4 3           |
| 3 5   | 5 -7 5 3 -7 5 |
| 1 5   |                 |
| 4 2   |                 |

Starter code: