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
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.
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
The city where Mocha lives in is called Zhijiang. There are $$$n+1$$$ villages and $$$2n-1$$$ directed roads in this city.

There are two kinds of roads:

- $$$n-1$$$ roads are from village $$$i$$$ to village $$$i+1$$$, for all $$$1\leq i \leq n-1$$$.
- $$$n$$$ roads can be described by a sequence $$$a_1,\ldots,a_n$$$. If $$$a_i=0$$$, the $$$i$$$-th of these roads goes from village $$$i$$$ to village $$$n+1$$$, otherwise it goes from village $$$n+1$$$ to village $$$i$$$, for all $$$1\leq i\leq n$$$.

Mocha plans to go hiking with Taki this weekend. To avoid the trip being boring, they plan to go through every village exactly once. They can start and finish at any villages. Can you help them to draw up a plan?

## Input Format
Each test contains multiple test cases.

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 20$$$) — 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 10^4$$$) — indicates that the number of villages is $$$n+1$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$). If $$$a_i=0$$$, it means that there is a road from village $$$i$$$ to village $$$n+1$$$. If $$$a_i=1$$$, it means that there is a road from village $$$n+1$$$ to village $$$i$$$.

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

## Output Format
For each test case, print a line with $$$n+1$$$ integers, where the $$$i$$$-th number is the $$$i$$$-th village they will go through. If the answer doesn't exist, print $$$-1$$$.

If there are multiple correct answers, you can print any one of them.

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

## Note
In the first test case, the city looks like the following graph:

So all possible answers are $$$(1 \to 4 \to 2 \to 3)$$$, $$$(1 \to 2 \to 3 \to 4)$$$.

In the second test case, the city looks like the following graph:

So all possible answers are $$$(4 \to 1 \to 2 \to 3)$$$, $$$(1 \to 2 \to 3 \to 4)$$$, $$$(3 \to 4 \to 1 \to 2)$$$, $$$(2 \to 3 \to 4 \to 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
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

A forest is an undirected graph without cycles (not necessarily connected).

Mocha and Diana are friends in Zhijiang, both of them have a forest with nodes numbered from $$$1$$$ to $$$n$$$, and they would like to add edges to their forests such that:

- After adding edges, both of their graphs are still forests.
- They add the same edges. That is, if an edge $$$(u, v)$$$ is added to Mocha's forest, then an edge $$$(u, v)$$$ is added to Diana's forest, and vice versa.

Mocha and Diana want to know the maximum number of edges they can add, and which edges to add.

## Input Format
The first line contains three integers $$$n$$$, $$$m_1$$$ and $$$m_2$$$ ($$$1 \le n \le 1000$$$, $$$0 \le m_1, m_2 < n$$$) — the number of nodes and the number of initial edges in Mocha's forest and Diana's forest.

Each of the next $$$m_1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Mocha's forest.

Each of the next $$$m_2$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Diana's forest.

## Output Format
The first line contains only one integer $$$h$$$, the maximum number of edges Mocha and Diana can add (in each forest).

Each of the next $$$h$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edge you add each time.

If there are multiple correct answers, you can print any one of them.

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

## Note
In the first example, we cannot add any edge.

In the second example, the initial forests are as follows.

We can add an edge $$$(2, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

A forest is an undirected graph without cycles (not necessarily connected).

Mocha and Diana are friends in Zhijiang, both of them have a forest with nodes numbered from $$$1$$$ to $$$n$$$, and they would like to add edges to their forests such that:

- After adding edges, both of their graphs are still forests.
- They add the same edges. That is, if an edge $$$(u, v)$$$ is added to Mocha's forest, then an edge $$$(u, v)$$$ is added to Diana's forest, and vice versa.

Mocha and Diana want to know the maximum number of edges they can add, and which edges to add.

## Input Format
The first line contains three integers $$$n$$$, $$$m_1$$$ and $$$m_2$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le m_1, m_2 < n$$$) — the number of nodes and the number of initial edges in Mocha's forest and Diana's forest.

Each of the next $$$m_1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Mocha's forest.

Each of the next $$$m_2$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Diana's forest.

## Output Format
The first line contains only one integer $$$h$$$, the maximum number of edges Mocha and Diana can add.

Each of the next $$$h$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edge you add each time.

If there are multiple correct answers, you can print any one of them.

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

## Note
In the first example, we cannot add any edge.

In the second example, the initial forests are as follows.

We can add an edge $$$(2, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Mocha wants to be an astrologer. There are $$$n$$$ stars which can be seen in Zhijiang, and the brightness of the $$$i$$$-th star is $$$a_i$$$.

Mocha considers that these $$$n$$$ stars form a constellation, and she uses $$$(a_1,a_2,\ldots,a_n)$$$ to show its state. A state is called mathematical if all of the following three conditions are satisfied:

- For all $$$i$$$ ($$$1\le i\le n$$$), $$$a_i$$$ is an integer in the range $$$[l_i, r_i]$$$.
- $$$\sum \limits _{i=1} ^ n a_i \le m$$$.
- $$$\gcd(a_1,a_2,\ldots,a_n)=1$$$.

Here, $$$\gcd(a_1,a_2,\ldots,a_n)$$$ denotes the greatest common divisor (GCD) of integers $$$a_1,a_2,\ldots,a_n$$$.

Mocha is wondering how many different mathematical states of this constellation exist. Because the answer may be large, you must find it modulo $$$998\,244\,353$$$.

Two states $$$(a_1,a_2,\ldots,a_n)$$$ and $$$(b_1,b_2,\ldots,b_n)$$$ are considered different if there exists $$$i$$$ ($$$1\le i\le n$$$) such that $$$a_i \ne b_i$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le 10^5$$$) — the number of stars and the upper bound of the sum of the brightness of stars.

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) — the range of the brightness of the $$$i$$$-th star.

