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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$2n$$$ distinct integers. You want to arrange the elements of the array in a circle such that no element is equal to the the arithmetic mean of its $$$2$$$ neighbours.

More formally, find an array $$$b$$$, such that:

- $$$b$$$ is a permutation of $$$a$$$.
- For every $$$i$$$ from $$$1$$$ to $$$2n$$$, $$$b_i \neq \frac{b_{i-1}+b_{i+1}}{2}$$$, where $$$b_0 = b_{2n}$$$ and $$$b_{2n+1} = b_1$$$.

It can be proved that under the constraints of this problem, such array $$$b$$$ always exists.

## Input Format
The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — the number of testcases. The description of testcases follows.

The first line of each testcase contains a single integer $$$n$$$ $$$(1 \leq n \leq 25)$$$.

The second line of each testcase contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$ $$$(1 \leq a_i \leq 10^9)$$$ — elements of the array.

Note that there is no limit to the sum of $$$n$$$ over all testcases.

## Output Format
For each testcase, you should output $$$2n$$$ integers, $$$b_1, b_2, \ldots b_{2n}$$$, for which the conditions from the statement are satisfied.

## Examples
```input
3
3
1 2 3 4 5 6
2
123 456 789 10
1
6 9
```
```output
3 1 4 2 5 6
123 10 456 789
9 6
```

## Note
In the first testcase, array $$$[3, 1, 4, 2, 5, 6]$$$ works, as it's a permutation of $$$[1, 2, 3, 4, 5, 6]$$$, and $$$\frac{3+4}{2}\neq 1$$$, $$$\frac{1+2}{2}\neq 4$$$, $$$\frac{4+5}{2}\neq 2$$$, $$$\frac{2+6}{2}\neq 5$$$, $$$\frac{5+3}{2}\neq 6$$$, $$$\frac{6+1}{2}\neq 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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$x$$$. Can you make $$$x$$$ by summing up some number of $$$11, 111, 1111, 11111, \ldots$$$? (You can use any number among them any number of times).

For instance,

- $$$33=11+11+11$$$
- $$$144=111+11+11+11$$$

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

The first and only line of each testcase contains a single integer $$$x$$$ $$$(1 \leq x \leq 10^9)$$$ — the number you have to make.

## Output Format
For each testcase, you should output a single string. If you can make $$$x$$$, output "YES" (without quotes). Otherwise, output "NO".

You can print each letter of "YES" and "NO" in any case (upper or lower).

## Examples
```input
3
33
144
69
```
```output
YES
YES
NO
```

## Note
Ways to make $$$33$$$ and $$$144$$$ were presented in the statement. It can be proved that we can't present $$$69$$$ this way.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Once upon a time, Oolimry saw a suffix array. He wondered how many strings can produce this suffix array.

More formally, given a suffix array of length $$$n$$$ and having an alphabet size $$$k$$$, count the number of strings that produce such a suffix array.

Let $$$s$$$ be a string of length $$$n$$$. Then the $$$i$$$-th suffix of $$$s$$$ is the substring $$$s[i \ldots n-1]$$$. A suffix array is the array of integers that represent the starting indexes of all the suffixes of a given string, after the suffixes are sorted in the lexicographic order. For example, the suffix array of oolimry is $$$[3,2,4,1,0,5,6]$$$ as the array of sorted suffixes is $$$[\texttt{imry},\texttt{limry},\texttt{mry},\texttt{olimry},\texttt{oolimry},\texttt{ry},\texttt{y}]$$$.

A string $$$x$$$ is lexicographically smaller than string $$$y$$$, if either $$$x$$$ is a prefix of $$$y$$$ (and $$$x\neq y$$$), or there exists such $$$i$$$ that $$$x_i < y_i$$$, and for any $$$1\leq j < i$$$ , $$$x_j = y_j$$$.

## Input Format
The first line contain 2 integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 200000,1 \leq k \leq 200000$$$) — the length of the suffix array and the alphabet size respectively.

The second line contains $$$n$$$ integers $$$s_0, s_1, s_2, \ldots, s_{n-1}$$$ ($$$0 \leq s_i \leq n-1$$$) where $$$s_i$$$ is the $$$i$$$-th element of the suffix array i.e. the starting position of the $$$i$$$-th lexicographically smallest suffix. It is guaranteed that for all $$$0 \leq i< j \leq n-1$$$, $$$s_i \neq s_j$$$.

## Output Format
Print how many strings produce such a suffix array. Since the number can be very large, print the answer modulo $$$998244353$$$.

## Examples
```input
3 2
0 2 1
```
```output
1
```
-----
```input
5 1
0 1 2 3 4
```
```output
0
```
-----
```input
6 200000
0 1 2 3 4 5
```
```output
822243495
```
-----
```input
7 6
3 2 4 1 0 5 6
```
```output
36
```

## Note
In the first test case, "abb" is the only possible solution.

In the second test case, it can be easily shown no possible strings exist as all the letters have to be equal.

In the fourth test case, one possible string is "ddbacef".

Please remember to print your answers modulo $$$998244353$$$.

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 python3.

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:
```python
<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.
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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
As their story unravels, a timeless tale is told once again...

Shirahime, a friend of Mocha's, is keen on playing the music game Arcaea and sharing Mocha interesting puzzles to solve. This day, Shirahime comes up with a new simple puzzle and wants Mocha to solve them. However, these puzzles are too easy for Mocha to solve, so she wants you to solve them and tell her the answers. The puzzles are described as follow.

There are $$$n$$$ squares arranged in a row, and each of them can be painted either red or blue.

Among these squares, some of them have been painted already, and the others are blank. You can decide which color to paint on each blank square.

Some pairs of adjacent squares may have the same color, which is imperfect. We define the imperfectness as the number of pairs of adjacent squares that share the same color.

For example, the imperfectness of "BRRRBBR" is $$$3$$$, with "BB" occurred once and "RR" occurred twice.

Your goal is to minimize the imperfectness and print out the colors of the squares after painting.

## 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 an integer $$$n$$$ ($$$1\leq n\leq 100$$$) — the length of the squares row.

The second line of each test case contains a string $$$s$$$ with length $$$n$$$, containing characters 'B', 'R' and '?'. Here 'B' stands for a blue square, 'R' for a red square, and '?' for a blank square.

## Output Format
For each test case, print a line with a string only containing 'B' and 'R', the colors of the squares after painting, which imperfectness is minimized. If there are multiple solutions, print any of them.

## Examples
```input
5
7
?R???BR
7
???R???
1
?
1
B
10
?R??RB??B?
```
```output
BRRBRBR
BRBRBRB
B
B
BRRBRBBRBR
```

## Note
In the first test case, if the squares are painted "BRRBRBR", the imperfectness is $$$1$$$ (since squares $$$2$$$ and $$$3$$$ have the same color), which is the minimum possible imperfectness.

Now solve the problem and return the code.