yl-9/probench huggingface dataset:
# Adventurers

## Problem Description

Once, four Roman merchants met in a Roman mansion to discuss their trading plans. They faced the following problem: they traded the same type of goods, and if they traded in the same city, they would inevitably incur losses. They decided to divide up the cities between them where they would trade.

The map of Rome can be represented in this problem as a plane with certain points marked — the cities of the Roman Empire.

The merchants decided to choose a certain dividing point $ (x_0, y_0) $ . Then, in a city with coordinates $ (x_i, y_i) $ ,

- the first merchant sells goods if $ x_0 \le x_i $ and $ y_0 \le y_i $ ;
- the second merchant sells goods if $ x_0 > x_i $ and $ y_0 \le y_i $ ;
- the third merchant sells goods if $ x_0 \le x_i $ and $ y_0 > y_i $ ;
- the fourth merchant sells goods if $ x_0 > x_i $ and $ y_0 > y_i $ .

The merchants want to choose $ (x_0, y_0) $ in such a way as to maximize the smallest number of cities that any of them gets (i. e., as fair as possible). Please find such a point for them.

## Input Format

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 a single integer $ n $ ( $ 4 \le n \le 10^5 $ ) — the number of cities on the map.

Each of the next $ n $ lines contains two integers $ x_i, y_i $ ( $ -10^9 \le x_i, y_i \le 10^9 $ ) — the coordinates of the cities.

Note that some points may coincide. This is because some cities may be so close that they cannot be distinguished on the map at the given scale.

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

## Output Format

For each test case, in the first line, print a single integer $ k $ ( $ 0 \le k \le \frac{n}{4} $ ) — the maximum possible number of cities that each merchant can get at a minimum.

In the second line, print two integers $ x_0 $ and $ y_0 $ ( $ |x_0|, |y_0| \le 10^9 $ ) — the coordinates of the dividing point. If there are multiple suitable points, print any of them.

## Sample #1

### Sample Input #1

```
4
4
1 1
1 2
2 1
2 2
4
0 0
0 0
0 0
0 0
8
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
-2 1
-1 2
7
1 1
1 2
1 3
1 4
2 1
3 1
4 1
```

### Sample Output #1

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

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: binary search, data structures, greedy, sortings, ternary search, two pointers
Difficulty: 2100
# Move Back at a Cost

## Problem Description

You are given an array of integers $ a $ of length $ n $ . You can perform the following operation zero or more times:

- In one operation choose an index $ i $ ( $ 1 \le i \le n $ ), assign $ a_i := a_i + 1 $ , and then move $ a_i $ to the back of the array (to the rightmost position). For example, if $ a = [3, 5, 1, 9] $ , and you choose $ i = 2 $ , the array becomes $ [3, 1, 9, 6] $ .

Find the lexicographically smallest $ ^{\text{∗}} $ array you can get by performing these operations.

 $ ^{\text{∗}} $ An array $ c $ is lexicographically smaller than an array $ d $ if and only if one of the following holds:

- $ c $ is a prefix of $ d $ , but $ c \ne d $ ; or
- in the first position where $ c $ and $ d $ differ, the array $ c $ has a smaller element than the corresponding element in $ d $ .

## Input Format

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 contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ), the length of the array.

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

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

## Output Format

For each test case, print the lexicographically smallest array you can get.

## Sample #1

### Sample Input #1

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

### Sample Output #1

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

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, data structures, greedy, sortings
Difficulty: 1600
# Swap Columns and Find a Path

## Problem Description

There is a matrix consisting of $ 2 $ rows and $ n $ columns. The rows are numbered from $ 1 $ to $ 2 $ from top to bottom; the columns are numbered from $ 1 $ to $ n $ from left to right. Let's denote the cell on the intersection of the $ i $ -th row and the $ j $ -th column as $ (i,j) $ . Each cell contains an integer; initially, the integer in the cell $ (i,j) $ is $ a_{i,j} $ .

