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 a chessboard of size $$$n$$$ by $$$n$$$. The square in the $$$i$$$-th row from top and $$$j$$$-th column from the left is labelled $$$(i,j)$$$.

Currently, Gregor has some pawns in the $$$n$$$-th row. There are also enemy pawns in the $$$1$$$-st row. On one turn, Gregor moves one of his pawns. A pawn can move one square up (from $$$(i,j)$$$ to $$$(i-1,j)$$$) if there is no pawn in the destination square. Additionally, a pawn can move one square diagonally up (from $$$(i,j)$$$ to either $$$(i-1,j-1)$$$ or $$$(i-1,j+1)$$$) if and only if there is an enemy pawn in that square. The enemy pawn is also removed.

Gregor wants to know what is the maximum number of his pawns that can reach row $$$1$$$?

Note that only Gregor takes turns in this game, and the enemy pawns never move. Also, when Gregor's pawn reaches row $$$1$$$, it is stuck and cannot make any further moves.

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

Each test case consists of three lines. The first line contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot{10}^{5}$$$) — the size of the chessboard.

The second line consists of a string of binary digits of length $$$n$$$, where a $$$1$$$ in the $$$i$$$-th position corresponds to an enemy pawn in the $$$i$$$-th cell from the left, and $$$0$$$ corresponds to an empty cell.

The third line consists of a string of binary digits of length $$$n$$$, where a $$$1$$$ in the $$$i$$$-th position corresponds to a Gregor's pawn in the $$$i$$$-th cell from the left, and $$$0$$$ corresponds to an empty cell.

It is guaranteed that the sum of $$$n$$$ across all test cases is less than $$$2\cdot{10}^{5}$$$.

## Output Format
For each test case, print one integer: the maximum number of Gregor's pawns which can reach the $$$1$$$-st row.

## Examples
```input
4
3
000
111
4
1111
1111
3
010
010
5
11001
00000
```
```output
3
4
0
0
```

## Note
In the first example, Gregor can simply advance all $$$3$$$ of his pawns forward. Thus, the answer is $$$3$$$.

In the second example, Gregor can guarantee that all $$$4$$$ of his pawns reach the enemy row, by following the colored paths as demonstrated in the diagram below. Remember, only Gregor takes turns in this "game"!

In the third example, Gregor's only pawn is stuck behind the enemy pawn, and cannot reach the end.

In the fourth example, Gregor has no pawns, so the answer is clearly $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp must pay exactly $$$n$$$ burles at the checkout. He has coins of two nominal values: $$$1$$$ burle and $$$2$$$ burles. Polycarp likes both kinds of coins equally. So he doesn't want to pay with more coins of one type than with the other.

Thus, Polycarp wants to minimize the difference between the count of coins of $$$1$$$ burle and $$$2$$$ burles being used. Help him by determining two non-negative integer values $$$c_1$$$ and $$$c_2$$$ which are the number of coins of $$$1$$$ burle and $$$2$$$ burles, respectively, so that the total value of that number of coins is exactly $$$n$$$ (i. e. $$$c_1 + 2 \cdot c_2 = n$$$), and the absolute value of the difference between $$$c_1$$$ and $$$c_2$$$ is as little as possible (i. e. you must minimize $$$|c_1-c_2|$$$).

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

Each test case consists of one line. This line contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the number of burles to be paid by Polycarp.

## Output Format
For each test case, output a separate line containing two integers $$$c_1$$$ and $$$c_2$$$ ($$$c_1, c_2 \ge 0$$$) separated by a space where $$$c_1$$$ is the number of coins of $$$1$$$ burle and $$$c_2$$$ is the number of coins of $$$2$$$ burles. If there are multiple optimal solutions, print any one.

## Examples
```input
6
1000
30
1
32
1000000000
5
```
```output
334 333
10 10
1 0
10 11
333333334 333333333
1 2
```

## Note
The answer for the first test case is "334 333". The sum of the nominal values of all coins is $$$334 \cdot 1 + 333 \cdot 2 = 1000$$$, whereas $$$|334 - 333| = 1$$$. One can't get the better value because if $$$|c_1 - c_2| = 0$$$, then $$$c_1 = c_2$$$ and $$$c_1 \cdot 1 + c_1 \cdot 2 = 1000$$$, but then the value of $$$c_1$$$ isn't an integer.

The answer for the second test case is "10 10". The sum of the nominal values is $$$10 \cdot 1 + 10 \cdot 2 = 30$$$ and $$$|10 - 10| = 0$$$, whereas there's no number having an absolute value less than $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between this problem and D2 is that you don't have to provide the way to construct the answer in this problem, but you have to do it in D2.

There's a table of $$$n \times m$$$ cells ($$$n$$$ rows and $$$m$$$ columns). The value of $$$n \cdot m$$$ is even.

