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

# Problem
Being Santa Claus is very difficult. Sometimes you have to deal with difficult situations.

Today Santa Claus came to the holiday and there were $$$m$$$ children lined up in front of him. Let's number them from $$$1$$$ to $$$m$$$. Grandfather Frost knows $$$n$$$ spells. The $$$i$$$-th spell gives a candy to every child whose place is in the $$$[L_i, R_i]$$$ range. Each spell can be used at most once. It is also known that if all spells are used, each child will receive at most $$$k$$$ candies.

It is not good for children to eat a lot of sweets, so each child can eat no more than one candy, while the remaining candies will be equally divided between his (or her) Mom and Dad. So it turns out that if a child would be given an even amount of candies (possibly zero), then he (or she) will be unable to eat any candies and will go sad. However, the rest of the children (who received an odd number of candies) will be happy.

Help Santa Claus to know the maximum number of children he can make happy by casting some of his spells.

## Input Format
The first line contains three integers of $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \leq 100\,000, 1 \leq m \leq 10^9, 1 \leq k \leq 8$$$) — the number of spells, the number of children and the upper limit on the number of candy a child can get if all spells are used, respectively.

This is followed by $$$n$$$ lines, each containing integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq m$$$) — the parameters of the $$$i$$$ spell.

## Output Format
Print a single integer — the maximum number of children that Santa can make happy.

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

## Note
In the first example, Santa should apply the first and third spell. In this case all children will be happy except the third.

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
Vasya had three strings $$$a$$$, $$$b$$$ and $$$s$$$, which consist of lowercase English letters. The lengths of strings $$$a$$$ and $$$b$$$ are equal to $$$n$$$, the length of the string $$$s$$$ is equal to $$$m$$$.

Vasya decided to choose a substring of the string $$$a$$$, then choose a substring of the string $$$b$$$ and concatenate them. Formally, he chooses a segment $$$[l_1, r_1]$$$ ($$$1 \leq l_1 \leq r_1 \leq n$$$) and a segment $$$[l_2, r_2]$$$ ($$$1 \leq l_2 \leq r_2 \leq n$$$), and after concatenation he obtains a string $$$a[l_1, r_1] + b[l_2, r_2] = a_{l_1} a_{l_1 + 1} \ldots a_{r_1} b_{l_2} b_{l_2 + 1} \ldots b_{r_2}$$$.

Now, Vasya is interested in counting number of ways to choose those segments adhering to the following conditions:

- segments $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ have non-empty intersection, i.e. there exists at least one integer $$$x$$$, such that $$$l_1 \leq x \leq r_1$$$ and $$$l_2 \leq x \leq r_2$$$;
- the string $$$a[l_1, r_1] + b[l_2, r_2]$$$ is equal to the string $$$s$$$.

## Input Format
The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 500\,000, 2 \leq m \leq 2 \cdot n$$$) — the length of strings $$$a$$$ and $$$b$$$ and the length of the string $$$s$$$.

The next three lines contain strings $$$a$$$, $$$b$$$ and $$$s$$$, respectively. The length of the strings $$$a$$$ and $$$b$$$ is $$$n$$$, while the length of the string $$$s$$$ is $$$m$$$.

All strings consist of lowercase English letters.

## Output Format
Print one integer — the number of ways to choose a pair of segments, which satisfy Vasya's conditions.

## Examples
```input
6 5
aabbaa
baaaab
aaaaa
```
```output
4
```
-----
```input
5 4
azaza
zazaz
azaz
```
```output
11
```
-----
```input
9 12
abcabcabc
xyzxyzxyz
abcabcayzxyz
```
```output
2
```

## Note
Let's list all the pairs of segments that Vasya could choose in the first example:

1. $$$[2, 2]$$$ and $$$[2, 5]$$$;
2. $$$[1, 2]$$$ and $$$[2, 4]$$$;
3. $$$[5, 5]$$$ and $$$[2, 5]$$$;
4. $$$[5, 6]$$$ and $$$[3, 5]$$$;

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
$$$n$$$ students are taking an exam. The highest possible score at this exam is $$$m$$$. Let $$$a_{i}$$$ be the score of the $$$i$$$-th student. You have access to the school database which stores the results of all students.

