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
Alice is playing a game with her good friend, Marisa.

There are $$$n$$$ boxes arranged in a line, numbered with integers from $$$1$$$ to $$$n$$$ from left to right. Marisa will hide a doll in one of the boxes. Then Alice will have $$$m$$$ chances to guess where the doll is. If Alice will correctly guess the number of box, where doll is now, she will win the game, otherwise, her friend will win the game.

In order to win, Marisa will use some unfair tricks. After each time Alice guesses a box, she can move the doll to the neighboring box or just keep it at its place. Boxes $$$i$$$ and $$$i + 1$$$ are neighboring for all $$$1 \leq i \leq n - 1$$$. She can also use this trick once before the game starts.

So, the game happens in this order: the game starts, Marisa makes the trick, Alice makes the first guess, Marisa makes the trick, Alice makes the second guess, Marisa makes the trick, $$$\ldots$$$, Alice makes $$$m$$$-th guess, Marisa makes the trick, the game ends.

Alice has come up with a sequence $$$a_1, a_2, \ldots, a_m$$$. In the $$$i$$$-th guess, she will ask if the doll is in the box $$$a_i$$$. She wants to know the number of scenarios $$$(x, y)$$$ (for all $$$1 \leq x, y \leq n$$$), such that Marisa can win the game if she will put the doll at the $$$x$$$-th box at the beginning and at the end of the game, the doll will be at the $$$y$$$-th box. Help her and calculate this number.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$, separated by space ($$$1 \leq n, m \leq 10^5$$$) — the number of boxes and the number of guesses, which Alice will make.

The next line contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$, separated by spaces ($$$1 \leq a_i \leq n$$$), the number $$$a_i$$$ means the number of the box which Alice will guess in the $$$i$$$-th guess.

## Output Format
Print the number of scenarios in a single line, or the number of pairs of boxes $$$(x, y)$$$ ($$$1 \leq x, y \leq n$$$), such that if Marisa will put the doll into the box with number $$$x$$$, she can make tricks in such way, that at the end of the game the doll will be in the box with number $$$y$$$ and she will win the game.

## Examples
```input
3 3
2 2 2
```
```output
7
```
-----
```input
5 2
3 1
```
```output
21
```

## Note
In the first example, the possible scenarios are $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$.

Let's take $$$(2, 2)$$$ as an example. The boxes, in which the doll will be during the game can be $$$2 \to 3 \to 3 \to 3 \to 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ football teams in the world.

The Main Football Organization (MFO) wants to host at most $$$m$$$ games. MFO wants the $$$i$$$-th game to be played between the teams $$$a_i$$$ and $$$b_i$$$ in one of the $$$k$$$ stadiums.

Let $$$s_{ij}$$$ be the numbers of games the $$$i$$$-th team played in the $$$j$$$-th stadium. MFO does not want a team to have much more games in one stadium than in the others. Therefore, for each team $$$i$$$, the absolute difference between the maximum and minimum among $$$s_{i1}, s_{i2}, \ldots, s_{ik}$$$ should not exceed $$$2$$$.

Each team has $$$w_i$$$ — the amount of money MFO will earn for each game of the $$$i$$$-th team. If the $$$i$$$-th team plays $$$l$$$ games, MFO will earn $$$w_i \cdot l$$$.

MFO needs to find what games in what stadiums they need to host in order to earn as much money as possible, not violating the rule they set.

However, this problem is too complicated for MFO. Therefore, they are asking you to help them.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$3 \leq n \leq 100$$$, $$$0 \leq m \leq 1\,000$$$, $$$1 \leq k \leq 1\,000$$$) — the number of teams, the number of games, and the number of stadiums.

The second line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \leq w_i \leq 1\,000$$$) — the amount of money MFO will earn for each game of the $$$i$$$-th game.

Each of the following $$$m$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — the teams that can play the $$$i$$$-th game. It is guaranteed that each pair of teams can play at most one game.

## Output Format
For each game in the same order, print $$$t_i$$$ ($$$1 \leq t_i \leq k$$$) — the number of the stadium, in which $$$a_i$$$ and $$$b_i$$$ will play the game. If the $$$i$$$-th game should not be played, $$$t_i$$$ should be equal to $$$0$$$.