A domino is a figure that consists of two cells having a common side. It may be horizontal (one of the cells is to the right of the other) or vertical (one of the cells is above the other).

You need to find out whether it is possible to place $$$\frac{nm}{2}$$$ dominoes on the table so that exactly $$$k$$$ of them are horizontal and all the other dominoes are vertical. The dominoes cannot overlap and must fill the whole table.

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

Each test case consists of a single line. The line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n,m \le 100$$$, $$$0 \le k \le \frac{nm}{2}$$$, $$$n \cdot m$$$ is even) — the number of rows, columns and horizontal dominoes, respectively.

## Output Format
For each test case output "YES", if it is possible to place dominoes in the desired way, or "NO" otherwise.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

## Examples
```input
8
4 4 2
2 3 0
3 2 3
1 2 0
2 4 2
5 2 2
2 17 16
2 1 1
```
```output
YES
YES
YES
NO
YES
NO
YES
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between this problem and D1 is that you don't have to provide the way to construct the answer in D1, but you have to do it in this problem.

There's a table of $$$n \times m$$$ cells ($$$n$$$ rows and $$$m$$$ columns). The value of $$$n \cdot m$$$ is even.

A domino is a figure that consists of two cells having a common side. It may be horizontal (one of the cells is to the right of the other) or vertical (one of the cells is above the other).

You need to place $$$\frac{nm}{2}$$$ dominoes on the table so that exactly $$$k$$$ of them are horizontal and all the other dominoes are vertical. The dominoes cannot overlap and must fill the whole table.

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

Each test case consists of a single line. The line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n,m \le 100$$$, $$$0 \le k \le \frac{nm}{2}$$$, $$$n \cdot m$$$ is even) — the count of rows, columns and horizontal dominoes, respectively.

## Output Format
For each test case:

- print "NO" if it's not possible to place the dominoes on the table in the described way;
- otherwise, print "YES" on a separate line, then print $$$n$$$ lines so that each of them contains $$$m$$$ lowercase letters of the Latin alphabet — the layout of the dominoes on the table. Each cell of the table must be marked by the letter so that for every two cells having a common side, they are marked by the same letters if and only if they are occupied by the same domino. I.e. both cells of the same domino must be marked with the same letter, but two dominoes that share a side must be marked with different letters. If there are multiple solutions, print any of them.

## Examples
```input
8
4 4 2
2 3 0
3 2 3
1 2 0
2 4 2
5 2 2
2 17 16
2 1 1
```
```output
YES
accx
aegx
bega
bdda
YES
aha
aha
YES
zz
aa
zz
NO
YES
aaza
bbza
NO
YES
bbaabbaabbaabbaay
ddccddccddccddccy
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A tree is an undirected connected graph without cycles.

You are given a tree of $$$n$$$ vertices. Find the number of ways to choose exactly $$$k$$$ vertices in this tree (i. e. a $$$k$$$-element subset of vertices) so that all pairwise distances between the selected vertices are equal (in other words, there exists an integer $$$c$$$ such that for all $$$u, v$$$ ($$$u \ne v$$$, $$$u, v$$$ are in selected vertices) $$$d_{u,v}=c$$$, where $$$d_{u,v}$$$ is the distance from $$$u$$$ to $$$v$$$).

Since the answer may be very large, you need to output it modulo $$$10^9 + 7$$$.

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

Each test case is preceded by an empty line.

Each test case consists of several lines. The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 100$$$) — the number of vertices in the tree and the number of vertices to be selected, respectively. Then $$$n - 1$$$ lines follow, each of them contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.

## Output Format
For each test case output in a separate line a single integer — the number of ways to select exactly $$$k$$$ vertices so that for all pairs of selected vertices the distances between the vertices in the pairs are equal, modulo $$$10^9 + 7$$$ (in other words, print the remainder when divided by $$$1000000007$$$).

