yl-9/probench huggingface dataset:
# Make It Equal

## Problem Description

You are given an integer array $ a $ of size $ n $ . The elements of the array are numbered from $ 1 $ to $ n $ .

You can perform the following operation any number of times (possibly, zero): choose an index $ i $ from $ 1 $ to $ n $ ; decrease $ a_i $ by $ 2 $ and increase $ a_{(i \bmod n) + 1} $ by $ 1 $ .

After you perform the operations, all elements of the array should be non-negative equal integers.

Your task is to calculate the minimum number of operations you have to perform.

## Input Format

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

The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ).

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

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

## Output Format

For each test case, print a single integer — the minimum number of operations you have to perform. If it is impossible to make all elements of the array equal, print -1.

## Sample #1

### Sample Input #1

```
3
2
1 1
3
1 3 2
4
2 1 2 6
```

### Sample Output #1

```
0
-1
3
```

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: binary search, brute force, greedy, math
Difficulty: 2100
# Natlan Exploring

## Problem Description

You are exploring the stunning region of Natlan! This region consists of $ n $ cities, and each city is rated with an attractiveness $ a_i $ . A directed edge exists from City $ i $ to City $ j $ if and only if $ i < j $ and $ \gcd(a_i,a_j)\neq 1 $ , where $ \gcd(x, y) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ .

Starting from City $ 1 $ , your task is to determine the total number of distinct paths you can take to reach City $ n $ , modulo $ 998\,244\,353 $ . Two paths are different if and only if the set of cities visited is different.

## Input Format

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

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 2 \leq a_i \leq 10^6 $ ) — the attractiveness of each city.

## Output Format

Output the total number of distinct paths you can take to reach City $ n $ , modulo $ 998\,244\,353 $ .

## Sample #1

### Sample Input #1

```
5
2 6 3 4 6
```

### Sample Output #1

```
5
```

## Sample #2

### Sample Input #2

```
5
4 196 2662 2197 121
```

### Sample Output #2

```
2
```

## Sample #3

### Sample Input #3

```
7
3 6 8 9 11 12 20
```

### Sample Output #3

```
7
```

## Sample #4

### Sample Input #4

```
2
2 3
```

### Sample Output #4

```
0
```

## Hint

In the first example, the five paths are the following:

- City $ 1\rightarrow $ City $ 5 $
- City $ 1\rightarrow $ City $ 2\rightarrow $ City $ 5 $
- City $ 1\rightarrow $ City $ 2\rightarrow $ City $ 3\rightarrow $ City $ 5 $
- City $ 1\rightarrow $ City $ 2\rightarrow $ City $ 4\rightarrow $ City $ 5 $
- City $ 1\rightarrow $ City $ 4\rightarrow $ City $ 5 $

In the second example, the two paths are the following:

- City $ 1\rightarrow $ City $ 3\rightarrow $ City $ 5 $
- City $ 1\rightarrow $ City $ 2\rightarrow $ City $ 3\rightarrow $ City $ 5 $

## Limit



Time Limit
4.00s

Memory Limit
250.00MB

Tags: bitmasks, combinatorics, data structures, dp, math, number theory
Difficulty: 2000
# Superultra's Favorite Permutation

## Problem Description

Superultra, a little red panda, desperately wants primogems. In his dreams, a voice tells him that he must solve the following task to obtain a lifetime supply of primogems. Help Superultra!

Construct a permutation $ ^{\text{∗}} $ $ p $ of length $ n $ such that $ p_i + p_{i+1} $ is composite $ ^{\text{†}} $ over all $ 1 \leq i \leq n - 1 $ . If it's not possible, output $ -1 $ .

 $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

 $ ^{\text{†}} $ An integer $ x $ is composite if it has at least one other divisor besides $ 1 $ and $ x $ . For example, $ 4 $ is composite because $ 2 $ is a divisor.

## Input Format

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

Each test case contains an integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — the length of the permutation.

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, if it's not possible to construct $ p $ , output $ -1 $ on a new line. Otherwise, output $ n $ integers $ p_1, p_2, \ldots, p_n $ on a new line.

## Sample #1

### Sample Input #1

```
2
3
8
```

### Sample Output #1

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

## Hint

In the first example, it can be shown that all permutation of size $ 3 $ contain two adjacent elements whose sum is prime. For example, in the permutation $ [2,3,1] $ the sum $ 2+3=5 $ is prime.