You can change each student's score as long as the following conditions are satisfied:

- All scores are integers
- $$$0 \leq a_{i} \leq m$$$
- The average score of the class doesn't change.

You are student $$$1$$$ and you would like to maximize your own score.

Find the highest possible score you can assign to yourself such that all conditions are satisfied.

## Input Format
Each test contains multiple test cases.

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^{3}$$$, $$$1 \leq m \leq 10^{5}$$$)  — the number of students and the highest possible score respectively.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$ 0 \leq a_{i} \leq m$$$)  — scores of the students.

## Output Format
For each testcase, output one integer  — the highest possible score you can assign to yourself such that both conditions are satisfied._

## Examples
```input
2
4 10
1 2 3 4
4 5
1 2 3 4
```
```output
10
5
```

## Note
In the first case, $$$a = [1,2,3,4] $$$, with average of $$$2.5$$$. You can change array $$$a$$$ to $$$[10,0,0,0]$$$. Average remains $$$2.5$$$, and all conditions are satisfied.

In the second case, $$$0 \leq a_{i} \leq 5$$$. You can change $$$a$$$ to $$$[5,1,1,3]$$$. You cannot increase $$$a_{1}$$$ further as it will violate condition $$$0\le a_i\le m$$$.

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 two integers $$$n$$$ and $$$k$$$. Your task is to find if $$$n$$$ can be represented as a sum of $$$k$$$ distinct positive odd (not divisible by $$$2$$$) integers or not.

You have to answer $$$t$$$ independent test cases.

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

The next $$$t$$$ lines describe test cases. The only line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^7$$$).

## Output Format
For each test case, print the answer — "YES" (without quotes) if $$$n$$$ can be represented as a sum of $$$k$$$ distinct positive odd (not divisible by $$$2$$$) integers and "NO" otherwise.

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

## Note
In the first test case, you can represent $$$3$$$ as $$$3$$$.

In the second test case, the only way to represent $$$4$$$ is $$$1+3$$$.

In the third test case, you cannot represent $$$10$$$ as the sum of three distinct positive odd integers.

In the fourth test case, you can represent $$$10$$$ as $$$3+7$$$, for example.

In the fifth test case, you can represent $$$16$$$ as $$$1+3+5+7$$$.

In the sixth test case, you cannot represent $$$16$$$ as the sum of five distinct positive odd integers.

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
Petya has a rectangular Board of size $$$n \times m$$$. Initially, $$$k$$$ chips are placed on the board, $$$i$$$-th chip is located in the cell at the intersection of $$$sx_i$$$-th row and $$$sy_i$$$-th column.

In one action, Petya can move all the chips to the left, right, down or up by $$$1$$$ cell.

If the chip was in the $$$(x, y)$$$ cell, then after the operation:

- left, its coordinates will be $$$(x, y - 1)$$$;
- right, its coordinates will be $$$(x, y + 1)$$$;
- down, its coordinates will be $$$(x + 1, y)$$$;
- up, its coordinates will be $$$(x - 1, y)$$$.

If the chip is located by the wall of the board, and the action chosen by Petya moves it towards the wall, then the chip remains in its current position.

Note that several chips can be located in the same cell.

For each chip, Petya chose the position which it should visit. Note that it's not necessary for a chip to end up in this position.

Since Petya does not have a lot of free time, he is ready to do no more than $$$2nm$$$ actions.

You have to find out what actions Petya should do so that each chip visits the position that Petya selected for it at least once. Or determine that it is not possible to do this in $$$2nm$$$ actions.

## Input Format
The first line contains three integers $$$n, m, k$$$ ($$$1 \le n, m, k \le 200$$$) — the number of rows and columns of the board and the number of chips, respectively.

The next $$$k$$$ lines contains two integers each $$$sx_i, sy_i$$$ ($$$ 1 \le sx_i \le n, 1 \le sy_i \le m$$$) — the starting position of the $$$i$$$-th chip.

