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
There is an $$$n \times m$$$ grid of white and black squares. In one operation, you can select any two squares of the same color, and color all squares in the subrectangle between them that color.

Formally, if you select positions $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, both of which are currently the same color $$$c$$$, set the color of all $$$(x, y)$$$ where $$$\min(x_1, x_2) \le x \le \max(x_1, x_2)$$$ and $$$\min(y_1, y_2) \le y \le \max(y_1, y_2)$$$ to $$$c$$$.

This diagram shows a sequence of two possible operations on a grid:

Is it possible for all squares in the grid to be the same color, after performing any number of operations (possibly zero)?

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 500$$$) — the number of rows and columns in the grid, respectively.

Each of the next $$$n$$$ lines contains $$$m$$$ characters 'W' and 'B' — the initial colors of the squares of the grid.

It is guaranteed that the sum of $$$n\cdot m$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.

## Output Format
For each test case, print "YES" if it is possible to make all squares in the grid the same color, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Examples
```input
8
2 1
W
B
6 6
WWWWBW
WBWWWW
BBBWWW
BWWWBB
WWBWBB
BBBWBW
1 1
W
2 2
BB
BB
3 4
BWBW
WBWB
BWBW
4 2
BB
BB
WW
WW
4 4
WWBW
BBWB
WWBB
BBBB
1 5
WBBWB
```
```output
NO
YES
YES
YES
YES
NO
YES
NO
```

## Note
In the first example, it is impossible to ever change the color of any square with an operation, so we output NO.

The second example is the case pictured above. As shown in that diagram, it is possible for all squares to be white after two operations, so we output YES.

In the third and fourth examples, all squares are already the same color, so we output YES.

In the fifth example we can do everything in two operations. First, select positions $$$(2, 1)$$$ and $$$(1, 4)$$$ and color all squares with $$$1 \le x \le 2$$$ and $$$1 \le y \le 4$$$ to white. Then, select positions $$$(2, 1)$$$ and $$$(3, 4)$$$ and color all squares with $$$2 \le x \le 3$$$ and $$$1 \le y \le 4$$$ to white. After these two operations all squares 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: 512.0 MB

# Problem
Monocarp's current password on Codeforces is a string $$$s$$$, consisting of lowercase Latin letters. Monocarp thinks that his current password is too weak, so he wants to insert exactly one lowercase Latin letter into the password to make it stronger. Monocarp can choose any letter and insert it anywhere, even before the first character or after the last character.

Monocarp thinks that the password's strength is proportional to the time it takes him to type the password. The time it takes to type the password is calculated as follows:

- the time to type the first character is $$$2$$$ seconds;
- for each character other than the first, the time it takes to type it is $$$1$$$ second if it is the same as the previous character, or $$$2$$$ seconds otherwise.

For example, the time it takes to type the password abacaba is $$$14$$$; the time it takes to type the password a is $$$2$$$; the time it takes to type the password aaabacc is $$$11$$$.

You have to help Monocarp — insert a lowercase Latin letter into his password so that the resulting password takes the maximum possible amount of time to type.

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

Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 10$$$), consisting of lowercase Latin letters.

## Output Format
For each test case, print one line containing the new password — a string which can be obtained from $$$s$$$ by inserting one lowercase Latin letter. The string you print should have the maximum possible required time to type it. If there are multiple answers, print any of them.

## Examples
```input
4
a
aaa
abb
password
```
```output
wa
aada
abcb
pastsword
```

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 is a grid, consisting of $$$2$$$ rows and $$$n$$$ columns. Each cell of the grid is either free or blocked.

A free cell $$$y$$$ is reachable from a free cell $$$x$$$ if at least one of these conditions holds:

- $$$x$$$ and $$$y$$$ share a side;
- there exists a free cell $$$z$$$ such that $$$z$$$ is reachable from $$$x$$$ and $$$y$$$ is reachable from $$$z$$$.

A connected region is a set of free cells of the grid such that all cells in it are reachable from one another, but adding any other free cell to the set violates this rule.

For example, consider the following layout, where white cells are free, and dark grey cells are blocked:

There are $$$3$$$ regions in it, denoted with red, green and blue color respectively:

The given grid contains at most $$$1$$$ connected region. Your task is to calculate the number of free cells meeting the following constraint:

- if this cell is blocked, the number of connected regions becomes exactly $$$3$$$.

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

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

The $$$i$$$-th of the next two lines contains a description of the $$$i$$$-th row of the grid — the string $$$s_i$$$, consisting of $$$n$$$ characters. Each character is either . (denoting a free cell) or x (denoting a blocked cell).

Additional constraint on the input:

- the given grid contains at most $$$1$$$ connected region;
- the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of cells such that the number of connected regions becomes $$$3$$$ if this cell is blocked.

## Examples
```input
4
8
.......x
.x.xx...
2
..
..
3
xxx
xxx
9
..x.x.x.x
x.......x
```
```output
1
0
0
2
```

## Note
In the first test case, if the cell $$$(1, 3)$$$ is blocked, the number of connected regions becomes $$$3$$$ (as shown in the picture from the statement).

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
You are given a rooted tree, consisting of $$$n$$$ vertices. The vertices in the tree are numbered from $$$1$$$ to $$$n$$$, and the root is the vertex $$$1$$$. The value $$$a_i$$$ is written at the $$$i$$$-th vertex.

