apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let $$$f$$$($$$x$$$) be the floor of the binary logarithm of $$$x$$$. In other words, $$$f$$$($$$x$$$) is largest non-negative integer $$$y$$$, such that $$$2^y$$$ does not exceed $$$x$$$.

Let $$$g$$$($$$x$$$) be the floor of the logarithm of $$$x$$$ with base $$$f$$$($$$x$$$). In other words, $$$g$$$($$$x$$$) is the largest non-negative integer $$$z$$$, such that $$${f(x)}^{z}$$$ does not exceed $$$x$$$.

You are given $$$q$$$ queries. The $$$i$$$-th query consists of two integers $$$l_i$$$ and $$$r_i$$$. The answer to the query is the sum of $$$g$$$($$$k$$$) across all integers $$$k$$$, such that $$$l_i \leq k \leq r_i$$$. Since the answers might be large, print them modulo $$${10^9 + 7}$$$.

## Input Format
The first line contains a single integer $$$q$$$ — the number of queries ($$$1 \leq q \leq 10^5$$$).

The next $$$q$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ — the bounds of the $$$i$$$-th query ($$$4 \leq l_i \leq r_i \leq 10^{18}$$$).

## Output Format
For each query, output the answer to the query modulo $$$10^9 + 7$$$.

## Examples
```input
12
4 6
4 7
4 8
4 100000
179 1000000000000000000
57 179
4 201018959
7 201018960
729 50624
728 50624
728 50625
729 50625
```
```output
6
8
9
348641
41949982
246
1
0
149688
149690
149694
149692
```

## Note
The table below contains the values of the functions $$$f$$$($$$x$$$) and $$$g$$$($$$x$$$) for all $$$x$$$ such that $$$1 \leq x \leq 8$$$.

$$$x$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$$$$f$$$$$$0$$$$$$1$$$$$$1$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$3$$$$$$g$$$$$$-$$$$$$-$$$$$$-$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$1$$$

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a sequence of integers $$$a$$$ of length $$$2n$$$. You have to split these $$$2n$$$ integers into $$$n$$$ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $$$a$$$ should become the $$$x$$$ or $$$y$$$ coordinate of exactly one point. Note that some points can be equal.

After the points are formed, you have to choose a path $$$s$$$ that starts from one of these points, ends at one of these points, and visits all $$$n$$$ points at least once.

The length of path $$$s$$$ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is defined as $$$|x_1-x_2| + |y_1-y_2|$$$.

Your task is to form $$$n$$$ points and choose a path $$$s$$$ in such a way that the length of path $$$s$$$ is minimized.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of points to be formed.

The next line contains $$$2n$$$ integers $$$a_1, a_2, \dots, a_{2n}$$$ ($$$0 \le a_i \le 1\,000$$$) — the description of the sequence $$$a$$$.

## Output Format
For each testcase, print the minimum possible length of path $$$s$$$ in the first line.

In the $$$i$$$-th of the following $$$n$$$ lines, print two integers $$$x_i$$$ and $$$y_i$$$ — the coordinates of the point that needs to be visited at the $$$i$$$-th position.

If there are multiple answers, print any of them.

## Examples
```input
2
2
15 1 10 5
3
10 30 20 20 30 10
```
```output
9
10 1
15 5
20
20 20
10 30
10 30
```

## Note
In the first testcase, for instance, you can form points $$$(10, 1)$$$ and $$$(15, 5)$$$ and start the path $$$s$$$ from the first point and end it at the second point. Then the length of the path will be $$$|10 - 15| + |1 - 5| = 5 + 4 = 9$$$.

In the second testcase, you can form points $$$(20, 20)$$$, $$$(10, 30)$$$, and $$$(10, 30)$$$, and visit them in that exact order. Then the length of the path will be $$$|20 - 10| + |20 - 30| + |10 - 10| + |30 - 30| = 10 + 10 + 0 + 0 = 20$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
A ticket is a non-empty string of digits from $$$1$$$ to $$$9$$$.

A lucky ticket is such a ticket that:

- it has an even length;
- the sum of digits in the first half is equal to the sum of digits in the second half.

You are given $$$n$$$ ticket pieces $$$s_1, s_2, \dots, s_n$$$. How many pairs $$$(i, j)$$$ (for $$$1 \le i, j \le n$$$) are there such that $$$s_i + s_j$$$ is a lucky ticket? Note that it's possible that $$$i=j$$$.

Here, the + operator denotes the concatenation of the two strings. For example, if $$$s_i$$$ is 13, and $$$s_j$$$ is 37, then $$$s_i + s_j$$$ is 1337.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of ticket pieces.

The second line contains $$$n$$$ non-empty strings $$$s_1, s_2, \dots, s_n$$$, each of length at most $$$5$$$ and consisting only of digits from $$$1$$$ to $$$9$$$.

## Output Format
Print a single integer — the number of pairs $$$(i, j)$$$ (for $$$1 \le i, j \le n$$$) such that $$$s_i + s_j$$$ is a lucky ticket.