## Output Format
Print a single integer — the number of different mathematical states of this constellation, modulo $$$998\,244\,353$$$.

## Examples
```input
2 4
1 3
1 2
```
```output
4
```
-----
```input
5 10
1 10
1 10
1 10
1 10
1 10
```
```output
251
```
-----
```input
5 100
1 94
1 96
1 91
4 96
6 97
```
```output
47464146
```

## Note
In the first example, there are $$$4$$$ different mathematical states of this constellation:

- $$$a_1=1$$$, $$$a_2=1$$$.
- $$$a_1=1$$$, $$$a_2=2$$$.
- $$$a_1=2$$$, $$$a_2=1$$$.
- $$$a_1=3$$$, $$$a_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: 256.0 MB

# Problem
You are given four integer values $$$a$$$, $$$b$$$, $$$c$$$ and $$$m$$$.

Check if there exists a string that contains:

- $$$a$$$ letters 'A';
- $$$b$$$ letters 'B';
- $$$c$$$ letters 'C';
- no other letters;
- exactly $$$m$$$ pairs of adjacent equal letters (exactly $$$m$$$ such positions $$$i$$$ that the $$$i$$$-th letter is equal to the $$$(i+1)$$$-th one).

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

Each of the next $$$t$$$ lines contains the description of the testcase — four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$m$$$ ($$$1 \le a, b, c \le 10^8$$$; $$$0 \le m \le 10^8$$$).

## Output Format
For each testcase print "YES" if there exists a string that satisfies all the requirements. Print "NO" if there are no such strings.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

## Examples
```input
3
2 2 1 0
1 1 1 1
1 2 3 2
```
```output
YES
NO
YES
```

## Note
In the first testcase strings "ABCAB" or "BCABA" satisfy the requirements. There exist other possible strings.

In the second testcase there's no way to put adjacent equal letters if there's no letter that appears at least twice.

In the third testcase string "CABBCC" satisfies the requirements. There exist other possible strings.

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
Ivan is playing yet another roguelike computer game. He controls a single hero in the game. The hero has $$$n$$$ equipment slots. There is a list of $$$c_i$$$ items for the $$$i$$$-th slot, the $$$j$$$-th of them increases the hero strength by $$$a_{i,j}$$$. The items for each slot are pairwise distinct and are listed in the increasing order of their strength increase. So, $$$a_{i,1} < a_{i,2} < \dots < a_{i,c_i}$$$.

For each slot Ivan chooses exactly one item. Let the chosen item for the $$$i$$$-th slot be the $$$b_i$$$-th item in the corresponding list. The sequence of choices $$$[b_1, b_2, \dots, b_n]$$$ is called a build.

The strength of a build is the sum of the strength increases of the items in it. Some builds are banned from the game. There is a list of $$$m$$$ pairwise distinct banned builds. It's guaranteed that there's at least one build that's not banned.

What is the build with the maximum strength that is not banned from the game? If there are multiple builds with maximum strength, print any of them.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10$$$) — the number of equipment slots.

The $$$i$$$-th of the next $$$n$$$ lines contains the description of the items for the $$$i$$$-th slot. First, one integer $$$c_i$$$ ($$$1 \le c_i \le 2 \cdot 10^5$$$) — the number of items for the $$$i$$$-th slot. Then $$$c_i$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,c_i}$$$ ($$$1 \le a_{i,1} < a_{i,2} < \dots < a_{i,c_i} \le 10^8$$$).

The sum of $$$c_i$$$ doesn't exceed $$$2 \cdot 10^5$$$.

The next line contains a single integer $$$m$$$ ($$$0 \le m \le 10^5$$$) — the number of banned builds.

Each of the next $$$m$$$ lines contains a description of a banned build — a sequence of $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le c_i$$$).

The builds are pairwise distinct, and there's at least one build that's not banned.

