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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A permutation is a sequence of $$$n$$$ integers from $$$1$$$ to $$$n$$$, in which all the numbers occur exactly once. For example, $$$[1]$$$, $$$[3, 5, 2, 1, 4]$$$, $$$[1, 3, 2]$$$ are permutations, and $$$[2, 3, 2]$$$, $$$[4, 3, 1]$$$, $$$[0]$$$ are not.

Polycarp was given four integers $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n)$$$ and $$$s$$$ ($$$1 \le s \le \frac{n (n+1)}{2}$$$) and asked to find a permutation $$$p$$$ of numbers from $$$1$$$ to $$$n$$$ that satisfies the following condition:

- $$$s = p_l + p_{l+1} + \ldots + p_r$$$.

For example, for $$$n=5$$$, $$$l=3$$$, $$$r=5$$$, and $$$s=8$$$, the following permutations are suitable (not all options are listed):

- $$$p = [3, 4, 5, 2, 1]$$$;
- $$$p = [5, 2, 4, 3, 1]$$$;
- $$$p = [5, 2, 1, 3, 4]$$$.

Help Polycarp, for the given $$$n$$$, $$$l$$$, $$$r$$$, and $$$s$$$, find a permutation of numbers from $$$1$$$ to $$$n$$$ that fits the condition above. If there are several suitable permutations, print any of them.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$). Then $$$t$$$ test cases follow.

Each test case consist of one line with four integers $$$n$$$ ($$$1 \le n \le 500$$$), $$$l$$$ ($$$1 \le l \le n$$$), $$$r$$$ ($$$l \le r \le n$$$), $$$s$$$ ($$$1 \le s \le \frac{n (n+1)}{2}$$$).

It is guaranteed that the sum of $$$n$$$ for all input data sets does not exceed $$$500$$$.

## Output Format
For each test case, output on a separate line:

- $$$n$$$ integers — a permutation of length $$$n$$$ that fits the condition above if such a permutation exists;
- -1, otherwise.

If there are several suitable permutations, print any of them.

## Examples
```input
5
5 2 3 5
5 3 4 1
3 1 2 4
2 2 2 2
2 1 1 3
```
```output
1 2 3 4 5 
-1
1 3 2 
1 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
Let us denote by $$$d(n)$$$ the sum of all divisors of the number $$$n$$$, i.e. $$$d(n) = \sum\limits_{k | n} k$$$.

For example, $$$d(1) = 1$$$, $$$d(4) = 1+2+4=7$$$, $$$d(6) = 1+2+3+6=12$$$.

For a given number $$$c$$$, find the minimum $$$n$$$ such that $$$d(n) = c$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

Each test case is characterized by one integer $$$c$$$ ($$$1 \le c \le 10^7$$$).

## Output Format
For each test case, output:

- "-1" if there is no such $$$n$$$ that $$$d(n) = c$$$;
- $$$n$$$, otherwise.

## Examples
```input
12
1
2
3
4
5
6
7
8
9
10
39
691
```
```output
1
-1
2
3
-1
5
4
7
-1
-1
18
-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
William really likes the cellular automaton called "Game of Life" so he decided to make his own version. For simplicity, William decided to define his cellular automaton on an array containing $$$n$$$ cells, with each cell either being alive or dead.

Evolution of the array in William's cellular automaton occurs iteratively in the following way:

- If the element is dead and it has exactly $$$1$$$ alive neighbor in the current state of the array, then on the next iteration it will become alive. For an element at index $$$i$$$ the neighbors would be elements with indices $$$i - 1$$$ and $$$i + 1$$$. If there is no element at that index, it is considered to be a dead neighbor.
- William is a humane person so all alive elements stay alive.

Check the note section for examples of the evolution.

You are given some initial state of all elements and you need to help William find the state of the array after $$$m$$$ iterations of evolution.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^3, 1 \le m \le 10^9$$$), which are the total number of cells in the array and the number of iterations.

The second line of each test case contains a string of length $$$n$$$ made up of characters "0" and "1" and defines the initial state of the array. "1" means a cell is alive and "0" means it is dead.

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