The next $$$k$$$ lines contains two integers each $$$fx_i, fy_i$$$ ($$$ 1 \le fx_i \le n, 1 \le fy_i \le m$$$) — the position that the $$$i$$$-chip should visit at least once.

## Output Format
In the first line print the number of operations so that each chip visits the position that Petya selected for it at least once.

In the second line output the sequence of operations. To indicate operations left, right, down, and up, use the characters $$$L, R, D, U$$$ respectively.

If the required sequence does not exist, print -1 in the single line.

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

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 a colored permutation $$$p_1, p_2, \dots, p_n$$$. The $$$i$$$-th element of the permutation has color $$$c_i$$$.

Let's define an infinite path as infinite sequence $$$i, p[i], p[p[i]], p[p[p[i]]] \dots$$$ where all elements have same color ($$$c[i] = c[p[i]] = c[p[p[i]]] = \dots$$$).

We can also define a multiplication of permutations $$$a$$$ and $$$b$$$ as permutation $$$c = a \times b$$$ where $$$c[i] = b[a[i]]$$$. Moreover, we can define a power $$$k$$$ of permutation $$$p$$$ as $$$p^k=\underbrace{p \times p \times \dots \times p}_{k \text{ times}}$$$.

Find the minimum $$$k > 0$$$ such that $$$p^k$$$ has at least one infinite path (i.e. there is a position $$$i$$$ in $$$p^k$$$ such that the sequence starting from $$$i$$$ is an infinite path).

It can be proved that the answer always exists.

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

Next $$$3T$$$ lines contain test cases — one per three lines. The first line contains single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the permutation.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i \neq p_j$$$ for $$$i \neq j$$$) — the permutation $$$p$$$.

The third line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — the colors of elements of the permutation.

It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
Print $$$T$$$ integers — one per test case. For each test case print minimum $$$k > 0$$$ such that $$$p^k$$$ has at least one infinite path.

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

## Note
In the first test case, $$$p^1 = p = [1, 3, 4, 2]$$$ and the sequence starting from $$$1$$$: $$$1, p[1] = 1, \dots$$$ is an infinite path.

In the second test case, $$$p^5 = [1, 2, 3, 4, 5]$$$ and it obviously contains several infinite paths.

In the third test case, $$$p^2 = [3, 6, 1, 8, 7, 2, 5, 4]$$$ and the sequence starting from $$$4$$$: $$$4, p^2[4]=8, p^2[8]=4, \dots$$$ is an infinite path since $$$c_4 = c_8 = 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
You wrote down all integers from $$$0$$$ to $$$10^n - 1$$$, padding them with leading zeroes so their lengths are exactly $$$n$$$. For example, if $$$n = 3$$$ then you wrote out 000, 001, ..., 998, 999.

A block in an integer $$$x$$$ is a consecutive segment of equal digits that cannot be extended to the left or to the right.

For example, in the integer $$$00027734000$$$ there are three blocks of length $$$1$$$, one block of length $$$2$$$ and two blocks of length $$$3$$$.

For all integers $$$i$$$ from $$$1$$$ to $$$n$$$ count the number of blocks of length $$$i$$$ among the written down integers.

Since these integers may be too large, print them modulo $$$998244353$$$.

## Input Format
The only line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

## Output Format
In the only line print $$$n$$$ integers. The $$$i$$$-th integer is equal to the number of blocks of length $$$i$$$.

Since these integers may be too large, print them modulo $$$998244353$$$.

