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
Recently, Tema and Vika celebrated Family Day. Their friend Arina gave them a carpet, which can be represented as an $$$n \cdot m$$$ table of lowercase Latin letters.

Vika hasn't seen the gift yet, but Tema knows what kind of carpets she likes. Vika will like the carpet if she can read her name on. She reads column by column from left to right and chooses one or zero letters from current column.

Formally, the girl will like the carpet if it is possible to select four distinct columns in order from left to right such that the first column contains "v", the second one contains "i", the third one contains "k", and the fourth one contains "a".

Help Tema understand in advance whether Vika will like Arina's gift.

## Input Format
Each test consists of multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 20$$$) — the sizes of the carpet.

The next $$$n$$$ lines contain $$$m$$$ lowercase Latin letters each, describing the given carpet.

## Output Format
For each set of input data, output "YES" if Vika will like the carpet, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

## Examples
```input
5
1 4
vika
3 3
bad
car
pet
4 4
vvvv
iiii
kkkk
aaaa
4 4
vkak
iiai
avvk
viaa
4 7
vbickda
vbickda
vbickda
vbickda
```
```output
YES
NO
YES
NO
YES
```

## Note
In the first sample, Vika can read her name from left to right.

In the second sample, Vika cannot read the character "v", so she will not like the carpet.

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
Tema and Vika are playing the following game.

First, Vika comes up with a sequence of positive integers $$$a$$$ of length $$$m$$$ and writes it down on a piece of paper. Then she takes a new piece of paper and writes down the sequence $$$b$$$ according to the following rule:

- First, she writes down $$$a_1$$$.
- Then, she writes down only those $$$a_i$$$ ($$$2 \le i \le m$$$) such that $$$a_{i - 1} \le a_i$$$. Let the length of this sequence be denoted as $$$n$$$.

For example, from the sequence $$$a=[4, 3, 2, 6, 3, 3]$$$, Vika will obtain the sequence $$$b=[4, 6, 3]$$$.

She then gives the piece of paper with the sequence $$$b$$$ to Tema. He, in turn, tries to guess the sequence $$$a$$$.

Tema considers winning in such a game highly unlikely, but still wants to find at least one sequence $$$a$$$ that could have been originally chosen by Vika. Help him and output any such sequence.

Note that the length of the sequence you output should not exceed the input sequence length by more than two times.

## Input Format
Each test consists of multiple test cases. The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. This is followed by a description of the test cases.

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

The second line of each test case contains $$$n$$$ integers $$$b_1, b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the elements of the sequence.

The sum of the values of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output two lines. In the first line, output a single integer $$$m$$$ — the length of the sequence ($$$n \le m \le 2 \cdot n$$$). In the second line, output $$$m$$$ integers $$$a_1, a_2, a_3, \dots, a_m$$$ ($$$1 \le a_i \le 10^9$$$) — the assumed sequence that Vika could have written on the first piece of paper.

If there are multiple suitable sequences, you can output any of them.

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

## Note
The first sample is explained in the problem statement.

In the second sample, Vika could have chosen the original sequence.

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
Tema decided to improve his ice cream making skills. He has already learned how to make ice cream in a cone using exactly two balls.

Before his ice cream obsession, Tema was interested in mathematics. Therefore, he is curious about the minimum number of balls he needs to have in order to make exactly $$$n$$$ different types of ice cream.

There are plenty possible ice cream flavours: $$$1, 2, 3, \dots$$$. Tema can make two-balls ice cream with any flavours (probably the same).

Two ice creams are considered different if their sets of ball flavours are different. For example, $$$\{1, 2\} = \{2, 1\}$$$, but $$$\{1, 1\} \neq \{1, 2\}$$$.

For example, having the following ice cream balls: $$$\{1, 1, 2\}$$$, Tema can make only two types of ice cream: $$$\{1, 1\}$$$ and $$$\{1, 2\}$$$.

Note, that Tema do not need to make all the ice cream cones at the same time. This means that he making ice cream cones independently. Also in order to make a following cone $$$\{x, x\}$$$ for some $$$x$$$, Tema needs at least $$$2$$$ balls of type $$$x$$$.

Help Tema answer this question. It can be shown that answer always exist.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — the number of ice cream types that Tema wants to make.