You can perform the following operation any number of times (possibly zero):

- choose two columns and swap them (i. e. choose two integers $ x $ and $ y $ such that $ 1 \le x < y \le n $ , then swap $ a_{1,x} $ with $ a_{1,y} $ , and then swap $ a_{2,x} $ with $ a_{2,y} $ ).

After performing the operations, you have to choose a path from the cell $ (1,1) $ to the cell $ (2,n) $ . For every cell $ (i,j) $ in the path except for the last, the next cell should be either $ (i+1,j) $ or $ (i,j+1) $ . Obviously, the path cannot go outside the matrix.

The cost of the path is the sum of all integers in all $ (n+1) $ cells belonging to the path. You have to perform the operations and choose a path so that its cost is maximum possible.

## Input Format

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

Each test case consists of three lines:

- the first line contains one integer $ n $ ( $ 1 \le n \le 5000 $ ) — the number of columns in the matrix;
- the second line contains $ n $ integers $ a_{1,1}, a_{1,2}, \ldots, a_{1,n} $ ( $ -10^5 \le a_{i,j} \le 10^5 $ ) — the first row of the matrix;
- the third line contains $ n $ integers $ a_{2,1}, a_{2,2}, \ldots, a_{2,n} $ ( $ -10^5 \le a_{i,j} \le 10^5 $ ) — the second row of the matrix.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

## Output Format