If there are multiple answers, print any.

## Examples
```input
7 11 3
4 7 8 10 10 9 3
6 2
6 1
7 6
4 3
4 6
3 1
5 3
7 5
7 3
4 2
1 4
```
```output
3
2
1
1
3
1
2
1
2
3
2
```

## Note
One of possible solutions to the example is shown below:

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
A string is called beautiful if no two consecutive characters are equal. For example, "ababcb", "a" and "abab" are beautiful strings, while "aaaaaa", "abaa" and "bb" are not.

Ahcl wants to construct a beautiful string. He has a string $$$s$$$, consisting of only characters 'a', 'b', 'c' and '?'. Ahcl needs to replace each character '?' with one of the three characters 'a', 'b' or 'c', such that the resulting string is beautiful. Please help him!

More formally, after replacing all characters '?', the condition $$$s_i \neq s_{i+1}$$$ should be satisfied for all $$$1 \leq i \leq |s| - 1$$$, where $$$|s|$$$ is the length of the string $$$s$$$.

## Input Format
The first line contains positive integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Next $$$t$$$ lines contain the descriptions of test cases.

Each line contains a non-empty string $$$s$$$ consisting of only characters 'a', 'b', 'c' and '?'.

It is guaranteed that in each test case a string $$$s$$$ has at least one character '?'. The sum of lengths of strings $$$s$$$ in all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case given in the input print the answer in the following format:

- If it is impossible to create a beautiful string, print "-1" (without quotes);
- Otherwise, print the resulting beautiful string after replacing all '?' characters. If there are multiple answers, you can print any of them.

## Examples
```input
3
a???cb
a??bbc
a?b?c
```
```output
ababcb
-1
acbac
```

## Note
In the first test case, all possible correct answers are "ababcb", "abcacb", "abcbcb", "acabcb" and "acbacb". The two answers "abcbab" and "abaabc" are incorrect, because you can replace only '?' characters and the resulting string must be beautiful.

In the second test case, it is impossible to create a beautiful string, because the $$$4$$$-th and $$$5$$$-th characters will be always equal.

In the third test case, the only answer is "acbac".

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
Creatnx has $$$n$$$ mirrors, numbered from $$$1$$$ to $$$n$$$. Every day, Creatnx asks exactly one mirror "Am I beautiful?". The $$$i$$$-th mirror will tell Creatnx that he is beautiful with probability $$$\frac{p_i}{100}$$$ for all $$$1 \le i \le n$$$.

Creatnx asks the mirrors one by one, starting from the $$$1$$$-st mirror. Every day, if he asks $$$i$$$-th mirror, there are two possibilities:

- The $$$i$$$-th mirror tells Creatnx that he is beautiful. In this case, if $$$i = n$$$ Creatnx will stop and become happy, otherwise he will continue asking the $$$i+1$$$-th mirror next day;
- In the other case, Creatnx will feel upset. The next day, Creatnx will start asking from the $$$1$$$-st mirror again.

You need to calculate the expected number of days until Creatnx becomes happy.

This number should be found by modulo $$$998244353$$$. Formally, let $$$M = 998244353$$$. 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}$$$.

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

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq 100$$$).

## Output Format
Print the answer modulo $$$998244353$$$ in a single line.

## Examples
```input
1
50
```
```output
2
```
-----
```input
3
10 20 50
```
```output
112
```

## Note
In the first test, there is only one mirror and it tells, that Creatnx is beautiful with probability $$$\frac{1}{2}$$$. So, the expected number of days until Creatnx becomes happy is $$$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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Let's call a positive integer composite if it has at least one divisor other than $$$1$$$ and itself. For example:

- the following numbers are composite: $$$1024$$$, $$$4$$$, $$$6$$$, $$$9$$$;
- the following numbers are not composite: $$$13$$$, $$$1$$$, $$$2$$$, $$$3$$$, $$$37$$$.

You are given a positive integer $$$n$$$. Find two composite integers $$$a,b$$$ such that $$$a-b=n$$$.

It can be proven that solution always exists.

