yl-9/probench huggingface dataset:
# Medium Demon Problem (hard version)

## Problem Description

This is the hard version of the problem. The key difference between the two versions is highlighted in bold.

A group of $ n $ spiders has come together to exchange plushies. Initially, each spider has $ 1 $ plushie. Every year, if spider $ i $ has at least one plushie, he will give exactly one plushie to spider $ r_i $ . Otherwise, he will do nothing. Note that all plushie transfers happen at the same time. In this version, each spider is allowed to have more than 1 plushie at any point in time.

The process is stable in the current year if each spider has the same number of plushies (before the current year's exchange) as he did the previous year (before the previous year's exchange). Note that year $ 1 $ can never be stable.

Find the first year in which the process becomes stable.

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — the number of spiders.

The following line contains $ n $ integers $ r_1, r_2, \ldots, r_n $ ( $ 1 \leq r_i \leq n, r_i \neq i $ ) — the recipient of the plushie of each spider.

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

## Output Format

For each test case, output an integer on a new line, the first year in which the process becomes stable.

## Sample #1

### Sample Input #1

```
5
2
2 1
5
2 3 4 5 1
5
2 1 4 2 3
5
4 1 1 5 4
10
4 3 9 1 6 7 9 10 10 3
```

### Sample Output #1

```
2
2
5
5
5
```

## Hint

For the second test case:

- At year $ 1 $ , the following array shows the number of plushies each spider has: $ [1, 1, 1, 1, 1] $ . Then, year $ 1 $ 's exchange happens.
- At year $ 2 $ , the following array shows the number of plushies each spider has: $ [1, 1, 1, 1, 1] $ . Since this array is the same as the previous year, this year is stable.

For the third test case:

- At year $ 1 $ , the following array shows the number of plushies each spider has: $ [1, 1, 1, 1, 1] $ . Then, year $ 1 $ 's exchange happens.
- At year $ 2 $ , the following array shows the number of plushies each spider has: $ [1, 2, 1, 1, 0] $ . Then, year $ 2 $ 's exchange happens.
- At year $ 3 $ , the following array shows the number of plushies each spider has: $ [1, 3, 0, 1, 0] $ . Then, year $ 3 $ 's exchange happens.
- At year $ 4 $ , the following array shows the number of plushies each spider has: $ [1, 4, 0, 0, 0] $ . Then, year $ 4 $ 's exchange happens.
- At year $ 5 $ , the following array shows the number of plushies each spider has: $ [1, 4, 0, 0, 0] $ . Since this array is the same as the previous year, this year is stable.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: dfs and similar, dp, dsu, graphs, implementation, trees
Difficulty: 1900
# Medium Demon Problem (easy version)

## Problem Description

This is the easy version of the problem. The key difference between the two versions is highlighted in bold.

A group of $ n $ spiders has come together to exchange plushies. Initially, each spider has $ 1 $ plushie. Every year, if spider $ i $ has at least one plushie, he will give exactly one plushie to spider $ r_i $ . Otherwise, he will do nothing. Note that all plushie transfers happen at the same time. In this version, if any spider has more than $ 1 $ plushie at any point in time, they will throw all but $ 1 $ away.

The process is stable in the current year if each spider has the same number of plushies (before the current year's exchange) as he did the previous year (before the previous year's exchange). Note that year $ 1 $ can never be stable.

Find the first year in which the process becomes stable.

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — the number of spiders.

The following line contains $ n $ integers $ r_1, r_2, \ldots, r_n $ ( $ 1 \leq r_i \leq n, r_i \neq i $ ) — the recipient of the plushie of each spider.

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

## Output Format

For each test case, output an integer on a new line, the first year in which the process becomes stable.

## Sample #1

### Sample Input #1

```
5
2
2 1
5
2 3 4 5 1
5
2 1 4 2 3
5
4 1 1 5 4
10
4 3 9 1 6 7 9 10 10 3
```

### Sample Output #1