You can perform the following operation any number of times (possibly zero): choose a vertex $$$v$$$ which has at least one child; increase $$$a_v$$$ by $$$1$$$; and decrease $$$a_u$$$ by $$$1$$$ for all vertices $$$u$$$ that are in the subtree of $$$v$$$ (except $$$v$$$ itself). However, after each operation, the values on all vertices should be non-negative.

Your task is to calculate the maximum possible value written at the root using the aforementioned operation.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the initial values written at vertices.

The third line contains $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the parent of the $$$i$$$-th vertex in the tree. Vertex $$$1$$$ is the root.

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the maximum possible value written at the root using the aforementioned operation.

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

## Note
In the first test case, the following sequence of operations is possible:

- perform the operation on $$$v=3$$$, then the values on the vertices will be $$$[0, 1, 1, 1]$$$;
- perform the operation on $$$v=1$$$, then the values on the vertices will be $$$[1, 0, 0, 0]$$$.

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

# Problem
Monocarp is playing a computer game. He starts the game being level $$$1$$$. He is about to fight $$$n$$$ monsters, in order from $$$1$$$ to $$$n$$$. The level of the $$$i$$$-th monster is $$$a_i$$$.

For each monster in the given order, Monocarp's encounter goes as follows:

- if Monocarp's level is strictly higher than the monster's level, the monster flees (runs away);
- otherwise, Monocarp fights the monster.

After every $$$k$$$-th fight with a monster (fleeing monsters do not count), Monocarp's level increases by $$$1$$$. So, his level becomes $$$2$$$ after $$$k$$$ monsters he fights, $$$3$$$ after $$$2k$$$ monsters, $$$4$$$ after $$$3k$$$ monsters, and so on.

You need to process $$$q$$$ queries of the following form:

- $$$i~x$$$: will Monocarp fight the $$$i$$$-th monster (or will this monster flee) if the parameter $$$k$$$ is equal to $$$x$$$?

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of monsters and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the levels of the monsters.

In the $$$j$$$-th of the following $$$q$$$ lines, two integers $$$i$$$ and $$$x$$$ ($$$1 \le i, x \le n$$$) — the index of the monster and the number of fights required for a level up in the $$$j$$$-th query.

## Output Format
For each query, output "YES", if Monocarp will fight the $$$i$$$-th monster in this query, and "NO", if the $$$i$$$-th monster flees.

## Examples
```input
4 16
2 1 2 1
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4
```
```output
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
```
-----
```input
7 15
1 1 2 1 1 1 1
5 3
2 2
2 2
1 6
5 1
5 5
7 7
3 5
7 4
4 3
2 5
1 2
5 6
4 1
6 1
```
```output
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You have $$$n$$$ chips, and you are going to place all of them in one of $$$x$$$ points, numbered from $$$1$$$ to $$$x$$$. There can be multiple chips in each point.

After placing the chips, you can perform the following four operations (in any order, any number of times):

- choose a chip in point $$$i \ge 3$$$, remove it and place two chips: one in $$$i-1$$$, one in $$$i-2$$$;
- choose two chips in adjacent points $$$i$$$ and $$$i+1$$$, remove them and place a new chip in $$$i+2$$$;
- choose a chip in point $$$1$$$ and move it to $$$2$$$;
- choose a chip in point $$$2$$$ and move it to $$$1$$$.

Note that the coordinates of the chips you place during the operations cannot be less than $$$1$$$, but can be greater than $$$x$$$.

Denote the cost of chip placement as the minimum number of chips which can be present on the line after you perform these operations, starting from the placement you've chosen.

For example, the cost of placing two chips in points $$$3$$$ and one chip in point $$$5$$$ is $$$2$$$, because you can reduce the number of chips to $$$2$$$ as follows:

- choose a chip in point $$$3$$$, remove it, place a chip in $$$1$$$ and another chip in $$$2$$$;
- choose the chips in points $$$2$$$ and $$$3$$$, remove them and place a chip in $$$4$$$;
- choose the chips in points $$$4$$$ and $$$5$$$, remove them and place a chip in $$$6$$$.

You are given three integers $$$n$$$, $$$x$$$ and $$$m$$$. Calculate the number of placements of exactly $$$n$$$ chips in points from $$$1$$$ to $$$x$$$ having cost equal to $$$m$$$, and print it modulo $$$998244353$$$. Two placements are considered different if the number of chips in some point differs between these placements.

## Input Format
The only line contains three integers $$$n$$$, $$$x$$$ and $$$m$$$ ($$$1 \le m \le n \le 1000$$$; $$$2 \le x \le 10$$$).

## Output Format
Print one integer — the number of placements with cost equal to $$$m$$$, taken modulo $$$998244353$$$.

## Examples
```input
2 3 1
```
```output
5
```
-----
```input
42 10 5
```
```output
902673363
```
-----
```input
1000 10 8
```
```output
187821763
```

## Note
In the first example, there are five ways to place $$$2$$$ chips in points from $$$1$$$ to $$$3$$$ so that the cost is $$$1$$$:

- $$$(1, 1)$$$;
- $$$(1, 2)$$$;
- $$$(1, 3)$$$;
- $$$(2, 2)$$$;
- $$$(2, 3)$$$.

Now solve the problem and return the code.