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
$$$n$$$ players are playing a game.

There are two different maps in the game. For each player, we know his strength on each map. When two players fight on a specific map, the player with higher strength on that map always wins. No two players have the same strength on the same map.

You are the game master and want to organize a tournament. There will be a total of $$$n-1$$$ battles. While there is more than one player in the tournament, choose any map and any two remaining players to fight on it. The player who loses will be eliminated from the tournament.

In the end, exactly one player will remain, and he is declared the winner of the tournament. For each player determine if he can win the tournament.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$, $$$a_i \neq a_j$$$ for $$$i \neq j$$$), where $$$a_i$$$ is the strength of the $$$i$$$-th player on the first map.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$, $$$b_i \neq b_j$$$ for $$$i \neq j$$$), where $$$b_i$$$ is the strength of the $$$i$$$-th player on the second map.

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

## Output Format
For each test case print a string of length $$$n$$$. $$$i$$$-th character should be "1" if the $$$i$$$-th player can win the tournament, or "0" otherwise.

## Examples
```input
3
4
1 2 3 4
1 2 3 4
4
11 12 20 21
44 22 11 30
1
1000000000
1000000000
```
```output
0001
1111
1
```

## Note
In the first test case, the $$$4$$$-th player will beat any other player on any game, so he will definitely win the tournament.

In the second test case, everyone can be a winner.

In the third test case, there is only one player. Clearly, he will win the tournament.

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 are given $$$n$$$ dominoes. Each domino has a left and a right cell. Each cell can be colored either black or white. Some cells are already colored, while some aren't yet.

The coloring is said to be valid if and only if it is possible to rearrange the dominoes in some order such that for each $$$1 \le i \le n$$$ the color of the right cell of the $$$i$$$-th domino is different from the color of the left cell of the $$$((i \bmod n)+1)$$$-st domino.

Note that you can't rotate the dominoes, so the left cell always remains the left cell, and the right cell always remains the right cell.

Count the number of valid ways to color the yet uncolored cells of dominoes. Two ways are considered different if there is a cell that is colored white in one way and black in the other. In particular, colorings BW WB and WB BW different (and both invalid).

As this number can be very big, output it modulo $$$998\,244\,353$$$.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of dominoes.

The next $$$n$$$ lines describe dominoes. Each line contains two characters which represent the left and the right cell. Character B means that the corresponding cell is black, character W means that the corresponding cell is white, and ? means that the cell is yet to be colored.

## Output Format
Print a single integer — the answer to the problem.

## Examples
```input
1
?W
```
```output
1
```
-----
```input
2
??
W?
```
```output
2
```
-----
```input
4
BB
??
W?
??
```
```output
10
```

## Note
In the first test case, there is only one domino, and we need the color of its right cell to be different from the color of its left cell. There is only one way to achieve this.

In the second test case, there are only $$$2$$$ such colorings:

BB WW and WB WB.

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
On an endless checkered sheet of paper, $$$n$$$ cells are chosen and colored in three colors, where $$$n$$$ is divisible by $$$3$$$. It turns out that there are exactly $$$\frac{n}{3}$$$ marked cells of each of three colors!

Find the largest such $$$k$$$ that it's possible to choose $$$\frac{k}{3}$$$ cells of each color, remove all other marked cells, and then select three rectangles with sides parallel to the grid lines so that the following conditions hold:

- No two rectangles can intersect (but they can share a part of the boundary). In other words, the area of intersection of any two of these rectangles must be $$$0$$$.
- The $$$i$$$-th rectangle contains all the chosen cells of the $$$i$$$-th color and no chosen cells of other colors, for $$$i = 1, 2, 3$$$.

## Input Format
The first line of the input contains a single integer $$$n$$$ — the number of the marked cells ($$$3 \leq n \le 10^5$$$, $$$n$$$ is divisible by 3).

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, $$$c_i$$$ ($$$|x_i|,|y_i| \leq 10^9$$$; $$$1 \leq c_i \leq 3$$$), where $$$(x_i, y_i)$$$ are the coordinates of the $$$i$$$-th marked cell and $$$c_i$$$ is its color.

It's guaranteed that all cells $$$(x_i, y_i)$$$ in the input are distinct, and that there are exactly $$$\frac{n}{3}$$$ cells of each color.

## Output Format
Output a single integer $$$k$$$ — the largest number of cells you can leave.

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

## Note
In the first sample, it's possible to leave $$$6$$$ cells with indexes $$$1, 5, 6, 7, 8, 9$$$.

In the second sample, it's possible to leave $$$3$$$ cells with indexes $$$1, 2, 3$$$.

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
For an array $$$c$$$ of nonnegative integers, $$$MEX(c)$$$ denotes the smallest nonnegative integer that doesn't appear in it. For example, $$$MEX([0, 1, 3]) = 2$$$, $$$MEX([42]) = 0$$$.

You are given integers $$$n, k$$$, and an array $$$[b_1, b_2, \ldots, b_n]$$$.