```
2
2
5
4
5
```

## Hint

For the second test case:

- At year $ 1 $ , the following array shows the number of plushies each spider has: $ [1, 1, 1, 1, 1] $ . Then, year $ 1 $ 's exchange happens.
- At year $ 2 $ , the following array shows the number of plushies each spider has: $ [1, 1, 1, 1, 1] $ . Since this array is the same as the previous year, this year is stable.

For the third test case:

- At year $ 1 $ , the following array shows the number of plushies each spider has: $ [1, 1, 1, 1, 1] $ . Then, year $ 1 $ 's exchange happens.
- At year $ 2 $ , the following array shows the number of plushies each spider has: $ [1, 1, 1, 1, 0] $ . Then, year $ 2 $ 's exchange happens. Note that even though two spiders gave spider $ 2 $ plushies, spider $ 2 $ may only keep one plushie.
- At year $ 3 $ , the following array shows the number of plushies each spider has: $ [1, 1, 0, 1, 0] $ . Then, year $ 3 $ 's exchange happens.
- At year $ 4 $ , the following array shows the number of plushies each spider has: $ [1, 1, 0, 0, 0] $ . Then, year $ 4 $ 's exchange happens.
- At year $ 5 $ , the following array shows the number of plushies each spider has: $ [1, 1, 0, 0, 0] $ . Since this array is the same as the previous year, this year is stable.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: dfs and similar, graph matchings, graphs, implementation, trees
Difficulty: 1700
# Easy Demon Problem

## Problem Description

For an arbitrary grid, Robot defines its beauty to be the sum of elements in the grid.

Robot gives you an array $ a $ of length $ n $ and an array $ b $ of length $ m $ . You construct a $ n $ by $ m $ grid $ M $ such that $ M_{i,j}=a_i\cdot b_j $ for all $ 1 \leq i \leq n $ and $ 1 \leq j \leq m $ .

Then, Robot gives you $ q $ queries, each consisting of a single integer $ x $ . For each query, determine whether or not it is possible to perform the following operation exactly once so that $ M $ has a beauty of $ x $ :

1. Choose integers $ r $ and $ c $ such that $ 1 \leq r \leq n $ and $ 1 \leq c \leq m $
2. Set $ M_{i,j} $ to be $ 0 $ for all ordered pairs $ (i,j) $ such that $ i=r $ , $ j=c $ , or both.

Note that queries are not persistent, meaning that you do not actually set any elements to $ 0 $ in the process — you are only required to output if it is possible to find $ r $ and $ c $ such that if the above operation is performed, the beauty of the grid will be $ x $ . Also, note that you must perform the operation for each query, even if the beauty of the original grid is already $ x $ .

## Input Format

The first line contains three integers $ n $ , $ m $ , and $ q $ ( $ 1 \leq n,m \leq 2\cdot 10^5, 1 \leq q \leq 5\cdot 10^4 $ ) — the length of $ a $ , the length of $ b $ , and the number of queries respectively.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq |a_i| \leq n $ ).

The third line contains $ m $ integers $ b_1, b_2, \ldots, b_m $ ( $ 0 \leq |b_i| \leq m $ ).

The following $ q $ lines each contain a single integer $ x $ ( $ 1 \leq |x| \leq 2\cdot 10^5 $ ), the beauty of the grid you wish to achieve by setting all elements in a row and a column to $ 0 $ .

## Output Format

For each testcase, output "YES" (without quotes) if there is a way to perform the aforementioned operation such that the beauty is $ x $ , and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

## Sample #1

### Sample Input #1

```
3 3 6
-2 3 -3
-2 2 -1
-1
1
-2
2
-3
3
```

### Sample Output #1

```
NO
YES
NO
NO
YES
NO
```

## Sample #2

### Sample Input #2

```
5 5 6
1 -2 3 0 0
0 -2 5 0 -3
4
-3
5
2
-1
2
```

### Sample Output #2