## Output Format
For each test case, output a single integer — the minimum number of balls Tema needs to buy.

## Examples
```input
5
1
3
6
179
1000000000000000000
```
```output
2
3
4
27
2648956421
```

## Note
In the first sample, it is enough to have following balls types: $$$\{1, 1\}$$$. Note, that set $$$\{1\}$$$ if not enough since we need at least $$$2$$$ balls of a type $$$1$$$ in order to make such cone $$$\{1, 1\}$$$.

In the second sample, it is not possible to make it with $$$2$$$ balls, but it can be done with these balls: $$$\{1, 2, 3\}$$$.

In the third sample, $$$\{1, 2, 3, 4\}$$$ is optimal answer, so we can get following ice cream cones: $$$\{1, 2\}$$$, $$$\{1, 3\}$$$, $$$\{1, 4\}$$$, $$$\{2, 3\}$$$, $$$\{2, 4\}$$$, $$$\{3, 4\}$$$.

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

# Problem
A portal of dark forces has opened at the border of worlds, and now the whole world is under a terrible threat. To close the portal and save the world, you need to defeat $$$n$$$ monsters that emerge from the portal one after another.

Only the sorceress Vika can handle this. She possesses two magical powers — water magic and fire magic. In one second, Vika can generate $$$w$$$ units of water mana and $$$f$$$ units of fire mana. She will need mana to cast spells. Initially Vika have $$$0$$$ units of water mana and $$$0$$$ units of fire mana.

Each of the $$$n$$$ monsters that emerge from the portal has its own strength, expressed as a positive integer. To defeat the $$$i$$$-th monster with strength $$$s_i$$$, Vika needs to cast a water spell or a fire spell of at least the same strength. In other words, Vika can spend at least $$$s_i$$$ units of water mana on a water spell, or at least $$$s_i$$$ units of fire mana on a fire spell.

Vika can create and cast spells instantly. Vika can cast an unlimited number of spells every second as long she has enough mana for that.

The sorceress wants to save the world as quickly as possible, so tell her how much time she will need.

## Input Format
Each test consists of several test cases. The first line of each test contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains two integers $$$w$$$, $$$f$$$ ($$$1 \le w, f \le 10^9$$$) — the amount of water and fire mana that Vika can generate per second.

The second line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of monsters.

The third line of each test case contains $$$n$$$ integers $$$s_1, s_2, s_3, \dots, s_n$$$ ($$$1 \le s_i \le 10^4$$$) — the strengths of the monsters.

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

## Output Format
For each test case, output a single integer — the minimum time in seconds that Vika will need to defeat all the monsters.

## Examples
```input
4
2 3
3
2 6 7
37 58
1
93
190 90
2
23 97
13 4
4
10 10 2 45
```
```output
3
2
1
5
```

## Note
In the first sample, after the first second, Vika can spend $$$2$$$ units of fire mana to kill the first monster. Then she has $$$2$$$ units of water mana and $$$1$$$ unit of fire mana. After the third second, she will have $$$6$$$ units of water mana and $$$7$$$ units of fire mana at her disposal. This will be enough to immediately kill the second and third monsters.

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

# Problem
You are given an undirected connected graph in which any two distinct simple cycles do not have common vertices. Since the graph can be very large, it is given to you in a compressed form: for each edge, you are also given a number $$$d$$$, which indicates that there are $$$d$$$ additional vertices on this edge.

You need to assign a weight to each vertex and each edge of the graph — an integer from $$$1$$$ to $$$3$$$.

An edge of the graph is called good if the bitwise XOR of the weights of its adjacent vertices is not equal to $$$0$$$ and not equal to the weight of that edge.

Similarly, a vertex of the graph is called good if the bitwise XOR of the weights of its adjacent edges is not equal to $$$0$$$ and not equal to the weight of that vertex.

You need to determine how many ways there are to assign weights to the vertices and edges of the graph so that all vertices and edges are good. Since the answer can be quite large, you need to calculate the remainder of the answer divided by $$$998\,244\,353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of vertices and the number of edges in the graph ($$$2 \le n \le 5 \cdot 10^5$$$, $$$n - 1 \le m \le 10^6$$$).