## Input Format
The input contains one integer $$$n$$$ ($$$1 \leq n \leq 10^7$$$): the given integer.

## Output Format
Print two composite integers $$$a,b$$$ ($$$2 \leq a, b \leq 10^9, a-b=n$$$).

It can be proven, that solution always exists.

If there are several possible solutions, you can print any.

## Examples
```input
1
```
```output
9 8
```
-----
```input
512
```
```output
4608 4096
```

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
A new delivery of clothing has arrived today to the clothing store. This delivery consists of $$$a$$$ ties, $$$b$$$ scarves, $$$c$$$ vests and $$$d$$$ jackets.

The store does not sell single clothing items — instead, it sells suits of two types:

- a suit of the first type consists of one tie and one jacket;
- a suit of the second type consists of one scarf, one vest and one jacket.

Each suit of the first type costs $$$e$$$ coins, and each suit of the second type costs $$$f$$$ coins.

Calculate the maximum possible cost of a set of suits that can be composed from the delivered clothing items. Note that one item cannot be used in more than one suit (though some items may be left unused).

## Input Format
The first line contains one integer $$$a$$$ $$$(1 \le a \le 100\,000)$$$ — the number of ties.

The second line contains one integer $$$b$$$ $$$(1 \le b \le 100\,000)$$$ — the number of scarves.

The third line contains one integer $$$c$$$ $$$(1 \le c \le 100\,000)$$$ — the number of vests.

The fourth line contains one integer $$$d$$$ $$$(1 \le d \le 100\,000)$$$ — the number of jackets.

The fifth line contains one integer $$$e$$$ $$$(1 \le e \le 1\,000)$$$ — the cost of one suit of the first type.

The sixth line contains one integer $$$f$$$ $$$(1 \le f \le 1\,000)$$$ — the cost of one suit of the second type.

## Output Format
Print one integer — the maximum total cost of some set of suits that can be composed from the delivered items.

## Examples
```input
4
5
6
3
1
2
```
```output
6
```
-----
```input
12
11
13
20
4
6
```
```output
102
```
-----
```input
17
14
5
21
15
17
```
```output
325
```

## Note
It is possible to compose three suits of the second type in the first example, and their total cost will be $$$6$$$. Since all jackets will be used, it's impossible to add anything to this set.

The best course of action in the second example is to compose nine suits of the first type and eleven suits of the second type. The total cost is $$$9 \cdot 4 + 11 \cdot 6 = 102$$$.

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
There are $$$n$$$ blocks arranged in a row and numbered from left to right, starting from one. Each block is either black or white.

You may perform the following operation zero or more times: choose two adjacent blocks and invert their colors (white block becomes black, and vice versa).

You want to find a sequence of operations, such that they make all the blocks having the same color. You don't have to minimize the number of operations, but it should not exceed $$$3 \cdot n$$$. If it is impossible to find such a sequence of operations, you need to report it.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 200$$$) — the number of blocks.

The second line contains one string $$$s$$$ consisting of $$$n$$$ characters, each character is either "W" or "B". If the $$$i$$$-th character is "W", then the $$$i$$$-th block is white. If the $$$i$$$-th character is "B", then the $$$i$$$-th block is black.

## Output Format
If it is impossible to make all the blocks having the same color, print $$$-1$$$.

Otherwise, print an integer $$$k$$$ ($$$0 \le k \le 3 \cdot n$$$) — the number of operations. Then print $$$k$$$ integers $$$p_1, p_2, \dots, p_k$$$ $$$(1 \le p_j \le n - 1)$$$, where $$$p_j$$$ is the position of the left block in the pair of blocks that should be affected by the $$$j$$$-th operation.

If there are multiple answers, print any of them.

## Examples
```input
8
BWWWWWWB
```
```output
3
6 2 4
```
-----
```input
4
BWBB
```
```output
-1
```
-----
```input
5
WWWWW
```
```output
0
```
-----
```input
3
BWB
```
```output
2
2 1
```

## Note
In the first example, it is possible to make all blocks black in $$$3$$$ operations. Start with changing blocks $$$6$$$ and $$$7$$$, so the sequence is "BWWWWBBB". Then change blocks $$$2$$$ and $$$3$$$, so the sequence is "BBBWWBB". And finally, change blocks $$$4$$$ and $$$5$$$, so all blocks are black.