```
YES
YES
YES
YES
NO
YES
```

## Hint

In the second example, the grid is

 0 -2 5 0 -3

0 4 -10 0 6

0 -6 15 0 -9

0 0 0 0 0

0 0 0 0 0

By performing the operation with $ r=4 $ and $ c=2 $ , we create the following grid:

0 0 5 0 -3

0 0 -10 0 6

0 0 15 0 -9

0 0 0 0 0

0 0 0 0 0

which has beauty $ 4 $ . Thus, we output YES.

In the second query, selecting $ r=3 $ and $ c=5 $ creates a grid with beauty $ -3 $ .

In the third query, selecting $ r=3 $ and $ c=3 $ creates a grid with beauty $ 5 $ .

## Limit



Time Limit
4.00s

Memory Limit
250.00MB

Tags: binary search, brute force, data structures, math, number theory
Difficulty: 1900
# Insane Problem

## Problem Description

Wave is given five integers $ k $ , $ l_1 $ , $ r_1 $ , $ l_2 $ , and $ r_2 $ . Wave wants you to help her count the number of ordered pairs $ (x, y) $ such that all of the following are satisfied:

- $ l_1 \leq x \leq r_1 $ .
- $ l_2 \leq y \leq r_2 $ .
- There exists a non-negative integer $ n $ such that $ \frac{y}{x} = k^n $ .

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The only line of each test case contains five integers $ k $ , $ l_1 $ , $ r_1 $ , $ l_2 $ , and $ r_2 $ ( $ 2 \leq k \leq 10^9, 1 \leq l_1 \leq r_1 \leq 10^9, 1 \leq l_2 \leq r_2 \leq 10^9 $ ).

## Output Format

For each test case, output the number of matching ordered pairs $ (x, y) $ on a new line.

## Sample #1

### Sample Input #1

```
5
2 2 6 2 12
2 1 1000000000 1 1000000000
3 5 7 15 63
1000000000 1 5 6 1000000000
15 17 78 2596 20914861
```

### Sample Output #1

```
12
1999999987
6
1
197
```

## Hint

In the third test case, the matching ordered pairs are the following:

- $ (5,15) $
- $ (5,45) $
- $ (6,18) $
- $ (6,54) $
- $ (7,21) $
- $ (7,63) $

In the fourth test case, the only valid ordered pair is $ (1,1\,000\,000\,000) $

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, greedy, implementation, math, number theory
Difficulty: 1300
# Harder Problem

## Problem Description

Given a sequence of positive integers, a positive integer is called a mode of the sequence if it occurs the maximum number of times that any positive integer occurs. For example, the mode of $ [2,2,3] $ is $ 2 $ . Any of $ 9 $ , $ 8 $ , or $ 7 $ can be considered to be a mode of the sequence $ [9,9,8,8,7,7] $ .

You gave UFO an array $ a $ of length $ n $ . To thank you, UFO decides to construct another array $ b $ of length $ n $ such that $ a_i $ is a mode of the sequence $ [b_1, b_2, \ldots, b_i] $ for all $ 1 \leq i \leq n $ .

However, UFO doesn't know how to construct array $ b $ , so you must help her. Note that $ 1 \leq b_i \leq n $ must hold for your array for all $ 1 \leq i \leq n $ .

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of $ a $ .

The following line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ).

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

## Output Format

For each test case, output $ n $ numbers $ b_1, b_2, \ldots, b_n $ ( $ 1 \leq b_i \leq n $ ) on a new line. It can be shown that $ b $ can always be constructed. If there are multiple possible arrays, you may print any.

## Sample #1

### Sample Input #1

```
4
2
1 2
4
1 1 1 2
8
4 5 5 5 1 1 2 1
10
1 1 2 2 1 1 3 3 1 1
```

### Sample Output #1

```
1 2
1 1 2 2
4 5 5 1 1 2 2 3
1 8 2 2 1 3 3 9 1 1
```