## Examples
```input
10
5 93746 59 3746 593 746 5937 46 59374 6
```
```output
20
```
-----
```input
5
2 22 222 2222 22222
```
```output
13
```
-----
```input
3
1 1 1
```
```output
9
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$.

Your task is to construct an array $$$b_1, b_2, \dots, b_n$$$ such that:

- every integer from $$$0$$$ to $$$n-1$$$ appears in $$$b$$$ exactly once;
- for every $$$i$$$ from $$$1$$$ to $$$n-1$$$, $$$b_i \oplus b_{i+1} = a_i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operator).

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \le a_i \le 2n$$$).

Additional constraint on the input: it's always possible to construct at least one valid array $$$b$$$ from the given sequence $$$a$$$.

## Output Format
Print $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$. If there are multiple such arrays, you may print any of them.

## Examples
```input
4
2 1 2
```
```output
0 2 3 1
```
-----
```input
6
1 6 1 4 1
```
```output
2 3 5 4 0 1
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Let's call an array $$$a$$$ of $$$n$$$ non-negative integers fancy if the following conditions hold:

- at least one from the numbers $$$x$$$, $$$x + 1$$$, ..., $$$x+k-1$$$ appears in the array;
- consecutive elements of the array differ by at most $$$k$$$ (i.e. $$$|a_i-a_{i-1}| \le k$$$ for each $$$i \in [2, n]$$$).

You are given $$$n$$$, $$$x$$$ and $$$k$$$. Your task is to calculate the number of fancy arrays of length $$$n$$$. Since the answer can be large, print it modulo $$$10^9+7$$$.

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

The only line of each test case contains three integers $$$n$$$, $$$x$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$; $$$0 \le x \le 40$$$).

## Output Format
For each test case, print a single integer — the number of fancy arrays of length $$$n$$$, taken modulo $$$10^9+7$$$.

## Examples
```input
4
3 0 1
1 4 25
4 7 2
1000000000 40 1000000000
```
```output
9
25
582
514035484
```

## Note
In the first test case of the example, the following arrays are fancy:

- $$$[0, 0, 0]$$$;
- $$$[0, 0, 1]$$$;
- $$$[0, 1, 0]$$$;
- $$$[0, 1, 1]$$$;
- $$$[0, 1, 2]$$$;
- $$$[1, 0, 0]$$$;
- $$$[1, 0, 1]$$$;
- $$$[1, 1, 0]$$$;
- $$$[2, 1, 0]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Berland starts to seize the initiative on the war with Flatland. To drive the enemy from their native land, the berlanders need to know exactly how many more flatland soldiers are left in the enemy's reserve. Fortunately, the scouts captured an enemy in the morning, who had a secret encrypted message with the information the berlanders needed so much.

The captured enemy had an array of positive integers. Berland intelligence have long been aware of the flatland code: to convey the message, which contained a number m, the enemies use an array of integers a. The number of its subarrays, in which there are at least k equal numbers, equals m. The number k has long been known in the Berland army so General Touristov has once again asked Corporal Vasya to perform a simple task: to decipher the flatlanders' message.

Help Vasya, given an array of integers a and number k, find the number of subarrays of the array of numbers a, which has at least k equal numbers.

Subarray a[i... j] (1 ≤ i ≤ j ≤ n) of array a = (a1, a2, ..., an) is an array, made from its consecutive elements, starting from the i-th one and ending with the j-th one: a[i... j] = (ai, ai + 1, ..., aj).

## Input Format
The first line contains two space-separated integers n, k (1 ≤ k ≤ n ≤ 4·105), showing how many numbers an array has and how many equal numbers the subarrays are required to have, correspondingly.

The second line contains n space-separated integers ai (1 ≤ ai ≤ 109) — elements of the array.

## Output Format
Print the single number — the number of such subarrays of array a, that they have at least k equal integers.

Please do not use the %lld specifier to read or write 64-bit integers in С++. In is preferred to use the cin, cout streams or the %I64d specifier.

## Examples
```input
4 2
1 2 1 2
```
```output
3
```
-----
```input
5 3
1 2 1 1 3
```
```output
2
```
-----
```input
3 1
1 1 1
```
```output
6
```

## Note
In the first sample are three subarrays, containing at least two equal numbers: (1,2,1), (2,1,2) and (1,2,1,2).

In the second sample are two subarrays, containing three equal numbers: (1,2,1,1,3) and (1,2,1,1).

In the third sample any subarray contains at least one 1 number. Overall they are 6: (1), (1), (1), (1,1), (1,1) and (1,1,1).

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ positive integers and a score. If your score is greater than or equal to $$$a_i$$$, then you can increase your score by $$$a_i$$$ and remove $$$a_i$$$ from the array.

For each index $$$i$$$, output the maximum number of additional array elements that you can remove if you remove $$$a_i$$$ and then set your score to $$$a_i$$$. Note that the removal of $$$a_i$$$ should not be counted in the answer.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases. The description of the test cases follows.

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