## Output Format
Print the build with the maximum strength that is not banned from the game. If there are multiple builds with maximum strength, print any of them.

## Examples
```input
3
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
3 2 2
```
```output
2 2 3
```
-----
```input
3
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
2 2 3
```
```output
1 2 3
```
-----
```input
3
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
2 2 3
```
```output
3 2 2
```
-----
```input
4
1 10
1 4
1 7
1 3
0
```
```output
1 1 1 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: 256.0 MB

# Problem
A matrix of size $$$n \times m$$$, such that each cell of it contains either $$$0$$$ or $$$1$$$, is considered beautiful if the sum in every contiguous submatrix of size $$$2 \times 2$$$ is exactly $$$2$$$, i. e. every "square" of size $$$2 \times 2$$$ contains exactly two $$$1$$$'s and exactly two $$$0$$$'s.

You are given a matrix of size $$$n \times m$$$. Initially each cell of this matrix is empty. Let's denote the cell on the intersection of the $$$x$$$-th row and the $$$y$$$-th column as $$$(x, y)$$$. You have to process the queries of three types:

- $$$x$$$ $$$y$$$ $$$-1$$$ — clear the cell $$$(x, y)$$$, if there was a number in it;
- $$$x$$$ $$$y$$$ $$$0$$$ — write the number $$$0$$$ in the cell $$$(x, y)$$$, overwriting the number that was there previously (if any);
- $$$x$$$ $$$y$$$ $$$1$$$ — write the number $$$1$$$ in the cell $$$(x, y)$$$, overwriting the number that was there previously (if any).

After each query, print the number of ways to fill the empty cells of the matrix so that the resulting matrix is beautiful. Since the answers can be large, print them modulo $$$998244353$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n, m \le 10^6$$$; $$$1 \le k \le 3 \cdot 10^5$$$) — the number of rows in the matrix, the number of columns, and the number of queries, respectively.

Then $$$k$$$ lines follow, the $$$i$$$-th of them contains three integers $$$x_i$$$, $$$y_i$$$, $$$t_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$; $$$-1 \le t_i \le 1$$$) — the parameters for the $$$i$$$-th query.

## Output Format
For each query, print one integer — the number of ways to fill the empty cells of the matrix after the respective query, taken modulo $$$998244353$$$.

## Examples
```input
2 2 7
1 1 1
1 2 1
2 1 1
1 1 0
1 2 -1
2 1 -1
1 1 -1
```
```output
3
1
0
1
2
3
6
```

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: 7.0 seconds
Memory limit: 512.0 MB

# Problem
A subarray of array $$$a$$$ from index $$$l$$$ to the index $$$r$$$ is the array $$$[a_l, a_{l+1}, \dots, a_{r}]$$$. The number of occurrences of the array $$$b$$$ in the array $$$a$$$ is the number of subarrays of $$$a$$$ such that they are equal to $$$b$$$.

You are given $$$n$$$ arrays $$$A_1, A_2, \dots, A_n$$$; the elements of these arrays are integers from $$$1$$$ to $$$k$$$. You have to build an array $$$a$$$ consisting of $$$m$$$ integers from $$$1$$$ to $$$k$$$ in such a way that, for every given subarray $$$A_i$$$, the number of occurrences of $$$A_i$$$ in the array $$$a$$$ is not less than the number of occurrences of each non-empty subarray of $$$A_i$$$ in $$$a$$$. Note that if $$$A_i$$$ doesn't occur in $$$a$$$, and no subarray of $$$A_i$$$ occurs in $$$a$$$, this condition is still met for $$$A_i$$$.

Your task is to calculate the number of different arrays $$$a$$$ you can build, and print it modulo $$$998244353$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m, k \le 3 \cdot 10^5$$$) — the number of the given arrays, the desired length of the array $$$a$$$, and the upper bound on the values in the arrays.

Then $$$n$$$ lines follow. The $$$i$$$-th line represents the array $$$A_i$$$. The first integer in the $$$i$$$-th line is $$$c_i$$$ ($$$1 \le c_i \le m$$$) — the number of elements in $$$A_i$$$; then, $$$c_i$$$ integers from $$$1$$$ to $$$k$$$ follow — the elements of the array $$$A_i$$$.

Additional constraint on the input: $$$\sum\limits_{i=1}^n c_i \le 3 \cdot 10^5$$$; i. e., the number of elements in the given arrays in total does not exceed $$$3 \cdot 10^5$$$.

## Output Format
Print one integer — the number of different arrays $$$a$$$ you can build, taken modulo $$$998244353$$$.

## Examples
```input
2 4 3
2 1 2
1 3
```
```output
5
```
-----
```input
2 4 3
2 1 2
3 3 2 1
```
```output
0
```
-----
```input
1 42 1337
2 13 31
```
```output
721234447
```

Now solve the problem and return the code.