## Hint

Let's verify the correctness for our sample output in test case $ 2 $ .

- At $ i = 1 $ , $ 1 $ is the only possible mode of $ [1] $ .
- At $ i = 2 $ , $ 1 $ is the only possible mode of $ [1, 1] $ .
- At $ i = 3 $ , $ 1 $ is the only possible mode of $ [1, 1, 2] $ .
- At $ i = 4 $ , $ 1 $ or $ 2 $ are both modes of $ [1, 1, 2, 2] $ . Since $ a_i = 2 $ , this array is valid.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, math
Difficulty: 1100
# Hard Problem

## Problem Description

Ball is the teacher in Paperfold University. The seats of his classroom are arranged in $ 2 $ rows with $ m $ seats each.

Ball is teaching $ a + b + c $ monkeys, and he wants to assign as many monkeys to a seat as possible. Ball knows that $ a $ of them only want to sit in row $ 1 $ , $ b $ of them only want to sit in row $ 2 $ , and $ c $ of them have no preference. Only one monkey may sit in each seat, and each monkey's preference must be followed if it is seated.

What is the maximum number of monkeys that Ball can seat?

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

Each test case contains four integers $ m $ , $ a $ , $ b $ , and $ c $ ( $ 1 \leq m, a, b, c \leq 10^8 $ ).

## Output Format

For each test case, output the maximum number of monkeys you can seat.

## Sample #1

### Sample Input #1

```
5
10 5 5 10
3 6 1 1
15 14 12 4
1 1 1 1
420 6 9 69
```

### Sample Output #1

```
20
5
30
2
84
```

## Hint

In the second test case, $ 6 $ monkeys want to sit in the front row, but only $ 3 $ seats are available. The monkeys that have no preference and the monkeys who prefer sitting in the second row can sit in the second row together. Thus, the answer is $ 3+2=5 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: greedy, math
Difficulty: 800
# Normal Problem

## Problem Description

A string consisting of only characters 'p', 'q', and 'w' is painted on a glass window of a store. Ship walks past the store, standing directly in front of the glass window, and observes string $ a $ . Ship then heads inside the store, looks directly at the same glass window, and observes string $ b $ .

Ship gives you string $ a $ . Your job is to find and output $ b $ .

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases.

The only line of each test case contains a string $ a $ ( $ 1 \leq |a| \leq 100 $ ) — the string Ship observes from outside the store. It is guaranteed that $ a $ only contains characters 'p', 'q', and 'w'.

## Output Format

For each test case, output string $ b $ , the string Ship observes from inside the store, on a new line.

## Sample #1

### Sample Input #1

```
5
qwq
ppppp
pppwwwqqq
wqpqwpqwwqp
pqpqpqpq
```

### Sample Output #1

```
pwp
qqqqq
pppwwwqqq
qpwwpqwpqpw
pqpqpqpq
```

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: implementation, strings
Difficulty: 800
# Easy Problem

## Problem Description

Cube is given an integer $ n $ . She wants to know how many ordered pairs of positive integers $ (a,b) $ there are such that $ a=n-b $ . Since Cube is not very good at math, please help her!

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 99 $ ) — the number of test cases.

The only line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 100 $ ).

## Output Format

For each test case, output the number of ordered pairs $ (a, b) $ on a new line.

## Sample #1

### Sample Input #1

```
3
2
4
6
```

### Sample Output #1

```
1
3
5
```

## Hint

In the first test case, the only ordered pair that works is $ (a,b)=(1,1) $ .

In the second test case, the three ordered pairs of $ (a,b) $ that work are $ (3,1), (2,2), (1,3) $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, math
Difficulty: 800
# Problem with Queries

## Problem Description

You are given an array $ a $ , consisting of $ n $ integers. Your task is to process $ q $ queries of two types:

- $ 1~p~x $ — set the value of the element at index $ p $ equal to $ x $ ;
- $ 2~l~r $ — count the number of pairs of indices $ (i, j) $ such that $ l \le i < j \le r $ and $ a_i \ne a_j $ .