It is impossible to make all colors equal in the second example.

All blocks are already white in the third example.

In the fourth example it is possible to make all blocks white in two operations: first operation is to change blocks $$$2$$$ and $$$3$$$ (so the sequence is "BBW"), and then change blocks $$$1$$$ and $$$2$$$ (so all blocks are white).

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
At first, let's define function $$$f(x)$$$ as follows: $$$$$$ \begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right. \end{matrix} $$$$$$

We can see that if we choose some value $$$v$$$ and will apply function $$$f$$$ to it, then apply $$$f$$$ to $$$f(v)$$$, and so on, we'll eventually get $$$1$$$. Let's write down all values we get in this process in a list and denote this list as $$$path(v)$$$. For example, $$$path(1) = [1]$$$, $$$path(15) = [15, 14, 7, 6, 3, 2, 1]$$$, $$$path(32) = [32, 16, 8, 4, 2, 1]$$$.

Let's write all lists $$$path(x)$$$ for every $$$x$$$ from $$$1$$$ to $$$n$$$. The question is next: what is the maximum value $$$y$$$ such that $$$y$$$ is contained in at least $$$k$$$ different lists $$$path(x)$$$?

Formally speaking, you need to find maximum $$$y$$$ such that $$$\left| \{ x ~|~ 1 \le x \le n, y \in path(x) \} \right| \ge k$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$).

## Output Format
Print the only integer — the maximum value that is contained in at least $$$k$$$ paths.

## Examples
```input
11 3
```
```output
5
```
-----
```input
11 6
```
```output
4
```
-----
```input
20 20
```
```output
1
```
-----
```input
14 5
```
```output
6
```
-----
```input
1000000 100
```
```output
31248
```

## Note
In the first example, the answer is $$$5$$$, since $$$5$$$ occurs in $$$path(5)$$$, $$$path(10)$$$ and $$$path(11)$$$.

In the second example, the answer is $$$4$$$, since $$$4$$$ occurs in $$$path(4)$$$, $$$path(5)$$$, $$$path(8)$$$, $$$path(9)$$$, $$$path(10)$$$ and $$$path(11)$$$.

In the third example $$$n = k$$$, so the answer is $$$1$$$, since $$$1$$$ is the only number occuring in all paths for integers from $$$1$$$ to $$$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: 256.0 MB

# Problem
Polycarp has three sisters: Alice, Barbara, and Cerene. They're collecting coins. Currently, Alice has $$$a$$$ coins, Barbara has $$$b$$$ coins and Cerene has $$$c$$$ coins. Recently Polycarp has returned from the trip around the world and brought $$$n$$$ coins.

He wants to distribute all these $$$n$$$ coins between his sisters in such a way that the number of coins Alice has is equal to the number of coins Barbara has and is equal to the number of coins Cerene has. In other words, if Polycarp gives $$$A$$$ coins to Alice, $$$B$$$ coins to Barbara and $$$C$$$ coins to Cerene ($$$A+B+C=n$$$), then $$$a + A = b + B = c + C$$$.

Note that A, B or C (the number of coins Polycarp gives to Alice, Barbara and Cerene correspondingly) can be 0.

Your task is to find out if it is possible to distribute all $$$n$$$ coins between sisters in a way described above.

You have to answer $$$t$$$ independent test cases.

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

The next $$$t$$$ lines describe test cases. Each test case is given on a new line and consists of four space-separated integers $$$a, b, c$$$ and $$$n$$$ ($$$1 \le a, b, c, n \le 10^8$$$) — the number of coins Alice has, the number of coins Barbara has, the number of coins Cerene has and the number of coins Polycarp has.

## Output Format
For each test case, print "YES" if Polycarp can distribute all $$$n$$$ coins between his sisters and "NO" otherwise.

## Examples
```input
5
5 3 2 8
100 101 102 105
3 2 1 100000000
10 20 15 14
101 101 101 3
```
```output
YES
YES
NO
NO
YES
```

Now solve the problem and return the code.