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
You are given three integers $$$a$$$, $$$b$$$, and $$$d$$$. Your task is to find any integer $$$x$$$ which satisfies all of the following conditions, or determine that no such integers exist:

- $$$0 \le x \lt 2^{60}$$$;
- $$$a|x$$$ is divisible by $$$d$$$;
- $$$b|x$$$ is divisible by $$$d$$$.

Here, $$$|$$$ denotes the bitwise OR operation.

## Input Format
Each test contains multiple test cases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one line, containing three integers $$$a$$$, $$$b$$$, and $$$d$$$ ($$$1 \le a,b,d \lt 2^{30}$$$).

## Output Format
For each test case print one integer. If there exists an integer $$$x$$$ which satisfies all of the conditions from the statement, print $$$x$$$. Otherwise, print $$$-1$$$.

If there are multiple solutions, you may print any of them.

## Examples
```input
8
12 39 5
6 8 14
100 200 200
3 4 6
2 2 2
18 27 3
420 666 69
987654321 123456789 999999999
```
```output
18
14
-1
-1
0
11
25599
184470016815529983
```

## Note
In the first test case, $$$x=18$$$ is one of the possible solutions, since $$$39|18=55$$$ and $$$12|18=30$$$, both of which are multiples of $$$d=5$$$.

In the second test case, $$$x=14$$$ is one of the possible solutions, since $$$8|14=6|14=14$$$, which is a multiple of $$$d=14$$$.

In the third and fourth test cases, we can show that there are no solutions.

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
The position of the leftmost maximum on the segment $$$[l; r]$$$ of array $$$x = [x_1, x_2, \ldots, x_n]$$$ is the smallest integer $$$i$$$ such that $$$l \le i \le r$$$ and $$$x_i = \max(x_l, x_{l+1}, \ldots, x_r)$$$.

You are given an array $$$a = [a_1, a_2, \ldots, a_n]$$$ of length $$$n$$$. Find the number of integer arrays $$$b = [b_1, b_2, \ldots, b_n]$$$ of length $$$n$$$ that satisfy the following conditions:

- $$$1 \le b_i \le m$$$ for all $$$1 \le i \le n$$$;
- for all pairs of integers $$$1 \le l \le r \le n$$$, the position of the leftmost maximum on the segment $$$[l; r]$$$ of the array $$$b$$$ is equal to the position of the leftmost maximum on the segment $$$[l; r]$$$ of the array $$$a$$$.

Since the answer might be very large, print its remainder modulo $$$10^9+7$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n,m \le 2 \cdot 10^5$$$, $$$n \cdot m \le 10^6$$$).

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

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases doesn't exceed $$$10^6$$$.

## Output Format
For each test case print one integer — the number of arrays $$$b$$$ that satisfy the conditions from the statement, modulo $$$10^9+7$$$.

## Examples
```input
4
3 3
1 3 2
4 2
2 2 2 2
6 9
6 9 6 9 6 9
9 100
10 40 20 20 100 60 80 60 60
```
```output
8
5
11880
351025663
```

## Note
In the first test case, the following $$$8$$$ arrays satisfy the conditions from the statement:

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

In the second test case, the following $$$5$$$ arrays satisfy the conditions from the statement:

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

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 have an array $$$a_0, a_1, \ldots, a_{n-1}$$$ of length $$$n$$$. Initially, $$$a_i = 2^i$$$ for all $$$0 \le i \lt n$$$. Note that array $$$a$$$ is zero-indexed.

You want to reverse this array (that is, make $$$a_i$$$ equal to $$$2^{n-1-i}$$$ for all $$$0 \le i \lt n$$$). To do this, you can perform the following operation no more than $$$250\,000$$$ times:

- Select an integer $$$i$$$ ($$$0 \le i \lt n$$$) and replace $$$a_i$$$ by $$$a_i \oplus a_{(i+1)\bmod n}$$$.

Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Your task is to find any sequence of operations that will result in the array $$$a$$$ being reversed. It can be shown that under the given constraints, a solution always exists.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 400$$$) — the length of the array $$$a$$$.

## Output Format
On the first line print one integer $$$k$$$ ($$$0 \le k \le 250\,000$$$) — the number of operations performed.

On the second line print $$$k$$$ integers $$$i_1,i_2,\ldots,i_k$$$ ($$$0 \le i_j \lt n$$$). Here, $$$i_j$$$ should be the integer selected on the $$$j$$$-th operation.

Note that you don't need to minimize the number of operations.

## Examples
```input
2
```
```output
3
1 0 1
```
-----
```input
3
```
```output
9
1 0 1 0 2 1 0 1 0
```

## Note
In the notes, the elements on which the operations are performed are colored red.

In the first test case, array $$$a$$$ will change in the following way:

$$$[1,\color{red}{2}] \rightarrow [\color{red}{1},3] \rightarrow [2,\color{red}{3}] \rightarrow [2,1]$$$.

In the second test case, array $$$a$$$ will change in the following way:

$$$[1,\color{red}{2},4] \rightarrow [\color{red}{1},6,4] \rightarrow [7,\color{red}{6},4] \rightarrow [\color{red}{7},2,4] \rightarrow [5,2,\color{red}{4}] \rightarrow [5,\color{red}{2},1] \rightarrow [\color{red}{5},3,1] \rightarrow [6,\color{red}{3},1] \rightarrow [\color{red}{6},2,1] \rightarrow [4,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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You work in the quality control department of technical support for a large company. Your job is to make sure all client issues have been resolved.

Today you need to check a copy of a dialog between a client and a technical support manager. According to the rules of work, each message of the client must be followed by one or several messages, which are the answer of a support manager. However, sometimes clients ask questions so quickly that some of the manager's answers to old questions appear after the client has asked some new questions.

Due to the privacy policy, the full text of messages is not available to you, only the order of messages is visible, as well as the type of each message: a customer question or a response from the technical support manager. It is guaranteed that the dialog begins with the question of the client.

You have to determine, if this dialog may correspond to the rules of work described above, or the rules are certainly breached.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the total number of messages in the dialog.

The second line of each test case consists of $$$n$$$ characters "Q" and "A", describing types of messages in the dialog in chronological order. Character "Q" denotes the message with client question, and character "A" — the message with technical support manager answer. It is guaranteed that the first character in the line equals to "Q".

## Output Format
For each test case print "Yes" (without quotes) if dialog may correspond to the rules of work, or "No" (without quotes) otherwise.

## Examples
```input
5
4
QQAA
4
QQAQ
3
QAA
1
Q
14
QAQQAQAAQQQAAA
```
```output
Yes
No
Yes
No
Yes
```

## Note
In the first test case the two questions from the client are followed with two specialist's answers. So this dialog may correspond to the rules of work.

In the second test case one of the first two questions was not answered.

In the third test case the technical support manager sent two messaged as the answer to the only message of the client.

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: 512.0 MB

# Problem
Recently, Mishka started noticing that his keyboard malfunctions — maybe it's because he was playing rhythm games too much. Empirically, Mishka has found out that every other time he presses a key, it is registered as if the key was pressed twice. For example, if Mishka types text, the first time he presses a key, exactly one letter is printed; the second time he presses a key, two same letters are printed; the third time he presses a key, one letter is printed; the fourth time he presses a key, two same letters are printed, and so on. Note that the number of times a key was pressed is counted for the whole keyboard, not for each key separately. For example, if Mishka tries to type the word osu, it will be printed on the screen as ossu.

You are given a word consisting of $$$n$$$ lowercase Latin letters. You have to determine if it can be printed on Mishka's keyboard or not. You may assume that Mishka cannot delete letters from the word, and every time he presses a key, the new letter (or letters) is appended to the end of the word.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the word.

The second line of the test case contains a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters — the word that should be checked.

## Output Format
For each test case, print YES if the word $$$s$$$ can be printed on Mishka's keyboard, and NO otherwise.

## Examples
```input
4
4
ossu
2
aa
6
addonn
3
qwe
```
```output
YES
NO
YES
NO
```

## Note
In the first test case, Mishka can type the word as follows: press o (one letter o appears at the end of the word), then presses s (two letters s appear at the end of the word), and, finally, press u (one letter appears at the end of the word, making the resulting word ossu).

In the second test case, Mishka can try typing the word as follows: press a (one letter a appears at the end of the word). But if he tries to press a one more time, two letters a will appear at the end of the word, so it is impossible to print the word using his keyboard.

In the fourth test case, Mishka has to start by pressing q. Then, if he presses w, two copies of w will appear at the end of the word, but the third letter should be e instead of w, so the answer is NO.

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: 15.0 seconds
Memory limit: 1024.0 MB

# Problem
Consider a deck of cards. Each card has one of $$$4$$$ suits, and there are exactly $$$n$$$ cards for each suit — so, the total number of cards in the deck is $$$4n$$$. The deck is shuffled randomly so that each of $$$(4n)!$$$ possible orders of cards in the deck has the same probability of being the result of shuffling. Let $$$c_i$$$ be the $$$i$$$-th card of the deck (from top to bottom).

Monocarp starts drawing the cards from the deck one by one. Before drawing a card, he tries to guess its suit. Monocarp remembers the suits of the $$$k$$$ last cards, and his guess is the suit that appeared the least often among the last $$$k$$$ cards he has drawn. So, while drawing the $$$i$$$-th card, Monocarp guesses that its suit is the suit that appears the minimum number of times among the cards $$$c_{i-k}, c_{i-k+1}, \dots, c_{i-1}$$$ (if $$$i \le k$$$, Monocarp considers all previously drawn cards, that is, the cards $$$c_1, c_2, \dots, c_{i-1}$$$). If there are multiple suits that appeared the minimum number of times among the previous cards Monocarp remembers, he chooses a random suit out of those for his guess (all suits that appeared the minimum number of times have the same probability of being chosen).

After making a guess, Monocarp draws a card and compares its suit to his guess. If they match, then his guess was correct; otherwise it was incorrect.

Your task is to calculate the expected number of correct guesses Monocarp makes after drawing all $$$4n$$$ cards from the deck.

## Input Format
The first (and only) line contains two integers $$$n$$$ ($$$1 \le n \le 500$$$) and $$$k$$$ ($$$1 \le k \le 4 \cdot n$$$).

## Output Format
Let the expected value you have to calculate be an irreducible fraction $$$\dfrac{x}{y}$$$. Print one integer — the value of $$$x \cdot y^{-1} \bmod 998244353$$$, where $$$y^{-1}$$$ is the inverse to $$$y$$$ (i. e. an integer such that $$$y \cdot y^{-1} \bmod 998244353 = 1$$$).

## Examples
```input
1 1
```
```output
748683266
```
-----
```input
3 2
```
```output
567184295
```
-----
```input
2 7
```
```output
373153250
```
-----
```input
2 8
```
```output
373153250
```

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: 512.0 MB

# Problem
Monocarp wants to watch $$$n$$$ videos. Each video is only one minute long, but its size may be arbitrary. The $$$i$$$-th video has the size $$$a_i$$$ megabytes. All videos are published on the Internet. A video should be downloaded before it can be watched. Monocarp has poor Internet connection — it takes exactly $$$1$$$ minute to download $$$1$$$ megabyte of data, so it will require $$$a_i$$$ minutes to download the $$$i$$$-th video.

Monocarp's computer has a hard disk of $$$m$$$ megabytes. The disk is used to store the downloaded videos. Once Monocarp starts the download of a video of size $$$s$$$, the $$$s$$$ megabytes are immediately reserved on a hard disk. If there are less than $$$s$$$ megabytes left, the download cannot be started until the required space is freed. Each single video can be stored on the hard disk, since $$$a_i \le m$$$ for all $$$i$$$. Once the download is started, it cannot be interrupted. It is not allowed to run two or more downloads in parallel.

Once a video is fully downloaded to the hard disk, Monocarp can watch it. Watching each video takes exactly $$$1$$$ minute and does not occupy the Internet connection, so Monocarp can start downloading another video while watching the current one.

When Monocarp finishes watching a video, he doesn't need it on the hard disk anymore, so he can delete the video, instantly freeing the space it occupied on a hard disk. Deleting a video takes negligible time.

Monocarp wants to watch all $$$n$$$ videos as quickly as possible. The order of watching does not matter, since Monocarp needs to watch all of them anyway. Please calculate the minimum possible time required for that.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 10^9$$$) — the number of videos Monocarp wants to watch and the size of the hard disk, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le m$$$) — the sizes of the videos.