Note that the queries in this task are encoded; each subsequent query can only be decoded after calculating the answer to the preceding query of the second type.

## Input Format

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ).

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ).

The third line contains a single integer $ q $ ( $ 1 \le q \le 3 \cdot 10^5 $ ) — the number of queries.

The next $ q $ lines describe the queries in one of the following formats:

- $ 1~p'~x' $ ( $ 0 \le p', x' \le n-1 $ );
- $ 2~l'~r' $ ( $ 0 \le l', r' \le n-1 $ ).

The queries are encoded as follows: let $ \mathit{last} $ be the answer to the latest processed query of the second type (initially, $ \mathit{last} = 0 $ ).

- if the type of the query is $ 1 $ , then $ p = ((p' + \mathit{last}) \bmod n) + 1 $ , $ x = ((x' + \mathit{last}) \bmod n) + 1 $ .
- if the type of the query is $ 2 $ , $ l = ((l' + \mathit{last}) \bmod n) + 1 $ , $ r = ((r' + \mathit{last}) \bmod n) + 1 $ . If $ l > r $ , swap their values.

Don't forget to update the value of $ \mathit{last} $ after answering each query of the second type.

Additional constraint on the input: there is at least one query of the second type.

## Output Format

For each query of the second type, print the answer — the number of pairs of indices $ (i, j) $ such that $ l \le i < j \le r $ and $ a_i \ne a_j $ .

## Sample #1

### Sample Input #1

```
3
1 2 3
5
2 0 2
1 0 2
2 0 2
1 2 0
2 1 0
```

### Sample Output #1

```
3 2 0
```

## Sample #2

### Sample Input #2

```
7
1 3 4 4 7 1 3
3
2 1 6
2 1 0
2 5 6
```

### Sample Output #2

```
13 18 0
```

## Hint

In the first example, the actual queries (after decoding) are:

- 2 1 3
- 1 1 3
- 2 1 3
- 1 2 3
- 2 1 3

## Limit



Time Limit
8.00s

Memory Limit
1000.00MB

Tags: brute force, data structures, implementation
# Nim

## Problem Description

Recall the rules of the game "Nim". There are $ n $ piles of stones, where the $ i $ -th pile initially contains some number of stones. Two players take turns choosing a non-empty pile and removing any positive (strictly greater than $ 0 $ ) number of stones from it. The player unable to make a move loses the game.

You are given an array $ a $ , consisting of $ n $ integers. Artem and Ruslan decided to play Nim on segments of this array. Each of the $ q $ rounds is defined by a segment $ (l_i, r_i) $ , where the elements $ a_{l_i}, a_{l_i+1}, \dots, a_{r_i} $ represent the sizes of the piles of stones.

Before the game starts, Ruslan can remove any number of piles from the chosen segment. However, at least one pile must remain, so in a single round he can remove at most $ (r_i - l_i) $ piles. He is allowed to remove $ 0 $ piles. After the removal, the game is played on the remaining piles within the segment.

All rounds are independent: the changes made in one round do not affect the original array or any other rounds.

Ruslan wants to remove as many piles as possible so that Artem, who always makes the first move, loses.

For each round, determine:

1. the maximum number of piles Ruslan can remove;
2. the number of ways to choose the maximum number of piles for removal.

Two ways are considered different if there exists an index $ i $ such that the pile at index $ i $ is removed in one way but not in the other. Since the number of ways can be large, output it modulo $ 998\,244\,353 $ .

If Ruslan cannot ensure Artem's loss in a particular round, output -1 for that round.

## Input Format

The first line of input contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 10^5 $ ) — the size of the array and the number of segments for which the answers need to be calculated.

The second line of input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 50 $ ) — the elements of the initial array.

The $ i $ -th of the next $ q $ lines contains two integers $ l_i, r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — the bounds of the segment on which the boys want to play the game during the $ i $ -th round.