For each test case, print one integer — the maximum cost of a path you can obtain.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
-5
16
29
```

## Hint

Here are the explanations of the first three test cases of the example. The left matrix is the matrix given in the input, the right one is the state of the matrix after several column swaps (possibly zero). The optimal path is highlighted in green.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2046A/28e18d69b8340ab8e799138974c8a936f265ad5d.png)

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: greedy, sortings
Difficulty: 1200
# GCDDCG

## Problem Description

You are playing the Greatest Common Divisor Deck-Building Card Game (GCDDCG). There are $ N $ cards (numbered from $ 1 $ to $ N $ ). Card $ i $ has the value of $ A_i $ , which is an integer between $ 1 $ and $ N $ (inclusive).

The game consists of $ N $ rounds (numbered from $ 1 $ to $ N $ ). Within each round, you need to build two non-empty decks, deck $ 1 $ and deck $ 2 $ . A card cannot be inside both decks, and it is allowed to not use all $ N $ cards. In round $ i $ , the greatest common divisor (GCD) of the card values in each deck must equal $ i $ .

Your creativity point during round $ i $ is the product of $ i $ and the number of ways to build two valid decks. Two ways are considered different if one of the decks contains different cards.

Find the sum of creativity points across all $ N $ rounds. Since the sum can be very large, calculate the sum modulo $ 998\,244\,353 $ .

## Input Format

The first line consists of an integer $ N $ ( $ 2 \leq N \leq 200\,000) $ .

The second line consists of $ N $ integers $ A_i $ ( $ 1 \leq A_i \leq N $ ).

## Output Format

Output a single integer representing the sum of creativity points across all $ N $ rounds modulo $ 998\,244\,353 $ .

## Sample #1

### Sample Input #1

```
3
3 3 3
```

### Sample Output #1

```
36
```

## Sample #2

### Sample Input #2

```
4
2 2 4 4
```

### Sample Output #2

```
44
```

## Sample #3

### Sample Input #3

```
9
4 2 6 9 7 7 7 3 3
```

### Sample Output #3

```
10858
```

## Hint

Explanation for the sample input/output #1

The creativity point during each of rounds $ 1 $ and $ 2 $ is $ 0 $ .

During round $ 3 $ , there are $ 12 $ ways to build both decks. Denote $ B $ and $ C $ as the set of card numbers within deck $ 1 $ and deck $ 2 $ , respectively. The $ 12 $ ways to build both decks are:

- $ B = \{ 1 \}, C = \{ 2 \} $ ;
- $ B = \{ 1 \}, C = \{ 3 \} $ ;
- $ B = \{ 1 \}, C = \{ 2, 3 \} $ ;
- $ B = \{ 2 \}, C = \{ 1 \} $ ;
- $ B = \{ 2 \}, C = \{ 3 \} $ ;
- $ B = \{ 2 \}, C = \{ 1, 3 \} $ ;
- $ B = \{ 3 \}, C = \{ 1 \} $ ;
- $ B = \{ 3 \}, C = \{ 2 \} $ ;
- $ B = \{ 3 \}, C = \{ 1, 2 \} $ ;
- $ B = \{ 1, 2 \}, C = \{ 3 \} $ ;
- $ B = \{ 2, 3 \}, C = \{ 1 \} $ ; and
- $ B = \{ 1, 3 \}, C = \{ 2 \} $ .

Explanation for the sample input/output #2

For rounds $ 1 $ , $ 2 $ , $ 3 $ and $ 4 $ , there are $ 0 $ , $ 18 $ , $ 0 $ , and $ 2 $ ways to build both decks, respectively.

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Difficulty: 2900
# Xorderable Array

## Problem Description

You are given an array $ A $ of $ N $ integers: $ [A_1, A_2, \dots, A_N] $ .

The array $ A $ is  $ (p, q) $ -xorderable if it is possible to rearrange $ A $ such that for each pair $ (i, j) $ that satisfies $ 1 \leq i < j \leq N $ , the following conditions must be satisfied after the rearrangement: $ A_i \oplus p \leq A_j \oplus q $ and $ A_i \oplus q \leq A_j \oplus p $ . The operator $ \oplus $ represents the bitwise xor.

You are given another array $ X $ of length $ M $ : $ [X_1, X_2, \dots, X_M] $ . Calculate the number of pairs $ (u, v) $ where array $ A $ is $ (X_u, X_v) $ -xorderable for $ 1 \leq u < v \leq M $ .

## Input Format

The first line consists of two integers $ N $ $ M $ ( $ 2 \leq N, M \leq 200\,000) $ .

The second line consists of $ N $ integers $ A_i $ ( $ 0 \leq A_i < 2^{30}) $ .

The third line consists of $ M $ integers $ X_u $ ( $ 0 \leq X_u < 2^{30}) $ .

## Output Format

Output a single integer representing the number of pairs $ (u, v) $ where array $ A $ is $ (X_u, X_v) $ -xorderable for $ 1 \leq u < v \leq M $ .

## Sample #1

### Sample Input #1

```
3 4
0 3 0
1 2 1 1
```

### Sample Output #1

```
3
```

## Sample #2

### Sample Input #2

```
5 2
0 7 13 22 24
12 10
```

### Sample Output #2

```
1
```

## Sample #3

### Sample Input #3

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

### Sample Output #3

```
0
```

## Hint

Explanation for the sample input/output #1

The array $ A $ is $ (1, 1) $ -xorderable by rearranging the array $ A $ to $ [0, 0, 3] $ .

Explanation for the sample input/output #2

The array $ A $ is $ (12, 10) $ -xorderable by rearranging the array $ A $ to $ [13, 0, 7, 24, 22] $ .

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: bitmasks, data structures
Difficulty: 2600
# Microwavable Subsequence

## Problem Description

You are given an array of $ N $ integers: $ [A_1, A_2, \dots, A_N] $ .

A subsequence can be derived from an array by removing zero or more elements without changing the order of the remaining elements. For example, $ [2, 1, 2] $ , $ [3, 3] $ , $ [1] $ , and $ [3, 2, 1, 3, 2] $ are subsequences of array $ [3, 2, 1, 3, 2] $ , while $ [1, 2, 3] $ is not a subsequence of array $ [3, 2, 1, 3, 2] $ .

A subsequence is microwavable if the subsequence consists of at most two distinct values and each element differs from its adjacent elements. For example, $ [2, 1, 2] $ , $ [3, 2, 3, 2] $ , and $ [1] $ are microwavable, while $ [3, 3] $ and $ [3, 2, 1, 3, 2] $ are not microwavable.

Denote a function $ f(x, y) $ as the length of the longest microwavable subsequence of array $ A $ such that each element within the subsequence is either $ x $ or $ y $ . Find the sum of $ f(x, y) $ for all $ 1 \leq x < y \leq M $ .

## Input Format

The first line consists of two integers $ N $ $ M $ ( $ 1 \leq N, M \leq 300\,000 $ ).

The second line consists of $ N $ integers $ A_i $ ( $ 1 \leq A_i \leq M $ ).

## Output Format

Output a single integer representing the sum of $ f(x, y) $ for all $ 1 \leq x < y \leq M $ .

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
13
```