## Output Format
Print one integer — the minimum time required to watch all $$$n$$$ videos.

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

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
Monocarp is playing a MMORPG. There are two commonly used types of currency in this MMORPG — gold coins and silver coins. Monocarp wants to buy a new weapon for his character, and that weapon costs $$$n$$$ silver coins. Unfortunately, right now, Monocarp has no coins at all.

Monocarp can earn gold coins by completing quests in the game. Each quest yields exactly one gold coin. Monocarp can also exchange coins via the in-game trading system. Monocarp has spent days analyzing the in-game economy; he came to the following conclusion: it is possible to sell one gold coin for $$$a$$$ silver coins (i. e. Monocarp can lose one gold coin to gain $$$a$$$ silver coins), or buy one gold coin for $$$b$$$ silver coins (i. e. Monocarp can lose $$$b$$$ silver coins to gain one gold coin).

Now Monocarp wants to calculate the minimum number of quests that he has to complete in order to have at least $$$n$$$ silver coins after some abuse of the in-game economy. Note that Monocarp can perform exchanges of both types (selling and buying gold coins for silver coins) any number of times.

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

Each test case consists of one line containing three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$1 \le n \le 10^7$$$; $$$1 \le a, b \le 50$$$).

## Output Format
For each test case, print one integer — the minimum possible number of quests Monocarp has to complete.

## Examples
```input
4
100 25 30
9999997 25 50
52 50 48
49 50 1
```
```output
4
400000
1
1
```

## Note
In the first test case of the example, Monocarp should complete $$$4$$$ quests, and then sell $$$4$$$ gold coins for $$$100$$$ silver coins.

In the second test case, Monocarp should complete $$$400000$$$ quests, and then sell $$$400000$$$ gold coins for $$$10$$$ million silver coins.

In the third test case, Monocarp should complete $$$1$$$ quest, sell the gold coin for $$$50$$$ silver coins, buy a gold coin for $$$48$$$ silver coins, and then sell it again for $$$50$$$ coins. So, he will have $$$52$$$ silver coins.

In the fourth test case, Monocarp should complete $$$1$$$ quest and then sell the gold coin he has obtained for $$$50$$$ silver coins.

Now solve the problem and return the code.