Find the number of arrays $$$[a_1, a_2, \ldots, a_n]$$$, for which the following conditions hold:

- $$$0 \le a_i \le n$$$ for each $$$i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.
- $$$|MEX([a_1, a_2, \ldots, a_i]) - b_i| \le k$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.

As this number can be very big, output it modulo $$$998\,244\,353$$$.

## Input Format
The first line of the input contains two integers $$$n, k$$$ ($$$1 \le n \le 2000$$$, $$$0 \le k \le 50$$$).

The second line of the input contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$-k \le b_i \le n+k$$$) — elements of the array $$$b$$$.

## Output Format
Output a single integer — the number of arrays which satisfy the conditions from the statement, modulo $$$998\,244\,353$$$.

## Examples
```input
4 0
0 0 0 0
```
```output
256
```
-----
```input
4 1
0 0 0 0
```
```output
431
```
-----
```input
4 1
0 0 1 1
```
```output
509
```
-----
```input
5 2
0 0 2 2 0
```
```output
6546
```
-----
```input
3 2
-2 0 4
```
```output
11
```

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 $$$m$$$ strings and a tree on $$$n$$$ nodes. Each edge has some letter written on it.

You have to answer $$$q$$$ queries. Each query is described by $$$4$$$ integers $$$u$$$, $$$v$$$, $$$l$$$ and $$$r$$$. The answer to the query is the total number of occurrences of $$$str(u,v)$$$ in strings with indices from $$$l$$$ to $$$r$$$. $$$str(u,v)$$$ is defined as the string that is made by concatenating letters written on the edges on the shortest path from $$$u$$$ to $$$v$$$ (in order that they are traversed).

## Input Format
The first line of the input contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m,q \le 10^5$$$).

The $$$i$$$-th of the following $$$n-1$$$ lines contains two integers $$$u_i, v_i$$$ and a lowercase Latin letter $$$c_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), denoting the edge between nodes $$$u_i, v_i$$$ with a character $$$c_i$$$ on it.

It's guaranteed that these edges form a tree.

The following $$$m$$$ lines contain the strings consisting of lowercase Latin letters. The total length of those strings does not exceed $$$10^5$$$.

Then $$$q$$$ lines follow, each containing four integers $$$u$$$, $$$v$$$, $$$l$$$ and $$$r$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$, $$$1 \le l \le r \le m$$$), denoting the queries.

## Output Format
For each query print a single integer — the answer to the query.

## Examples
```input
2 5 3
1 2 a
aab
abab
aaa
b
a
2 1 1 5
1 2 1 3
2 1 3 5
```
```output
8
7
4
```
-----
```input
9 5 6
1 2 a
2 7 c
1 3 b
3 4 b
4 6 b
3 5 a
5 8 b
5 9 c
ababa
cabbb
bac
bbbac
abacaba
2 7 1 4
2 5 1 5
6 3 4 4
6 9 4 5
5 7 3 5
5 3 1 5
```
```output
3
4
2
1
1
10
```

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
You are given an integer $$$n$$$. You have to change the minimum number of digits in it in such a way that the resulting number does not have any leading zeroes and is divisible by $$$7$$$.

If there are multiple ways to do it, print any of them. If the given number is already divisible by $$$7$$$, leave it unchanged.

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

Then the test cases follow, each test case consists of one line containing one integer $$$n$$$ ($$$10 \le n \le 999$$$).

## Output Format
For each test case, print one integer without any leading zeroes — the result of your changes (i. e. the integer that is divisible by $$$7$$$ and can be obtained by changing the minimum possible number of digits in $$$n$$$).

If there are multiple ways to apply changes, print any resulting number. If the given number is already divisible by $$$7$$$, just print it.

## Examples
```input
3
42
23
377
```
```output
42
28
777
```

## Note
In the first test case of the example, $$$42$$$ is already divisible by $$$7$$$, so there's no need to change it.

In the second test case of the example, there are multiple answers — $$$28$$$, $$$21$$$ or $$$63$$$.

In the third test case of the example, other possible answers are $$$357$$$, $$$371$$$ and $$$378$$$. Note that you cannot print $$$077$$$ or $$$77$$$.

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 of integers $$$a$$$ of size $$$n$$$. Initially, all elements of the array are equal to $$$1$$$. You can perform the following operation: choose two integers $$$i$$$ ($$$1 \le i \le n$$$) and $$$x$$$ ($$$x > 0$$$), and then increase the value of $$$a_i$$$ by $$$\left\lfloor\frac{a_i}{x}\right\rfloor$$$ (i.e. make $$$a_i = a_i + \left\lfloor\frac{a_i}{x}\right\rfloor$$$).

After performing all operations, you will receive $$$c_i$$$ coins for all such $$$i$$$ that $$$a_i = b_i$$$.

Your task is to determine the maximum number of coins that you can receive by performing no more than $$$k$$$ operations.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^3; 0 \le k \le 10^6$$$) — the size of the array and the maximum number of operations, respectively.