Each of the next $$$m$$$ lines contains three integers $$$a_i, b_i$$$, and $$$d_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$, $$$0 \le d_i \le 10^9$$$), indicating that there is an edge in the graph connecting vertices $$$a_i$$$ and $$$b_i$$$. Additionally, on this edge, there are $$$d_i$$$ additional vertices. It is guaranteed that the given graph is connected, there are no multiple edges, loops, and any two distinct simple cycles of the graph do not have common vertices.

## Output Format
Output a single integer — the answer to the problem modulo $$$998\,244\,353$$$.

## Examples
```input
3 3
1 2 0
2 3 0
3 1 0
```
```output
12
```
-----
```input
6 7
1 2 0
2 3 0
3 1 0
4 5 0
5 6 0
6 4 0
4 3 0
```
```output
0
```
-----
```input
2 1
2 1 777
```
```output
0
```
-----
```input
3 3
1 2 0
2 3 110850709
3 1 1000000000
```
```output
179179178
```

## Note
In the first test, the graph is a simple cycle of $$$3$$$ vertices. It can be shown, that there are exactly $$$12$$$ ways to assign weights, to make all vertexes and edges good.

In the second test, the graph has the form of two simple cycles of $$$3$$$ vertices connected by an edge. It can be shown that for such a graph there are no ways to arrange weights so that all vertices and edges are good.

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

# Problem
You are playing a word puzzle. The puzzle starts with a $$$3$$$ by $$$3$$$ grid, where each cell contains either the letter A, B, or C.

The goal of this puzzle is to find the lexicographically smallest possible word of length $$$3$$$. The word can be formed by choosing three different cells where the cell containing the first letter is adjacent to the cell containing the second letter, and the cell containing the second letter is adjacent to the cell containing the third letter.

Two cells are adjacent to each other if they share a border or a corner, as shown in the following illustration. Formally, if $$$(r, c)$$$ denotes the cell in the $$$r$$$-th row and $$$c$$$-th column, then cell $$$(r, c)$$$ is adjacent to cell $$$(r, c + 1)$$$, $$$(r - 1, c + 1)$$$, $$$(r - 1, c)$$$, $$$(r - 1, c - 1)$$$, $$$(r, c - 1)$$$, $$$(r + 1, c - 1)$$$, $$$(r + 1, c)$$$, and $$$(r + 1, c + 1)$$$.

Determine the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.

A string $$$s$$$ of length $$$n$$$ is lexicographically smaller than string $$$t$$$ of the same length if there exists an integer $$$1 \leq i \leq n$$$ such that $$$s_j = t_j$$$ for all $$$1 \leq j < i$$$, and $$$s_i < t_i$$$ in alphabetical order. The following illustration shows some examples on some grids and their the lexicographically smallest possible word of length $$$3$$$ that you can find within the grids.

## Input Format
Input consists of three lines, each containing three letters, representing the puzzle grid. Each letter in the grid can only be either A, B, or C.

## Output Format
Output the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.

## Examples
```input
BCB
CAC
BCB
```
```output
ABC
```
-----
```input
BCB
CCC
CCA
```
```output
ACB
```
-----
```input
ACA
CBC
ACA
```
```output
ABA
```
-----
```input
ACA
CAC
ACA
```
```output
AAA
```
-----
```input
CCC
CBC
CCC
```
```output
BCC
```

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

# Problem
You are given $$$N$$$ buttons (numbered from $$$1$$$ to $$$N$$$) and $$$N$$$ lamps (numbered from $$$1$$$ to $$$N$$$). Each lamp can either be on or off. Initially, lamp $$$i$$$ is on if $$$A_i = 1$$$, and off if $$$A_i = 0$$$.

Button $$$i$$$ is connected to lamp $$$i - 1$$$ (if $$$i > 1$$$) and lamp $$$i + 1$$$ (if $$$i < N$$$). In one move, you can press a button $$$i$$$ only if lamp $$$i$$$ is on. When a button is pressed, the state of the lamps connected to this button is toggled. Formally, the lamps will be on if it was off previously, and the lamps will be off if it was on previously. Note that lamp $$$i$$$ is not connected to button $$$i$$$, thus, the state of lamp $$$i$$$ does not change if button $$$i$$$ is pressed.