## Sample #2

### Sample Input #2

```
3 3
1 1 1
```

### Sample Output #2

```
2
```

## Hint

Explanation for the sample input/output #1

The value of $ f(1, 2) $ is $ 3 $ , taken from the subsequence $ [2, 1, 2] $ that can be obtained by removing $ A_1 $ and $ A_4 $ . The value of $ f(1, 3) $ is $ 3 $ , taken from the subsequence $ [3, 1, 3] $ that can be obtained by removing $ A_2 $ and $ A_5 $ . The value of $ f(2, 3) $ is $ 4 $ , taken from the subsequence $ [3, 2, 3, 2] $ that can be obtained by removing $ A_3 $ . The value of $ f(1, 4) $ , $ f(2, 4) $ , and $ f(3, 4) $ are all $ 1 $ .

Explanation for the sample input/output #2

The value of $ f(1, 2) $ and $ f(1, 3) $ are both $ 1 $ , while the value of $ f(2, 3) $ is $ 0 $ .

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: data structures
Difficulty: 2100
# Missing Separators

## Problem Description

You have a dictionary, which is a list of distinct words sorted in alphabetical order. Each word consists of uppercase English letters.

You want to print this dictionary. However, there is a bug with the printing system, and all words in the list are printed next to each other without any separators between words. Now, you ended up with a string $ S $ that is a concatenation of all the words in the dictionary in the listed order.

Your task is to reconstruct the dictionary by splitting $ S $ into one or more words. Note that the reconstructed dictionary must consist of distinct words sorted in alphabetical order. Furthermore, you want to maximize the number of words in the dictionary. If there are several possible dictionaries with the maximum number of words, you can choose any of them.

## Input Format

A single line consisting of a string $ S $ ( $ 1 \leq |S| \leq 5000) $ . String $ S $ consists of only uppercase English letters.

## Output Format

First, output an integer in a single line representing the maximum number of the words in the reconstructed dictionary. Denote this number as $ n $ .

Then, output $ n $ lines, each containing a single string representing the word. The words must be distinct, and the list must be sorted alphabetically. The concatenation of the words in the listed order must equal $ S $ .

If there are several possible dictionaries with the maximum number of words, output any of them.

## Sample #1

### Sample Input #1

```
ABACUS
```

### Sample Output #1

```
4
A
BA
C
US
```

## Sample #2

### Sample Input #2

```
AAAAAA
```

### Sample Output #2

```
3
A
AA
AAA
```

## Sample #3

### Sample Input #3

```
EDCBA
```

### Sample Output #3

```
1
EDCBA
```

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: dp, sortings, string suffix structures, strings
Difficulty: 2200
# Saraga

## Problem Description

The word saraga is an abbreviation of sarana olahraga, an Indonesian term for a sports facility. It is created by taking the prefix sara of the word sarana and the suffix ga of the word olahraga. Interestingly, it can also be created by the prefix sa of the word sarana and the suffix raga of the word olahraga.

An abbreviation of two strings $ S $ and $ T $ is interesting if there are at least two different ways to split the abbreviation into two non-empty substrings such that the first substring is a prefix of $ S $ and the second substring is a suffix of $ T $ .