## Output Format
In each test case output a string of length $$$n$$$, made up of characters "0" and "1"  — the state of the array after $$$m$$$ iterations of evolution.

## Examples
```input
4
11 3
01000000001
10 2
0110100101
5 2
10101
3 100
000
```
```output
11111001111
1110111101
10101
000
```

## Note
Sequence of iterations of evolution for the first test case

- 01000000001  — initial state
- 11100000011  — first iteration of evolution
- 11110000111  — second iteration of evolution
- 11111001111  — third iteration of evolution

Sequence of iterations of evolution for the second test case

- 0110100101  — initial state
- 1110111101  — first iteration of evolution
- 1110111101  — second iteration of evolution

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
William is hosting a party for $$$n$$$ of his trader friends. They started a discussion on various currencies they trade, but there's an issue: not all of his trader friends like every currency. They like some currencies, but not others.

For each William's friend $$$i$$$ it is known whether he likes currency $$$j$$$. There are $$$m$$$ currencies in total. It is also known that a trader may not like more than $$$p$$$ currencies.

Because friends need to have some common topic for discussions they need to find the largest by cardinality (possibly empty) subset of currencies, such that there are at least $$$\lceil \frac{n}{2} \rceil$$$ friends (rounded up) who like each currency in this subset.

## Input Format
The first line contains three integers $$$n, m$$$ and $$$p$$$ $$$(1 \le n \le 2 \cdot 10^5, 1 \le p \le m \le 60, 1 \le p \le 15)$$$, which is the number of trader friends, the number of currencies, the maximum number of currencies each friend can like.

Each of the next $$$n$$$ lines contain $$$m$$$ characters. The $$$j$$$-th character of $$$i$$$-th line is $$$1$$$ if friend $$$i$$$ likes the currency $$$j$$$ and $$$0$$$ otherwise. It is guaranteed that the number of ones in each line does not exceed $$$p$$$.

## Output Format
Print a string of length $$$m$$$, which defines the subset of currencies of the maximum size, which are liked by at least half of all friends. Currencies belonging to this subset must be signified by the character $$$1$$$.

If there are multiple answers, print any.

## Examples
```input
3 4 3
1000
0110
1001
```
```output
1000
```
-----
```input
5 5 4
11001
10101
10010
01110
11011
```
```output
10001
```

## Note
In the first sample test case only the first currency is liked by at least $$$\lceil \frac{3}{2} \rceil = 2$$$ friends, therefore it's easy to demonstrate that a better answer cannot be found.

In the second sample test case the answer includes $$$2$$$ currencies and will be liked by friends $$$1$$$, $$$2$$$, and $$$5$$$. For this test case there are other currencies that are liked by at least half of the friends, but using them we cannot achieve a larger subset size.

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
To monitor cryptocurrency exchange rates trader William invented a wonderful device consisting of $$$n$$$ lights arranged in a row. The device functions in the following way:

Initially, all lights on William's device are turned off. At the beginning of a new iteration the device randomly, with a uniform distribution, picks a light that is turned off and turns it on, telling William which cryptocurrency he should invest in. After this iteration if any $$$k$$$ consecutive lights contain more than one turned on light, then the device finishes working.

William doesn't like uncertainty, so he wants you to calculate the expected value of the number of lights that are turned on in the device after it finishes working.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). Description of the test cases follows.

The only line for each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 10^5$$$), which are the total number of lights and the length of subsegment of lights that are being checked, respectively.

## Output Format
For each test case print the answer, modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Examples
```input
3
3 2
15 2
40 15
```
```output
333333338
141946947
329622137
```

## Note
Explanation of the first sample test case:

Let's write out all possible sequences of light toggles, which will make the device complete its operation:

1. $$$(1, 2)$$$  — $$$2$$$ lights are turned on
2. $$$(1, 3, 2)$$$  — $$$3$$$ lights are turned on
3. $$$(2, 1)$$$  — $$$2$$$ lights are turned on
4. $$$(2, 3)$$$  — $$$2$$$ lights are turned on
5. $$$(3, 2)$$$  — $$$2$$$ lights are turned on
6. $$$(3, 1, 2)$$$  — $$$3$$$ lights are turned on