After zero or more moves, you want lamp $$$i$$$ to be on if $$$B_i = 1$$$, and off if $$$B_i = 0$$$. Determine if it is possible to achieve this task.

## Input Format
This problem has multiple test cases. The first line consists of an integer $$$T$$$ ($$$1 \leq T \leq 1000$$$), which represents the number of test cases. Each test case consists of three lines.

The first line of each test case consists of an integer $$$N$$$ ($$$3 \le N \le 200\,000$$$). The sum of $$$N$$$ over all test cases does not exceed $$$200\,000$$$.

The second line of each test case consists of a string $$$A$$$ of length $$$N$$$. Each character of $$$A$$$ can either be 0 or 1. The $$$i$$$-th character represents the initial state of lamp $$$i$$$.

The third line of each test case consists of a string $$$A$$$ of length $$$N$$$. Each character of $$$B$$$ can either be 0 or 1. The $$$i$$$-th character represents the desired final state of lamp $$$i$$$.

## Output Format
For each test case, output YES in a single line if the final state of all lamps can be reached after zero or more moves, or NO otherwise.

## Examples
```input
2
4
0101
0100
3
000
010
```
```output
YES
NO
```
-----
```input
5
7
0101011
1111010
5
11111
00000
4
1101
1101
6
101010
100100
3
000
000
```
```output
NO
NO
YES
YES
YES
```

## Note
Explanation for the sample input/output #1

For the first test case, by pressing the buttons $$$4, 2, 4, 3, 1, 2$$$ in sequence, the condition of the buttons changes as: $$$0101 \rightarrow 0111 \rightarrow 1101 \rightarrow 1111 \rightarrow 1010 \rightarrow 1110 \rightarrow 0100$$$.

For the second test case, you are unable to press any button, hence it is impossible to reach the final state.

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

# Problem
You are currently researching the Merge Sort algorithm. Merge Sort is a sorting algorithm that is based on the principle of Divide and Conquer. It works by dividing an array into two subarrays of equal length, sorting each subarrays, then merging the sorted subarrays back together to form the final sorted array.

You are particularly interested in the merging routine. Common merge implementation will combine two subarrays by iteratively comparing their first elements, and move the smaller one to a new merged array. More precisely, the merge algorithm can be presented by the following pseudocode.

During your research, you are keen to understand the behaviour of the merge algorithm when arrays $$$A$$$ and $$$B$$$ are not necessarily sorted. For example, if $$$A = [3, 1, 6]$$$ and $$$B = [4, 5, 2]$$$, then $$$\text{Merge}(A, B) = [3, 1, 4, 5, 2, 6]$$$.

To further increase the understanding of the merge algorithm, you decided to work on the following problem. You are given an array $$$C$$$ of length $$$2 \cdot N$$$ such that it is a permutation of $$$1$$$ to $$$2 \cdot N$$$. Construct any two arrays $$$A$$$ and $$$B$$$ of the same length $$$N$$$, such that $$$\text{Merge}(A, B) = C$$$, or determine if it is impossible to do so.

## Input Format
The first line consists of an integer $$$N$$$ ($$$1 \leq N \leq 1000$$$).

The following line consists of $$$2 \cdot N$$$ integers $$$C_i$$$. The array $$$C$$$ is a permutation of $$$1$$$ to $$$2 \cdot N$$$.

## Output Format
If it is impossible to construct two arrays $$$A$$$ and $$$B$$$ of length $$$N$$$ such that $$$\text{Merge}(A, B) = C$$$, then output -1.

Otherwise, output the arrays $$$A$$$ and $$$B$$$ in two lines. The first line consists of $$$N$$$ integers $$$A_i$$$. The second line consists of $$$N$$$ integers $$$B_i$$$. If there are several possible answers, output any of them.

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

## Note
Explanation for the sample input/output #1

The solution $$$A = [3, 1, 4]$$$ and $$$B = [5, 2, 6]$$$ is also correct.

Explanation for the sample input/output #2

The solution $$$A = [1, 2, 3, 4]$$$ and $$$B = [5, 6, 7, 8]$$$ is also correct.

Now solve the problem and return the code.