## Examples
```input
1
```
```output
10
```
-----
```input
2
```
```output
180 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given three integers $$$n$$$, $$$k$$$, $$$m$$$ and $$$m$$$ conditions $$$(l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m)$$$.

Calculate the number of distinct arrays $$$a$$$, consisting of $$$n$$$ integers such that:

- $$$0 \le a_i < 2^k$$$ for each $$$1 \le i \le n$$$;
- bitwise AND of numbers $$$a[l_i] \& a[l_i + 1] \& \dots \& a[r_i] = x_i$$$ for each $$$1 \le i \le m$$$.

Two arrays $$$a$$$ and $$$b$$$ are considered different if there exists such a position $$$i$$$ that $$$a_i \neq b_i$$$.

The number can be pretty large so print it modulo $$$998244353$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 5 \cdot 10^5$$$, $$$1 \le k \le 30$$$, $$$0 \le m \le 5 \cdot 10^5$$$) — the length of the array $$$a$$$, the value such that all numbers in $$$a$$$ should be smaller than $$$2^k$$$ and the number of conditions, respectively.

Each of the next $$$m$$$ lines contains the description of a condition $$$l_i$$$, $$$r_i$$$ and $$$x_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$0 \le x_i < 2^k$$$) — the borders of the condition segment and the required bitwise AND value on it.

## Output Format
Print a single integer — the number of distinct arrays $$$a$$$ that satisfy all the above conditions modulo $$$998244353$$$.

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

## Note
You can recall what is a bitwise AND operation here.

In the first example, the answer is the following arrays: $$$[3, 3, 7, 6]$$$, $$$[3, 7, 7, 6]$$$ and $$$[7, 3, 7, 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: 4.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given a string $$$S$$$ and an array of strings $$$[t_1, t_2, \dots, t_k]$$$. Each string $$$t_i$$$ consists of lowercase Latin letters from a to n; $$$S$$$ consists of lowercase Latin letters from a to n and no more than $$$14$$$ question marks.

Each string $$$t_i$$$ has its cost $$$c_i$$$ — an integer number. The value of some string $$$T$$$ is calculated as $$$\sum\limits_{i = 1}^{k} F(T, t_i) \cdot c_i$$$, where $$$F(T, t_i)$$$ is the number of occurences of string $$$t_i$$$ in $$$T$$$ as a substring. For example, $$$F(\text{aaabaaa}, \text{aa}) = 4$$$.

You have to replace all question marks in $$$S$$$ with pairwise distinct lowercase Latin letters from a to n so the value of $$$S$$$ is maximum possible.

## Input Format
The first line contains one integer $$$k$$$ ($$$1 \le k \le 1000$$$) — the number of strings in the array $$$[t_1, t_2, \dots, t_k]$$$.

Then $$$k$$$ lines follow, each containing one string $$$t_i$$$ (consisting of lowercase Latin letters from a to n) and one integer $$$c_i$$$ ($$$1 \le |t_i| \le 1000$$$, $$$-10^6 \le c_i \le 10^6$$$). The sum of lengths of all strings $$$t_i$$$ does not exceed $$$1000$$$.

The last line contains one string $$$S$$$ ($$$1 \le |S| \le 4 \cdot 10^5$$$) consisting of lowercase Latin letters from a to n and question marks. The number of question marks in $$$S$$$ is not greater than $$$14$$$.

## Output Format
Print one integer — the maximum value of $$$S$$$ after replacing all question marks with pairwise distinct lowercase Latin letters from a to n.

## Examples
```input
4
abc -10
a 1
b 1
c 3
?b?
```
```output
5
```
-----
```input
2
a 1
a 1
?
```
```output
2
```
-----
```input
3
a 1
b 3
ab 4
ab
```
```output
8
```
-----
```input
1
a -1
?????????????
```
```output
0
```
-----
```input
1
a -1
??????????????
```
```output
-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
You are given a special jigsaw puzzle consisting of $$$n\cdot m$$$ identical pieces. Every piece has three tabs and one blank, as pictured below.

The jigsaw puzzle is considered solved if the following conditions hold:

1. The pieces are arranged into a grid with $$$n$$$ rows and $$$m$$$ columns.
2. For any two pieces that share an edge in the grid, a tab of one piece fits perfectly into a blank of the other piece.

Through rotation and translation of the pieces, determine if it is possible to solve the jigsaw puzzle.

## Input Format
The test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$) — the number of test cases. Next $$$t$$$ lines contain descriptions of test cases.

Each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$).

## Output Format
For each test case output a single line containing "YES" if it is possible to solve the jigsaw puzzle, or "NO" otherwise. You can print each letter in any case (upper or lower).

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

## Note
For the first test case, this is an example solution:

For the second test case, we can show that no solution exists.

For the third test case, this is an example solution:

Now solve the problem and return the code.