In the second example, we can verify that the sample output is correct because $ 1+8 $ , $ 8+7 $ , $ 7+3 $ , $ 3+6 $ , $ 6+2 $ , $ 2+4 $ , and $ 4+5 $ are all composite. There may be other constructions that are correct.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, math, number theory
Difficulty: 1000
# Intercepted Inputs

## Problem Description

To help you prepare for your upcoming Codeforces contest, Citlali set a grid problem and is trying to give you a $ n $ by $ m $ grid through your input stream. Specifically, your input stream should contain the following:

- The first line contains two integers $ n $ and $ m $ — the dimensions of the grid.
- The following $ n $ lines contain $ m $ integers each — the values of the grid.

However, someone has intercepted your input stream, shuffled all given integers, and put them all on one line! Now, there are $ k $ integers all on one line, and you don't know where each integer originally belongs. Instead of asking Citlali to resend the input, you decide to determine the values of $ n $ and $ m $ yourself.

Output any possible value of $ n $ and $ m $ that Citlali could have provided.

## 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 $ k $ ( $ 3 \leq k \leq 2 \cdot 10^5 $ ) — the total number of inputs in your input stream.

The following line of each test case contains $ k $ integers $ a_1, a_2, \ldots, a_k $ ( $ 1 \leq a_i \leq k $ ) — the shuffled inputs of your input stream. It is guaranteed that $ n $ and $ m $ are contained within the $ k $ integers.

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

## Output Format