You are given two strings $ S $ and $ T $ . You want to create an interesting abbreviation of strings $ S $ and $ T $ with minimum length, or determine if it is impossible to create an interesting abbreviation.

## Input Format

The first line consists of a string $ S $ ( $ 1 \leq |S| \leq 200\,000 $ ).

The second line consists of a string $ T $ ( $ 1 \leq |T| \leq 200\,000 $ ).

Both strings $ S $ and $ T $ only consist of lowercase English letters.

## Output Format

If it is impossible to create an interesting abbreviation, output -1.

Otherwise, output a string in a single line representing an interesting abbreviation of strings $ S $ and $ T $ with minimum length. If there are multiple solutions, output any of them.

## Sample #1

### Sample Input #1

```
sarana
olahraga
```

### Sample Output #1

```
saga
```

## Sample #2

### Sample Input #2

```
berhiber
wortelhijau
```

### Sample Output #2

```
berhijau
```

## Sample #3

### Sample Input #3

```
icpc
icpc
```

### Sample Output #3

```
icpc
```

## Sample #4

### Sample Input #4

```
icpc
jakarta
```

### Sample Output #4

```
-1
```

## Hint

Explanation for the sample input/output #1

You can split saga into s and aga, or sa and ga. The abbreviation saraga is interesting, but saga has a smaller length.

Explanation for the sample input/output #2

The abbreviation belhijau is also interesting with minimum length, so it is another valid solution.

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: greedy, strings
Difficulty: 1400
# ICPC Square

## Problem Description

ICPC Square is a hotel provided by the ICPC Committee for the accommodation of the participants. It consists of $ N $ floors (numbered from $ 1 $ to $ N $ ). This hotel has a very unique elevator. If a person is currently at floor $ x $ , by riding the elevator once, they can go to floor $ y $ if and only if $ y $ is a multiple of $ x $ and $ y - x \leq D $ .

You are currently at floor $ S $ . You want to go to the highest possible floor by riding the elevator zero or more times. Determine the highest floor you can reach.

## Input Format

A single line consisting of three integers $ N $ $ D $ $ S $ ( $ 2 \leq N \leq 10^{12}; 1 \leq D \leq N - 1; 1 \leq S \leq N $ ).

## Output Format

Output a single integer representing the highest floor you can reach by riding the elevator zero or more times.

## Sample #1

### Sample Input #1

```
64 35 3
```

### Sample Output #1

```
60
```

## Sample #2

### Sample Input #2

```
2024 2023 1273
```

### Sample Output #2

```
1273
```

## Hint

Explanation for the sample input/output #1

First, ride the elevator from floor $ 3 $ to floor $ 15 $ . This is possible because $ 15 $ is a multiple of $ 3 $ and $ 15 - 3 \leq 35 $ . Then, ride the elevator from floor $ 15 $ to floor $ 30 $ . This is possible because $ 30 $ is a multiple of $ 15 $ and $ 30 - 15 \leq 35 $ . Finally, ride the elevator from floor $ 30 $ to floor $ 60 $ . This is possible because $ 60 $ is a multiple of $ 30 $ and $ 60 - 30 \leq 35 $ .

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: math, number theory
Difficulty: 2000
# Scrambled Scrabble

## Problem Description

You are playing a word game using a standard set of $ 26 $ uppercase English letters: A — Z. In this game, you can form vowels and consonants as follows.

- The letters A, E, I, O, and U can only form a vowel.
- The letter Y can form either a vowel or a consonant.
- Each of the remaining letters other than A, E, I, O, U, and Y can only form a consonant.
- The string NG can form a single consonant when concatenated together.

Denote a syllable as a concatenation of a consonant, a vowel, and a consonant in that order. A word is a concatenation of one or more syllables.

You are given a string $ S $ and you want to create a word from it. You are allowed to delete zero or more letters from $ S $ and rearrange the remaining letters to form the word. Find the length of the longest word that can be created, or determine if no words can be created.