The second line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^3$$$).

The third line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^6$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

## Output Format
For each test case, print one integer — the maximum number of coins that you can get by performing no more than $$$k$$$ operations.

## Examples
```input
4
4 4
1 7 5 2
2 6 5 2
3 0
3 5 2
5 4 7
5 9
5 2 5 6 3
5 9 1 9 7
6 14
11 4 6 2 8 16
43 45 9 41 15 38
```
```output
9
0
30
167
```

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
You are given a connected weighted undirected graph, consisting of $$$n$$$ vertices and $$$m$$$ edges.

You are asked $$$k$$$ queries about it. Each query consists of a single integer $$$x$$$. For each query, you select a spanning tree in the graph. Let the weights of its edges be $$$w_1, w_2, \dots, w_{n-1}$$$. The cost of a spanning tree is $$$\sum \limits_{i=1}^{n-1} |w_i - x|$$$ (the sum of absolute differences between the weights and $$$x$$$). The answer to a query is the lowest cost of a spanning tree.

The queries are given in a compressed format. The first $$$p$$$ $$$(1 \le p \le k)$$$ queries $$$q_1, q_2, \dots, q_p$$$ are provided explicitly. For queries from $$$p+1$$$ to $$$k$$$, $$$q_j = (q_{j-1} \cdot a + b) \mod c$$$.

Print the xor of answers to all queries.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 50$$$; $$$n - 1 \le m \le 300$$$) — the number of vertices and the number of edges in the graph.

Each of the next $$$m$$$ lines contains a description of an undirected edge: three integers $$$v$$$, $$$u$$$ and $$$w$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$; $$$0 \le w \le 10^8$$$) — the vertices the edge connects and its weight. Note that there might be multiple edges between a pair of vertices. The edges form a connected graph.

The next line contains five integers $$$p, k, a, b$$$ and $$$c$$$ ($$$1 \le p \le 10^5$$$; $$$p \le k \le 10^7$$$; $$$0 \le a, b \le 10^8$$$; $$$1 \le c \le 10^8$$$) — the number of queries provided explicitly, the total number of queries and parameters to generate the queries.

The next line contains $$$p$$$ integers $$$q_1, q_2, \dots, q_p$$$ ($$$0 \le q_j < c$$$) — the first $$$p$$$ queries.

## Output Format
Print a single integer — the xor of answers to all queries.

## Examples
```input
5 8
4 1 4
3 1 0
3 5 3
2 5 4
3 4 8
4 3 4
4 2 8
5 3 9
3 11 1 1 10
0 1 2
```
```output
4
```
-----
```input
6 7
2 4 0
5 4 7
2 4 0
2 1 7
2 6 1
3 4 4
1 4 8
4 10 3 3 7
3 0 2 1
```
```output
5
```
-----
```input
3 3
1 2 50
2 3 100
1 3 150
1 10000000 0 0 100000000
75
```
```output
164
```

## Note
The queries in the first example are $$$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0$$$. The answers are $$$11, 9, 7, 3, 1, 5, 8, 7, 5, 7, 11$$$.

The queries in the second example are $$$3, 0, 2, 1, 6, 0, 3, 5, 4, 1$$$. The answers are $$$14, 19, 15, 16, 11, 19, 14, 12, 13, 16$$$.

The queries in the third example are $$$75, 0, 0, \dots$$$. The answers are $$$50, 150, 150, \dots$$$.

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 have an array $$$a$$$ of length $$$n$$$. You can exactly once select an integer $$$len$$$ between $$$1$$$ and $$$n - 1$$$ inclusively, and then sort in non-decreasing order the prefix of the array of length $$$len$$$ and the suffix of the array of length $$$n - len$$$ independently.

For example, if the array is $$$a = [3, 1, 4, 5, 2]$$$, and you choose $$$len = 2$$$, then after that the array will be equal to $$$[1, 3, 2, 4, 5]$$$.

Could it be that after performing this operation, the array will not be sorted in non-decreasing order?

## Input Format
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^4$$$) — the length of the array.

The second line of the test case contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the array elements.

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

## Output Format
For each test case of input data, output "YES" (without quotes), if the array may be not sorted in non-decreasing order, output "NO" (without quotes) otherwise. You can output each letter in any case (uppercase or lowercase).

## Examples
```input
3
3
2 2 1
4
3 1 2 1
5
1 2 2 4 4
```
```output
YES
YES
NO
```

## Note
In the first test case, it's possible to select $$$len = 1$$$, then after operation, the array will not be sorted in non-decreasing order and will be equal to $$$[2, 1, 2]$$$.

In the second test case, it's possible to select $$$len = 3$$$, then after operation, the array will not be sorted in non-decreasing order and will be equal to $$$[1, 2, 3, 1]$$$.

In the third test case, the array will be sorted in non-decreasing order for every possible $$$len$$$.

Now solve the problem and return the code.