## Examples
```input
3

4 2
1 2
2 3
2 4

3 3
1 2
2 3

5 3
1 2
2 3
2 4
4 5
```
```output
6
0
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
PizzaForces is Petya's favorite pizzeria. PizzaForces makes and sells pizzas of three sizes: small pizzas consist of $$$6$$$ slices, medium ones consist of $$$8$$$ slices, and large pizzas consist of $$$10$$$ slices each. Baking them takes $$$15$$$, $$$20$$$ and $$$25$$$ minutes, respectively.

Petya's birthday is today, and $$$n$$$ of his friends will come, so he decided to make an order from his favorite pizzeria. Petya wants to order so much pizza that each of his friends gets at least one slice of pizza. The cooking time of the order is the total baking time of all the pizzas in the order.

Your task is to determine the minimum number of minutes that is needed to make pizzas containing at least $$$n$$$ slices in total. For example:

- if $$$12$$$ friends come to Petya's birthday, he has to order pizzas containing at least $$$12$$$ slices in total. He can order two small pizzas, containing exactly $$$12$$$ slices, and the time to bake them is $$$30$$$ minutes;
- if $$$15$$$ friends come to Petya's birthday, he has to order pizzas containing at least $$$15$$$ slices in total. He can order a small pizza and a large pizza, containing $$$16$$$ slices, and the time to bake them is $$$40$$$ minutes;
- if $$$300$$$ friends come to Petya's birthday, he has to order pizzas containing at least $$$300$$$ slices in total. He can order $$$15$$$ small pizzas, $$$10$$$ medium pizzas and $$$13$$$ large pizzas, in total they contain $$$15 \cdot 6 + 10 \cdot 8 + 13 \cdot 10 = 300$$$ slices, and the total time to bake them is $$$15 \cdot 15 + 10 \cdot 20 + 13 \cdot 25 = 750$$$ minutes;
- if only one friend comes to Petya's birthday, he can order a small pizza, and the time to bake it is $$$15$$$ minutes.

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

Each testcase consists of a single line that contains a single integer $$$n$$$ ($$$1 \le n \le 10^{16}$$$) — the number of Petya's friends.

## Output Format
For each testcase, print one integer — the minimum number of minutes that is needed to bake pizzas containing at least $$$n$$$ slices in total.

## Examples
```input
6
12
15
300
1
9999999999999999
3
```
```output
30
40
750
15
25000000000000000
15
```

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
Let's call the string beautiful if it does not contain a substring of length at least $$$2$$$, which is a palindrome. Recall that a palindrome is a string that reads the same way from the first character to the last and from the last character to the first. For example, the strings a, bab, acca, bcabcbacb are palindromes, but the strings ab, abbbaa, cccb are not.

Let's define cost of a string as the minimum number of operations so that the string becomes beautiful, if in one operation it is allowed to change any character of the string to one of the first $$$3$$$ letters of the Latin alphabet (in lowercase).

You are given a string $$$s$$$ of length $$$n$$$, each character of the string is one of the first $$$3$$$ letters of the Latin alphabet (in lowercase).

You have to answer $$$m$$$ queries — calculate the cost of the substring of the string $$$s$$$ from $$$l_i$$$-th to $$$r_i$$$-th position, inclusive.

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

The second line contains the string $$$s$$$, it consists of $$$n$$$ characters, each character one of the first $$$3$$$ Latin letters.

The following $$$m$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — parameters of the $$$i$$$-th query.

## Output Format
For each query, print a single integer — the cost of the substring of the string $$$s$$$ from $$$l_i$$$-th to $$$r_i$$$-th position, inclusive.

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

## Note
Consider the queries of the example test.

- in the first query, the substring is baa, which can be changed to bac in one operation;
- in the second query, the substring is baacb, which can be changed to cbacb in two operations;
- in the third query, the substring is cb, which can be left unchanged;
- in the fourth query, the substring is aa, which can be changed to ba in one operation.

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 undirected graph consisting of $$$n$$$ vertices with weighted edges.

A simple cycle is a cycle of the graph without repeated vertices. Let the weight of the cycle be the XOR of weights of edges it consists of.

Let's say the graph is good if all its simple cycles have weight $$$1$$$. A graph is bad if it's not good.

Initially, the graph is empty. Then $$$q$$$ queries follow. Each query has the next type:

- $$$u$$$ $$$v$$$ $$$x$$$ — add edge between vertices $$$u$$$ and $$$v$$$ of weight $$$x$$$ if it doesn't make the graph bad.

For each query print, was the edge added or not.

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

Next $$$q$$$ lines contain queries — one per line. Each query contains three integers $$$u$$$, $$$v$$$ and $$$x$$$ ($$$1 \le u, v \le n$$$; $$$u \neq v$$$; $$$0 \le x \le 1$$$) — the vertices of the edge and its weight.

It's guaranteed that there are no multiple edges in the input.

## Output Format
For each query, print YES if the edge was added to the graph, or NO otherwise (both case-insensitive).

## Examples
```input
9 12
6 1 0
1 3 1
3 6 0
6 2 0
6 4 1
3 4 1
2 4 0
2 5 0
4 5 0
7 8 1
8 9 1
9 7 0
```
```output
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp doesn't like integers that are divisible by $$$3$$$ or end with the digit $$$3$$$ in their decimal representation. Integers that meet both conditions are disliked by Polycarp, too.

Polycarp starts to write out the positive (greater than $$$0$$$) integers which he likes: $$$1, 2, 4, 5, 7, 8, 10, 11, 14, 16, \dots$$$. Output the $$$k$$$-th element of this sequence (the elements are numbered from $$$1$$$).

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

Each test case consists of one line containing one integer $$$k$$$ ($$$1 \le k \le 1000$$$).

## Output Format
For each test case, output in a separate line one integer $$$x$$$ — the $$$k$$$-th element of the sequence that was written out by Polycarp.

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

Now solve the problem and return the code.