## Input Format

A single line consisting of a string $ S $ ( $ 1 \leq |S| \leq 5000 $ ). The string $ S $ consists of only uppercase English letters.

## Output Format

If a word cannot be created, output 0. Otherwise, output a single integer representing the length of longest word that can be created.

## Sample #1

### Sample Input #1

```
ICPCJAKARTA
```

### Sample Output #1

```
9
```

## Sample #2

### Sample Input #2

```
NGENG
```

### Sample Output #2

```
5
```

## Sample #3

### Sample Input #3

```
YYY
```

### Sample Output #3

```
3
```

## Sample #4

### Sample Input #4

```
DANGAN
```

### Sample Output #4

```
6
```

## Sample #5

### Sample Input #5

```
AEIOUY
```

### Sample Output #5

```
0
```

## Hint

Explanation for the sample input/output #1

A possible longest word is JAKCARTAP, consisting of the syllables JAK, CAR, and TAP.

Explanation for the sample input/output #2

The whole string $ S $ is a word consisting of one syllable which is the concatenation of the consonant NG, the vowel E, and the consonant NG.

Explanation for the sample input/output #3

The whole string $ S $ is a word consisting of one syllable which is the concatenation of the consonant Y, the vowel Y, and the consonant Y.

Explanation for the sample input/output #4

The whole string $ S $ is a word consisting of two syllables: DAN and GAN.

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: brute force, greedy
Difficulty: 1700
# Hard Demon Problem

## Problem Description

Swing is opening a pancake factory! A good pancake factory must be good at flattening things, so Swing is going to test his new equipment on 2D matrices.

Swing is given an $ n \times n $ matrix $ M $ containing positive integers. He has $ q $ queries to ask you.

For each query, he gives you four integers $ x_1 $ , $ y_1 $ , $ x_2 $ , $ y_2 $ and asks you to flatten the submatrix bounded by $ (x_1, y_1) $ and $ (x_2, y_2) $ into an array $ A $ . Formally, $ A = [M_{(x1,y1)}, M_{(x1,y1+1)}, \ldots, M_{(x1,y2)}, M_{(x1+1,y1)}, M_{(x1+1,y1+1)}, \ldots, M_{(x2,y2)}] $ .

The following image depicts the flattening of a submatrix bounded by the red dotted lines. The orange arrows denote the direction that the elements of the submatrix are appended to the back of $ A $ , and $ A $ is shown at the bottom of the image.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2044H/75bdaf28c8054bf099c5d719d2a33cac51011434.png)Afterwards, he asks you for the value of $ \sum_{i=1}^{|A|} A_i \cdot i $ (sum of $ A_i \cdot i $ over all $ i $ ).

## Input Format

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

The first line of each test contains two integers $ n $ and $ q $ ( $ 1 \leq n \leq 2000, 1 \leq q \leq 10^6 $ ) — the length of $ M $ and the number of queries.

The following $ n $ lines contain $ n $ integers each, the $ i $ 'th of which contains $ M_{(i,1)}, M_{(i,2)}, \ldots, M_{(i,n)} $ ( $ 1 \leq M_{(i, j)} \leq 10^6 $ ).

The following $ q $ lines contain four integers $ x_1 $ , $ y_1 $ , $ x_2 $ , and $ y_2 $ ( $ 1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq n $ ) — the bounds of the query.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ and the sum of $ q $ over all test cases does not exceed $ 10^6 $ .

## Output Format

For each test case, output the results of the $ q $ queries on a new line.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
500 42 168 
14 42 5
```

## Hint

In the second query of the first test case, $ A = [9, 5, 5, 2] $ . Therefore, the sum is $ 1 \cdot 9 + 2 \cdot 5 + 3 \cdot 5 + 4 \cdot 2 = 42 $ .

## Limit



Time Limit
3.50s

Memory Limit
500.00MB

Tags: constructive algorithms, data structures, dp, implementation, math
Difficulty: 2100