Then the final expected value will be equal to $$$\frac{2}{6}$$$ + $$$\frac{3}{6}$$$ + $$$\frac{2}{6}$$$ + $$$\frac{2}{6}$$$ + $$$\frac{2}{6}$$$ + $$$\frac{3}{6}$$$ = $$$\frac{14}{6}$$$ = $$$\frac{7}{3}$$$.

Then the required output will be $$$333333338$$$, since $$$333333338 \cdot 3 \equiv 7 \pmod{10^9+7}$$$.

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
William really wants to get a pet. Since his childhood he dreamt about getting a pet grasshopper. William is being very responsible about choosing his pet, so he wants to set up a trial for the grasshopper!

The trial takes place on an array $$$a$$$ of length $$$n$$$, which defines lengths of hops for each of $$$n$$$ cells. A grasshopper can hop around the sells according to the following rule: from a cell with index $$$i$$$ it can jump to any cell with indices from $$$i$$$ to $$$i+a_i$$$ inclusive.

Let's call the $$$k$$$-grasshopper value of some array the smallest number of hops it would take a grasshopper to hop from the first cell to the last, but before starting you can select no more than $$$k$$$ cells and remove them from the array. When a cell is removed all other cells are renumbered but the values of $$$a_i$$$ for each cell remains the same. During this the first and the last cells may not be removed.

It is required to process $$$q$$$ queries of the following format: you are given three numbers $$$l$$$, $$$r$$$, $$$k$$$. You are required to find the $$$k$$$-grasshopper value for an array, which is a subarray of the array $$$a$$$ with elements from $$$l$$$ to $$$r$$$ inclusive.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 20000$$$), the length of the array and the number of queries respectively.

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

The following $$$q$$$ lines contain queries: each line contains three integers $$$l$$$, $$$r$$$ and $$$k$$$ ($$$1 \le l \le r \le n$$$, $$$0 \le k \le min(30, r-l)$$$), which are the edges of the subarray and the number of the grasshopper value respectively.

## Output Format
For each query print a single number in a new line  — the response to a query.

## Examples
```input
9 5
1 1 2 1 3 1 2 1 1
1 1 0
2 5 1
5 9 1
2 8 2
1 9 4
```
```output
0
2
1
2
2
```

## Note
For the second query the process occurs like this:

For the third query the process occurs like this:

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
Given an integer $$$n$$$, find the maximum value of integer $$$k$$$ such that the following condition holds:

$$$n$$$ & ($$$n-1$$$) & ($$$n-2$$$) & ($$$n-3$$$) & ... ($$$k$$$) = $$$0$$$

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$). Then $$$t$$$ test cases follow.

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

## Output Format
For each test case, output a single integer — the required integer $$$k$$$.

## Examples
```input
3
2
5
17
```
```output
1
3
15
```

## Note
In the first testcase, the maximum value for which the continuous & operation gives 0 value, is 1.

In the second testcase, the maximum value for which the continuous & operation gives 0 value, is 3. No value greater then 3, say for example 4, will give the & sum 0.

- $$$5 \, \& \, 4 \neq 0$$$,
- $$$5 \, \& \, 4 \, \& \, 3 = 0$$$.

Hence, 3 is the answer.

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
The weight of a sequence is defined as the number of unordered pairs of indexes $$$(i,j)$$$ (here $$$i \lt j$$$) with same value ($$$a_{i} = a_{j}$$$). For example, the weight of sequence $$$a = [1, 1, 2, 2, 1]$$$ is $$$4$$$. The set of unordered pairs of indexes with same value are $$$(1, 2)$$$, $$$(1, 5)$$$, $$$(2, 5)$$$, and $$$(3, 4)$$$.

You are given a sequence $$$a$$$ of $$$n$$$ integers. Print the sum of the weight of all subsegments of $$$a$$$.

A sequence $$$b$$$ is a subsegment of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). 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 second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

## Output Format
For each test case, print a single integer — the sum of the weight of all subsegments of $$$a$$$.

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