For each test case, output two integers, one possible value of $ n $ and $ m $ . If multiple possible answers exist, output any.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
1 1
3 3
2 3
4 1
1 6
```

## Hint

In the first test case, the initial input could have been the following:

1 1

2

In the second test case, the initial input could have been the following:

3 3

4 5 6

7 8 9

9 10 11

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, implementation
Difficulty: 800
# Twice

## Problem Description

Kinich wakes up to the start of a new day. He turns on his phone, checks his mailbox, and finds a mysterious present. He decides to unbox the present.

Kinich unboxes an array $ a $ with $ n $ integers. Initially, Kinich's score is $ 0 $ . He will perform the following operation any number of times:

- Select two indices $ i $ and $ j $ $ (1 \leq i < j \leq n) $ such that neither $ i $ nor $ j $ has been chosen in any previous operation and $ a_i = a_j $ . Then, add $ 1 $ to his score.

Output the maximum score Kinich can achieve after performing the aforementioned operation any number of times.

## Input Format

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

The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 20 $ ) — the length of $ a $ .

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

## Output Format

For each test case, output the maximum score achievable on a new line.

## Sample #1

### Sample Input #1

```
5
1
1
2
2 2
2
1 2
4
1 2 3 1
6
1 2 3 1 2 3
```

### Sample Output #1

```
0
1
0
1
3
```

## Hint

In the first and third testcases, Kinich cannot perform any operations.

In the second testcase, Kinich can perform one operation with $ i=1 $ and $ j=2 $ .

In the fourth testcase, Kinich can perform one operation with $ i=1 $ and $ j=4 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: implementation
Difficulty: 800
# XORificator 3000

## Problem Description

Alice has been giving gifts to Bob for many years, and she knows that what he enjoys the most is performing [bitwise XOR](http://tiny.cc/xor_wiki_eng) of interesting integers. Bob considers a positive integer $ x $ to be interesting if it satisfies $ x \not\equiv k (\bmod 2^i) $ . Therefore, this year for his birthday, she gifted him a super-powerful "XORificator 3000", the latest model.

Bob was very pleased with the gift, as it allowed him to instantly compute the XOR of all interesting integers in any range from $ l $ to $ r $ , inclusive. After all, what else does a person need for happiness? Unfortunately, the device was so powerful that at one point it performed XOR with itself and disappeared. Bob was very upset, and to cheer him up, Alice asked you to write your version of the "XORificator".

## Input Format

The first line of input contains a single integer $ t $ $ (1 \leq t \leq 10^4) $ — the number of XOR queries on the segment. The following $ t $ lines contain the queries, each consisting of the integers $ l $ , $ r $ , $ i $ , $ k $ $ (1 \leq l \leq r \leq 10^{18} $ , $ 0 \leq i \leq 30 $ , $ 0 \leq k < 2^i) $ .

## Output Format

For each query, output a single integer — the XOR of all integers $ x $ in the range $ [l, r] $ such that $ x \not\equiv k \mod 2^i $ .

## Sample #1

### Sample Input #1

```
6
1 3 1 0
2 28 3 7
15 43 1 0
57 2007 1 0
1010 1993 2 2
1 1000000000 30 1543
```

### Sample Output #1

```
2
2
13
0
4
1000000519
```

## Hint

In the first query, the interesting integers in the range $ [1, 3] $ are $ 1 $ and $ 3 $ , so the answer will be $ 1 \oplus 3 = 2 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: bitmasks, dp, number theory, two pointers
Difficulty: 1900
# I Love 1543

## Problem Description

One morning, Polycarp woke up and realized that $ 1543 $ is the most favorite number in his life.

The first thing that Polycarp saw that day as soon as he opened his eyes was a large wall carpet of size $ n $ by $ m $ cells; $ n $ and $ m $ are even integers. Each cell contains one of the digits from $ 0 $ to $ 9 $ .

Polycarp became curious about how many times the number $ 1543 $ would appear in all layers $ ^{\text{∗}} $ of the carpet when traversed clockwise.

 $ ^{\text{∗}} $ The first layer of a carpet of size $ n \times m $ is defined as a closed strip of length $ 2 \cdot (n+m-2) $ and thickness of $ 1 $ element, surrounding its outer part. Each subsequent layer is defined as the first layer of the carpet obtained by removing all previous layers from the original carpet.

## Input Format

The first line of the input contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The following lines describe the test cases.

The first line of each test case contains a pair of numbers $ n $ and $ m $ ( $ 2 \leq n, m \leq 10^3 $ , $ n, m $ — even integers).

This is followed by $ n $ lines of length $ m $ , consisting of digits from $ 0 $ to $ 9 $ — the description of the carpet.

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

## Output Format

For each test case, output a single number — the total number of times $ 1543 $ appears in all layers of the carpet in the order of traversal clockwise.

## Sample #1

### Sample Input #1

```
8
2 4
1543
7777
2 4
7154
8903
2 4
3451
8888
2 2
54
13
2 2
51
43
2 6
432015
512034
4 4
5431
1435
5518
7634
6 4
5432
1152
4542
2432
2302
5942
```

### Sample Output #1

```
1
1
0
1
0
2
2
2
```

## Hint

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2036D/997bfe25a98d4cf2f508d78ff1490796ddf33705.png) Occurrences of $ 1543 $ in the seventh example. Different layers are colored in different colors.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, implementation, matrices
Difficulty: 1300
# Anya and 1100

## Problem Description

While rummaging through things in a distant drawer, Anya found a beautiful string $ s $ consisting only of zeros and ones.

Now she wants to make it even more beautiful by performing $ q $ operations on it.

Each operation is described by two integers $ i $ ( $ 1 \le i \le |s| $ ) and $ v $ ( $ v \in \{0, 1\} $ ) and means that the $ i $ -th character of the string is assigned the value $ v $ (that is, the assignment $ s_i = v $ is performed).

But Anya loves the number $ 1100 $ , so after each query, she asks you to tell her whether the substring "1100" is present in her string (i.e. there exist such $ 1 \le i \le |s| - 3 $ that $ s_{i}s_{i + 1}s_{i + 2}s_{i + 3} = \texttt{1100} $ ).

## Input Format

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

The first line of the test case contains the string $ s $ ( $ 1 \leq |s| \leq 2 \cdot 10^5 $ ), consisting only of the characters "0" and "1". Here $ |s| $ denotes the length of the string $ s $ .

The next line contains an integer $ q $ ( $ 1 \leq q \leq 2 \cdot 10^5 $ ) — the number of queries.

The following $ q $ lines contain two integers $ i $ ( $ 1 \leq i \leq |s| $ ) and $ v $ ( $ v \in \{0, 1\} $ ), describing the query.

It is guaranteed that the sum of $ |s| $ across all test cases does not exceed $ 2 \cdot 10^5 $ . It is also guaranteed that the sum of $ q $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each query, output "YES", if "1100" is present in Anya's string; otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Sample #1

### Sample Input #1

```
4
100
4
1 1
2 0
2 0
3 1
1100000
3
6 1
7 1
4 1
111010
4
1 1
5 0
4 1
5 0
0100
4
3 1
1 1
2 0
2 1
```

### Sample Output #1

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

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: brute force, implementation
Difficulty: 1100
# Startup

## Problem Description

Arseniy came up with another business plan — to sell soda from a vending machine! For this, he purchased a machine with $ n $ shelves, as well as $ k $ bottles, where the $ i $ -th bottle is characterized by the brand index $ b_i $ and the cost $ c_i $ .

You can place any number of bottles on each shelf, but all bottles on the same shelf must be of the same brand.

Arseniy knows that all the bottles he puts on the shelves of the machine will be sold. Therefore, he asked you to calculate the maximum amount he can earn.

## Input Format

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

The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n, k \le 2 \cdot 10^5 $ ), where $ n $ is the number of shelves in the machine, and $ k $ is the number of bottles available to Arseniy.

The next $ k $ lines contain two integers $ b_i $ and $ c_i $ ( $ 1 \le b_i \le k, 1 \le c_i \le 1000 $ ) — the brand and cost of the $ i $ -th bottle.

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

## Output Format

For each test case, output one integer — the maximum amount that Arseniy can earn.

## Sample #1

### Sample Input #1

```
4
3 3
2 6
2 7
1 15
1 3
2 6
2 7
1 15
6 2
1 7
2 5
190000 1
1 1000
```

### Sample Output #1

```
28
15
12
1000
```

## Hint

In the first test case, Arseniy has $ 3 $ shelves in the vending machine. He can place, for example, two bottles of the brand $ 2 $ on the first shelf and a bottle of the brand $ 1 $ on the second shelf. Then the total cost of the bottles would be $ 6 + 7 + 15 = 28 $ .

In the second test case, he has only one shelf. It is not difficult to show that the optimal option is to place a bottle of the brand $ 1 $ on it. Then the total cost will be $ 15 $ .

In the third test case, he has as many as $ 6 $ shelves, so he can place all available bottles with a total cost of $ 7 + 5 = 12 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: greedy, sortings
Difficulty: 800
# Quintomania

## Problem Description

Boris Notkin composes melodies. He represents them as a sequence of notes, where each note is encoded as an integer from $ 0 $ to $ 127 $ inclusive. The interval between two notes $ a $ and $ b $ is equal to $ |a - b| $ semitones.

Boris considers a melody perfect if the interval between each two adjacent notes is either $ 5 $ semitones or $ 7 $ semitones.

After composing his latest melodies, he enthusiastically shows you his collection of works. Help Boris Notkin understand whether his melodies are perfect.

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of melodies.

Each melody is described by two lines.

The first line contains an integer $ n $ ( $ 2 \leq n \leq 50 $ ) — the number of notes in the melody.

The second line contains $ n $ integers $ a_{1}, a_{2}, \dots, a_{n} $ ( $ 0 \leq a_{i} \leq 127 $ ) — the notes of the melody.

## Output Format

For each melody, output "YES", if it is perfect; otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Sample #1

### Sample Input #1

```
8
2
114 109
2
17 10
3
76 83 88
8
38 45 38 80 85 92 99 106
5
63 58 65 58 65
8
117 124 48 53 48 43 54 49
5
95 102 107 114 121
10
72 77 82 75 70 75 68 75 68 75
```

### Sample Output #1

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

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: implementation
Difficulty: 800
# Monster

## Problem Description

Man, this Genshin boss is so hard. Good thing they have a top-up of $ 6 $ coins for only $  \$4.99 $ . I should be careful and spend no more than I need to, lest my mom catches me...



You are fighting a monster with $ z $ health using a weapon with $ d $ damage. Initially, $ d=0 $ . You can perform the following operations.

- Increase $ d $ — the damage of your weapon by $ 1 $ , costing $ x $ coins.
- Attack the monster, dealing $ d $ damage and costing $ y $ coins.

You cannot perform the first operation for more than $ k $ times in a row.

Find the minimum number of coins needed to defeat the monster by dealing at least $ z $ damage.

## Input Format

The first line contains a single integer $ t $ ( $ 1\le t\le 100 $ ) — the number of test cases.

The only line of each test case contains 4 integers $ x $ , $ y $ , $ z $ , and $ k $ ( $ 1\leq x, y, z, k\leq 10^8 $ ) — the first operation's cost, the second operation's cost, the monster's health, and the limitation on the first operation.

## Output Format

For each test case, output the minimum number of coins needed to defeat the monster.

## Sample #1

### Sample Input #1

```
4
2 3 5 5
10 20 40 5
1 60 100 10
60 1 100 10
```

### Sample Output #1

```
12
190
280
160
```

## Hint

In the first test case, $ x = 2 $ , $ y = 3 $ , $ z = 5 $ , and $ k = 5 $ . Here's a strategy that achieves the lowest possible cost of $ 12 $ coins:

- Increase damage by $ 1 $ , costing $ 2 $ coins.
- Increase damage by $ 1 $ , costing $ 2 $ coins.
- Increase damage by $ 1 $ , costing $ 2 $ coins.
- Attack the monster, dealing $ 3 $ damage, costing $ 3 $ coins.
- Attack the monster, dealing $ 3 $ damage, costing $ 3 $ coins.

You deal a total of $ 3 + 3 = 6 $ damage, defeating the monster who has $ 5 $ health. The total number of coins you use is $ 2 + 2 + 2 + 3 + 3 = 12 $ coins.

In the second test case, $ x = 10 $ , $ y = 20 $ , $ z = 40 $ , and $ k = 5 $ . Here's a strategy that achieves the lowest possible cost of $ 190 $ coins:

- Increase damage by $ 5 $ , costing $ 5\cdot x $ = $ 50 $ coins.
- Attack the monster once, dealing $ 5 $ damage, costing $ 20 $ coins.
- Increase damage by $ 2 $ , costing $ 2\cdot x $ = $ 20 $ coins.
- Attack the monster $ 5 $ times, dealing $ 5\cdot 7 = 35 $ damage, costing $ 5\cdot y $ = $ 100 $ coins.

You deal a total of $ 5 + 35 = 40 $ damage, defeating the monster who has exactly $ 40 $ health. The total number of coins you use is $ 50 + 20 + 20 + 100 = 190 $ coins.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, brute force, constructive algorithms, greedy, implementation, math, ternary search
Difficulty: 2300
# Yet Another Real Number Problem

## Problem Description

Three r there are's in strawberry.



You are given an array $ b $ of length $ m $ . You can perform the following operation any number of times (possibly zero):

- Choose two distinct indices $ i $ and $ j $ where $ \bf{1\le i < j\le m} $ and $ b_i $ is even, divide $ b_i $ by $ 2 $ and multiply $ b_j $ by $ 2 $ .

 Your task is to maximize the sum of the array after performing any number of such operations. Since it could be large, output this sum modulo $ 10^9+7 $ .Since this problem is too easy, you are given an array $ a $ of length $ n $ and need to solve the problem for each prefix of $ a $ .

In other words, denoting the maximum sum of $ b $ after performing any number of such operations as $ f(b) $ , you need to output $ f([a_1]) $ , $ f([a_1,a_2]) $ , $ \ldots $ , $ f([a_1,a_2,\ldots,a_n]) $ modulo $ 10^9+7 $ respectively.

## Input Format

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

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

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the starting values of array $ a $ .

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

## Output Format

For each test case, output $ n $ integers representing the answer for each prefix of $ a $ modulo $ 10^9+7 $ .

## Sample #1

### Sample Input #1

```
3
10
1 2 3 4 5 6 7 8 9 10
11
1 6 9 4 7 4 4 10 3 2 3
4
527792568 502211460 850237282 374773208
```

### Sample Output #1

```
1 3 8 13 46 59 126 149 1174 1311 
1 7 22 26 70 74 150 1303 1306 1308 1568 
527792568 83665723 399119771 773892979
```

## Hint

For each prefix in the first example, a possible array after operations is:

- $ [1] $ and the sum is $ 1 $ ;
- $ [1, 2] $ and the sum is $ 3 $ ;
- $ [1, 1, 6] $ and the sum is $ 8 $ ;
- $ [1, 1, 3, 8] $ and the sum is $ 13 $ ;
- $ [1, 1, 3, 1, 40] $ and the sum is $ 46 $ ;
- $ [1, 1, 3, 1, 5, 48] $ and the sum is $ 59 $ ;
- $ [1, 1, 3, 1, 5, 3, 112] $ and the sum is $ 126 $ ;
- $ [1, 1, 3, 1, 5, 3, 7, 128] $ and the sum is $ 149 $ ;
- $ [1, 1, 3, 1, 5, 3, 7, 1, 1152] $ and the sum is $ 1174 $ ;
- $ [1, 1, 3, 1, 5, 3, 7, 1, 9, 1280] $ and the sum is $ 1311 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, data structures, divide and conquer, greedy, implementation, math
Difficulty: 1800