The second line of each test case 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, output $$$n$$$ integers, the $$$i$$$-th of which denotes the maximum number of additional array elements that you can remove if you remove $$$a_i$$$ from the array and then set your score to $$$a_i$$$.

## Examples
```input
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000
```
```output
4 3 0 3 1 
1 0 2 
0 
4 4 4 4 4
```

## Note
In the first test case, the answers are as follows:

If we start with $$$i=4$$$, our initial score is $$$a_4=4$$$ and $$$a=[20,5,1,2]$$$. We can remove $$$3$$$ additional elements in the following order:

1. Since $$$4 \ge 1$$$, we can remove $$$1$$$ and our score becomes $$$5$$$. After this, $$$a=[20,5,2]$$$.
2. Since $$$5 \ge 5$$$, we can remove $$$5$$$ and our score becomes $$$10$$$. After this, $$$a=[20,2]$$$.
3. Since $$$10 \ge 2$$$, we can remove $$$2$$$ and our score becomes $$$12$$$. After this, $$$a=[20]$$$.

If we start with $$$i=1$$$ we can remove all remaining elements in the array, so the answer is $$$4$$$.

If we start with $$$i=2$$$, we can remove $$$3$$$ additional elements in the following order: $$$1$$$, $$$4$$$, $$$2$$$.

If we start with $$$i=3$$$, we can remove no additional elements.

If we start with $$$i=5$$$, we can remove $$$1$$$ additional element: $$$1$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ positive integers. In one operation, you must pick some $$$(i, j)$$$ such that $$$1\leq i < j\leq |a|$$$ and append $$$|a_i - a_j|$$$ to the end of the $$$a$$$ (i.e. increase $$$n$$$ by $$$1$$$ and set $$$a_n$$$ to $$$|a_i - a_j|$$$). Your task is to minimize and print the minimum value of $$$a$$$ after performing $$$k$$$ operations.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2\le n\le 2\cdot 10^3$$$, $$$1\le k\le 10^9$$$) — the length of the array and the number of operations you should perform.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^{18}$$$) — the elements of the array $$$a$$$.

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

## Output Format
For each test case, print a single integer — the smallest possible value of the minimum of array $$$a$$$ after performing $$$k$$$ operations.

## Examples
```input
4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000
```
```output
1
0
3
500000000000000000
```

## Note
In the first test case, after any $$$k=2$$$ operations, the minimum value of $$$a$$$ will be $$$1$$$.

In the second test case, an optimal strategy is to first pick $$$i=1, j=2$$$ and append $$$|a_1 - a_2| = 3$$$ to the end of $$$a$$$, creating $$$a=[7, 4, 15, 12, 3]$$$. Then, pick $$$i=3, j=4$$$ and append $$$|a_3 - a_4| = 3$$$ to the end of $$$a$$$, creating $$$a=[7, 4, 15, 12, 3, 3]$$$. In the final operation, pick $$$i=5, j=6$$$ and append $$$|a_5 - a_6| = 0$$$ to the end of $$$a$$$. Then the minimum value of $$$a$$$ will be $$$0$$$.

In the third test case, an optimal strategy is to first pick $$$i=2, j=3$$$ to append $$$|a_2 - a_3| = 3$$$ to the end of $$$a$$$. Any second operation will still not make the minimum value of $$$a$$$ be less than $$$3$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of the problem. The only differences between the two versions of this problem are the constraints on $$$n$$$ and the time limit. You can make hacks only if all versions of the problem are solved.

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$.

You can perform the following operation some (possibly zero) times:

1. choose $$$l$$$ and $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$.
2. let $$$x=\max(a_l,a_{l+1},\ldots,a_r)$$$.
3. for all $$$l \leq i \leq r$$$, set $$$a_i := x$$$.

Determine if you can make array $$$a$$$ equal to array $$$b$$$.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the arrays.

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

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — the elements of array $$$b$$$.

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

## Output Format
For each test case, output "YES" (without quotes) if you can make $$$a$$$ into $$$b$$$ using any number of operations, 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).

## Examples
```input
5
5
1 2 3 2 4
1 3 3 2 4
5
3 4 2 2 4
3 4 3 4 4
5
3 2 1 1 1
3 3 3 2 2
2
1 1
1 2
3
1 1 2
2 1 2
```
```output
YES
NO
YES
NO
NO
```

## Note
In the first test case, we can achieve array $$$b$$$ by applying a single operation: $$$(l,r)=(2,3)$$$.

In the second test case, it can be shown we cannot achieve array $$$b$$$ in any amount of operations.

In the third test case, we can achieve array $$$b$$$ by applying two operations: $$$(l,r)=(2,5)$$$. followed by $$$(l,r)=(1,3)$$$.

In the fourth and fifth test cases, it can be shown we cannot achieve array $$$b$$$ in any amount of operations.

Now solve the problem and return the code.