## Note
- In test case $$$1$$$, all possible subsegments of sequence $$$[1, 2, 1, 1]$$$ having size more than $$$1$$$ are:   $$$[1, 2]$$$ having $$$0$$$ valid unordered pairs;  $$$[2, 1]$$$ having $$$0$$$ valid unordered pairs;  $$$[1, 1]$$$ having $$$1$$$ valid unordered pair;  $$$[1, 2, 1]$$$ having $$$1$$$ valid unordered pairs;  $$$[2, 1, 1]$$$ having $$$1$$$ valid unordered pair;  $$$[1, 2, 1, 1]$$$ having $$$3$$$ valid unordered pairs.  Answer is $$$6$$$.
- In test case $$$2$$$, all elements of the sequence are distinct. So, there is no valid unordered pair with the same value for any subarray. Answer is $$$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
You are given an array $$$a$$$ of $$$n$$$ integers. Define the cost of some array $$$t$$$ as follows:

$$$$$$cost(t) = \sum_{x \in set(t) } last(x) - first(x),$$$$$$

where $$$set(t)$$$ is the set of all values in $$$t$$$ without repetitions, $$$first(x)$$$, and $$$last(x)$$$ are the indices of the first and last occurrence of $$$x$$$ in $$$t$$$, respectively. In other words, we compute the distance between the first and last occurrences for each distinct element and sum them up.

You need to split the array $$$a$$$ into $$$k$$$ consecutive segments such that each element of $$$a$$$ belongs to exactly one segment and the sum of the cost of individual segments is minimum.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 35\,000$$$, $$$1 \le k \le \min(n,100)$$$).

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

## Output Format
Output the minimum sum of the cost of individual segments.

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

## Note
In the first example, we can divide the array into $$$[1,6,6,4]$$$ and $$$[6,6,6]$$$. Cost of $$$[1,6,6,4]$$$ will be $$$(1-1) + (3 - 2) + (4-4) = 1$$$ and cost of $$$[6,6,6]$$$ will be $$$3-1 = 2$$$. Total cost would be $$$1 + 2 = 3$$$.

In the second example, divide the array into $$$[5,5],[5],[5,2,3]$$$ and $$$[3]$$$. Total Cost would be $$$1 + 0 + 0 + 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Mocha is a young girl from high school. She has learned so much interesting knowledge from her teachers, especially her math teacher. Recently, Mocha is learning about binary system and very interested in bitwise operation.

This day, Mocha got a sequence $$$a$$$ of length $$$n$$$. In each operation, she can select an arbitrary interval $$$[l, r]$$$ and for all values $$$i$$$ ($$$0\leq i \leq r-l$$$), replace $$$a_{l+i}$$$ with $$$a_{l+i} \,\&\, a_{r-i}$$$ at the same time, where $$$\&$$$ denotes the bitwise AND operation. This operation can be performed any number of times.

For example, if $$$n=5$$$, the array is $$$[a_1,a_2,a_3,a_4,a_5]$$$, and Mocha selects the interval $$$[2,5]$$$, then the new array is $$$[a_1,a_2\,\&\, a_5, a_3\,\&\, a_4, a_4\,\&\, a_3, a_5\,\&\, a_2]$$$.

Now Mocha wants to minimize the maximum value in the sequence. As her best friend, can you help her to get the answer?

## Input Format
Each test contains multiple test cases.

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

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

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

## Output Format
For each test case, print one integer — the minimal value of the maximum value in the sequence.

## Examples
```input
4
2
1 2
3
1 1 3
4
3 11 3 7
5
11 7 15 3 7
```
```output
0
1
3
3
```

## Note
In the first test case, Mocha can choose the interval $$$[1,2]$$$, then the sequence becomes $$$[ 0, 0]$$$, where the first element is $$$1\,\&\,2$$$, and the second element is $$$2\,\&\,1$$$.

In the second test case, Mocha can choose the interval $$$[1,3]$$$, then the sequence becomes $$$[ 1,1,1]$$$, where the first element is $$$1\,\&\,3$$$, the second element is $$$1\,\&\,1$$$, and the third element is $$$3\,\&\,1$$$.

Now solve the problem and return the code.