## Output Format

For each round:

- if Ruslan can win, print two integers — the maximum number of piles that can be removed, and the number of ways to remove the maximum number of piles, taken modulo $ 998\,244\,353 $ ;
- otherwise print -1.

## Sample #1

### Sample Input #1

```
9 5
0 1 2 1 3 4 5 6 0
1 5
2 5
3 5
4 5
1 9
```

### Sample Output #1

```
4 1
2 1
0 1
-1
8 2
```

## Limit



Time Limit
6.00s

Memory Limit
500.00MB

Tags: bitmasks, brute force, combinatorics, dp, games, greedy, implementation, shortest paths
# Problem about GCD

## Problem Description

Given three integers $ l $ , $ r $ , and $ G $ , find two integers $ A $ and $ B $ ( $ l \le A \le B \le r $ ) such that their greatest common divisor (GCD) equals $ G $ and the distance $ |A - B| $ is maximized.

If there are multiple such pairs, choose the one where $ A $ is minimized. If no such pairs exist, output "-1 -1".

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^3 $ ) — the number of test cases. Then, $ t $ test cases follow.

Each test case consists of a single line containing three integers $ l, r, G $ ( $ 1 \le l \le r \le 10^{18} $ ; $ 1 \le G \le 10^{18} $ ) — the range boundaries and the required GCD.

## Output Format

For each test case, output two integers $ A $ and $ B $ — the solution to the problem, or "-1 -1" if no such pair exists.

## Sample #1

### Sample Input #1

```
4
4 8 2
4 8 3
4 8 4
5 7 6
```

### Sample Output #1

```
4 6
-1 -1
4 8
6 6
```

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, flows, math, number theory
# Sums on Segments

## Problem Description

You are given an array $ a $ of $ n $ integers, where all elements except for at most one are equal to $ -1 $ or $ 1 $ . The remaining element $ x $ satisfies $ -10^9 \le x \le 10^9 $ .

Find all possible sums of subarrays of $ a $ , including the empty subarray, whose sum is defined as $ 0 $ . In other words, find all integers $ x $ such that the array $ a $ has at least one subarray (possibly empty) with sum equal to $ x $ . A subarray is a contiguous subsegment of an array.

Output these sums in ascending order. Each sum should be printed only once, even if it is achieved by multiple subarrays.

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Then, $ t $ test cases follow.

Each test case consists of two lines:

- The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the size of the array.
- The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ) — the elements of the array $ a $ . In the array $ a $ , there is at most one element that is neither $ 1 $ nor $ -1 $ .

Additional constraint on the input: the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output two lines:

- In the first line, print a single integer — the number of distinct subarray sums.
- In the second line, print these sums in ascending order.

Each sum should be printed only once, even if it is produced by multiple subarrays.

## Sample #1

### Sample Input #1

```
5
5
1 -1 10 1 1
5
-1 -1 -1 -1 -1
2
-1 2
2
7 1
3
1 4 -1
```

### Sample Output #1

```
8
-1 0 1 2 9 10 11 12 
6
-5 -4 -3 -2 -1 0 
4
-1 0 1 2 
4
0 1 7 8 
6
-1 0 1 3 4 5
```

## Hint

Let's define $ a[i,j] $ as the subarray of $ a $ from position $ i $ to position $ j $ .

Consider the first test case of the example:

- $ -1 $ is produced by $ a[2,2] $ ;
- $ 0 $ is produced by the empty subarray;
- $ 1 $ is produced by $ a[4,4] $ ;
- $ 2 $ is produced by $ a[4,5] $ ;
- $ 9 $ is produced by $ a[2,3] $ ;
- $ 10 $ is produced by $ a[1,3] $ ;
- $ 11 $ is produced by $ a[3,4] $ ;
- $ 12 $ is produced by $ a[3,5] $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: binary search, brute force, data structures, dp, greedy, math