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

# Problem
Kirill has two integer arrays $$$a_1,a_2,\ldots,a_n$$$ and $$$b_1,b_2,\ldots,b_n$$$ of length $$$n$$$. He defines the absolute beauty of the array $$$b$$$ as $$$$$$\sum_{i=1}^{n} |a_i - b_i|.$$$$$$ Here, $$$|x|$$$ denotes the absolute value of $$$x$$$.

Kirill can perform the following operation at most once:

- select two indices $$$i$$$ and $$$j$$$ ($$$1 \leq i < j \leq n$$$) and swap the values of $$$b_i$$$ and $$$b_j$$$.

Help him find the maximum possible absolute beauty of the array $$$b$$$ after performing at most one swap.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10\,000$$$). The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — the length of the arrays $$$a$$$ and $$$b$$$.

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

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1\leq b_i\leq 10^9$$$) — the array $$$b$$$.

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

## Output Format
For each test case, output one integer — the maximum possible absolute beauty of the array $$$b$$$ after no more than one swap.

## Examples
```input
6
3
1 3 5
3 3 3
2
1 2
1 2
2
1 2
2 1
4
1 2 3 4
5 6 7 8
10
1 8 2 5 3 5 3 1 1 3
2 9 2 4 8 2 3 5 3 1
3
47326 6958 358653
3587 35863 59474
```
```output
4
2
2
16
31
419045
```

## Note
In the first test case, each of the possible swaps does not change the array $$$b$$$.

In the second test case, the absolute beauty of the array $$$b$$$ without performing the swap is $$$|1-1| + |2-2| = 0$$$. After swapping the first and the second element in the array $$$b$$$, the absolute beauty becomes $$$|1-2| + |2-1| = 2$$$. These are all the possible outcomes, hence the answer is $$$2$$$.

In the third test case, it is optimal for Kirill to not perform the swap. Similarly to the previous test case, the answer is $$$2$$$.

In the fourth test case, no matter what Kirill does, the absolute beauty of $$$b$$$ remains equal to $$$16$$$.

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
Sofia has a string $$$s$$$ of length $$$n$$$, consisting only of lowercase English letters. She can perform operations of the following types with this string.

1. Select an index $$$1 \le i \le |s|$$$ and remove the character $$$s_i$$$ from the string.
2. Select a pair of indices $$$(l, r)$$$ ($$$1 \le l \le r \le |s|$$$) and sort the substring $$$s_{l} s_{l+1} \ldots s_r$$$ in alphabetical order.

Sofia wants to obtain the string $$$t$$$ of length $$$m$$$ after performing zero or more operations on string $$$s$$$ as described above. Please determine whether it is possible or not.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1\leq m \leq n \leq 2\cdot 10^5$$$) — the lengths of string $$$s$$$ and $$$t$$$, respectively.

The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting only of lowercase English letters.

The third line of each test case contains the string $$$t$$$ of length $$$m$$$, consisting only of lowercase English letters.

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

## Output Format
For each test case, output "YES" if Sofia can obtain the string $$$t$$$ from $$$s$$$ using the operations above. Otherwise, output "NO".

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
5 5
sofia
afios
3 2
cba
bc
5 1
sofia
e
15 7
anavolimilovana
aamanan
26 4
abcdefghijklmnopqrstuvwxyz
nope
26 4
zyxwvutsrqponmlkjihgfedcba
nope
7 3
apricot
cat
3 3
cba
acb
```
```output
YES
YES
NO
YES
NO
YES
NO
YES
```

## Note
In the first test case, Sofia can perform the following operation:

1. operation of the second type with $$$l=1$$$ and $$$r=5$$$: string $$$s$$$ becomes $$$\mathtt{afios}$$$ after it.

In the second test case, Sofia can perform the following operations:

1. operation of the second type with $$$l=1$$$ and $$$r=2$$$: string $$$s$$$ becomes $$$\mathtt{bca}$$$ after it;
2. operation of the first type with $$$i=3$$$: string $$$s$$$ becomes $$$\mathtt{bc}$$$ after it.

In the third test case, it can be shown that it is impossible to obtain $$$t$$$ from $$$s$$$ using the provided operations.

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
Bob came to a cash & carry store, put n items into his trolley, and went to the checkout counter to pay. Each item is described by its price ci and time ti in seconds that a checkout assistant spends on this item. While the checkout assistant is occupied with some item, Bob can steal some other items from his trolley. To steal one item Bob needs exactly 1 second. What is the minimum amount of money that Bob will have to pay to the checkout assistant? Remember, please, that it is Bob, who determines the order of items for the checkout assistant.

## Input Format
The first input line contains number n (1 ≤ n ≤ 2000). In each of the following n lines each item is described by a pair of numbers ti, ci (0 ≤ ti ≤ 2000, 1 ≤ ci ≤ 109). If ti is 0, Bob won't be able to steal anything, while the checkout assistant is occupied with item i.

## Output Format
Output one number — answer to the problem: what is the minimum amount of money that Bob will have to pay.

## Examples
```input
4
2 10
0 20
1 5
1 3
```
```output
8
```
-----
```input
3
0 1
0 10
0 100
```
```output
111
```

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
Once Bob saw a string. It contained so many different letters, that the letters were marked by numbers, but at the same time each letter could be met in the string at most 10 times. Bob didn't like that string, because it contained repeats: a repeat of length x is such a substring of length 2x, that its first half coincides character by character with its second half. Bob started deleting all the repeats from the string. He does it as follows: while it's possible, Bob takes the shortest repeat, if it is not unique, he takes the leftmost one, and deletes its left half and everything that is to the left of this repeat.

You're given the string seen by Bob. Find out, what it will look like after Bob deletes all the repeats in the way described above.

## Input Format
The first input line contains integer n (1 ≤ n ≤ 105) — length of the string. The following line contains n space-separated integer numbers from 0 to 109 inclusive — numbers that stand for the letters of the string. It's guaranteed that each letter can be met in the string at most 10 times.

## Output Format
In the first line output the length of the string's part, left after Bob's deletions. In the second line output all the letters (separated by a space) of the string, left after Bob deleted all the repeats in the described way.

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

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.5 seconds
Memory limit: 256.0 MB

# Problem
Once upon a time there lived a good fairy A. One day a fine young man B came to her and asked to predict his future. The fairy looked into her magic ball and said that soon the fine young man will meet the most beautiful princess ever and will marry her. Then she drew on a sheet of paper n points and joined some of them with segments, each of the segments starts in some point and ends in some other point. Having drawn that picture, she asked the young man to erase one of the segments from the sheet. Then she tries to colour each point red or blue so, that there is no segment having points of the same colour as its ends. If she manages to do so, the prediction will come true. B wants to meet the most beautiful princess, that's why he asks you to help him. Find all the segments that will help him to meet the princess.

## Input Format
The first input line contains two integer numbers: n — amount of the drawn points and m — amount of the drawn segments (1 ≤ n ≤ 104, 0 ≤ m ≤ 104). The following m lines contain the descriptions of the segments. Each description contains two different space-separated integer numbers v, u (1 ≤ v ≤ n, 1 ≤ u ≤ n) — indexes of the points, joined by this segment. No segment is met in the description twice.

## Output Format
In the first line output number k — amount of the segments in the answer. In the second line output k space-separated numbers — indexes of these segments in ascending order. Each index should be output only once. Segments are numbered from 1 in the input order.

## Examples
```input
4 4
1 2
1 3
2 4
3 4
```
```output
4
1 2 3 4
```
-----
```input
4 5
1 2
2 3
3 4
4 1
1 3
```
```output
1
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: 2.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given two strings $$$s$$$, $$$t$$$ of length $$$n$$$, $$$m$$$, respectively. Both strings consist of lowercase letters of the English alphabet.

Count the triples $$$(x, y, z)$$$ of strings such that the following conditions are true:

- $$$s = x+y+z$$$ (the symbol $$$+$$$ represents the concatenation);
- $$$t = x+\underbrace{ y+\dots+y }_{k \text{ times}} + z$$$ for some integer $$$k$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n < m \leq 10^7$$$) — the length of the strings $$$s$$$ and $$$t$$$, respectively.

The second line contains the string $$$s$$$ of length $$$n$$$, consisting of lowercase letters of the English alphabet.

The third line contains the string $$$t$$$ of length $$$m$$$, consisting of lowercase letters of the English alphabet.

## Output Format
Output a single integer: the number of valid triples $$$(x, y, z)$$$.

## Examples
```input
4 8
abcd
abcbcbcd
```
```output
1
```
-----
```input
3 5
aaa
aaaaa
```
```output
5
```
-----
```input
12 16
abbababacaab
abbababababacaab
```
```output
8
```

## Note
In the first test case, the only valid triple is $$$(x, y, z) = (\texttt{"a"}, \texttt{"bc"}, \texttt{"d"})$$$. In fact,

- $$$\texttt{"abcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"d"}$$$;
- $$$\texttt{"abcbcbcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"d"}$$$.

In the second test case, there are $$$5$$$ valid triples:

- $$$(x, y, z) = (\texttt{""}, \texttt{"a"}, \texttt{"aa"})$$$;
- $$$(x, y, z) = (\texttt{""}, \texttt{"aa"}, \texttt{"a"})$$$;
- $$$(x, y, z) = (\texttt{"a"}, \texttt{"a"}, \texttt{"a"})$$$;
- $$$(x, y, z) = (\texttt{"a"}, \texttt{"aa"}, \texttt{""})$$$;
- $$$(x, y, z) = (\texttt{"aa"}, \texttt{"a"}, \texttt{""})$$$.

In the third test case, there are $$$8$$$ valid triples:

- $$$(x, y, z) = (\texttt{"ab"}, \texttt{"ba"}, \texttt{"babacaab"})$$$;
- $$$(x, y, z) = (\texttt{"abb"}, \texttt{"ab"}, \texttt{"abacaab"})$$$;
- $$$(x, y, z) = (\texttt{"abba"}, \texttt{"ba"}, \texttt{"bacaab"})$$$;
- $$$(x, y, z) = (\texttt{"ab"}, \texttt{"baba"}, \texttt{"bacaab"})$$$;
- $$$(x, y, z) = (\texttt{"abbab"}, \texttt{"ab"}, \texttt{"acaab"})$$$;
- $$$(x, y, z) = (\texttt{"abb"}, \texttt{"abab"}, \texttt{"acaab"})$$$;
- $$$(x, y, z) = (\texttt{"abbaba"}, \texttt{"ba"}, \texttt{"caab"})$$$;
- $$$(x, y, z) = (\texttt{"abba"}, \texttt{"baba"}, \texttt{"caab"})$$$.

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 three digits $$$a$$$, $$$b$$$, $$$c$$$. Two of them are equal, but the third one is different from the other two.

Find the value that occurs exactly once.

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

The only line of each test case contains three digits $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \leq a$$$, $$$b$$$, $$$c \leq 9$$$). Two of the digits are equal, but the third one is different from the other two.

## Output Format
For each test case, output the value that occurs exactly once.

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

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 Latin square is a $$$3 \times 3$$$ grid made up of the letters $$$\texttt{A}$$$, $$$\texttt{B}$$$, and $$$\texttt{C}$$$ such that:

- in each row, the letters $$$\texttt{A}$$$, $$$\texttt{B}$$$, and $$$\texttt{C}$$$ each appear once, and
- in each column, the letters $$$\texttt{A}$$$, $$$\texttt{B}$$$, and $$$\texttt{C}$$$ each appear once.

You are given a Latin square, but one of the letters was replaced with a question mark $$$\texttt{?}$$$. Find the letter that was replaced.

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 108$$$) — the number of testcases.

Each test case contains three lines, each consisting of three characters, representing the Latin square. Each character is one of $$$\texttt{A}$$$, $$$\texttt{B}$$$, $$$\texttt{C}$$$, or $$$\texttt{?}$$$.

Each test case is a Latin square with exactly one of the letters replaced with a question mark $$$\texttt{?}$$$.

## Output Format
For each test case, output the letter that was replaced.

## Examples
```input
3
ABC
C?B
BCA
BCA
CA?
ABC
?AB
BCA
ABC
```
```output
A
B
C
```

## Note
The correct Latin squares for the three test cases are shown below:

$$$$$$\begin{bmatrix} \texttt{A} & \texttt{B} & \texttt{C} \\ \texttt{C} & \color{red}{\texttt{A}} & \texttt{B} \\ \texttt{B} & \texttt{C} & \texttt{A} \\ \end{bmatrix} \quad \begin{bmatrix} \texttt{B} & \texttt{C} & \texttt{A} \\ \texttt{C} & \texttt{A} & \color{red}{\texttt{B}} \\ \texttt{A} & \texttt{B} & \texttt{C} \\ \end{bmatrix} \quad \begin{bmatrix} \color{red}{\texttt{C}} & \texttt{A} & \texttt{B} \\ \texttt{B} & \texttt{C} & \texttt{A} \\ \texttt{A} & \texttt{B} & \texttt{C} \\ \end{bmatrix}$$$$$$

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
Lura was bored and decided to make a simple language using the five letters $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$, $$$\texttt{d}$$$, $$$\texttt{e}$$$. There are two types of letters:

- vowels — the letters $$$\texttt{a}$$$ and $$$\texttt{e}$$$. They are represented by $$$\textsf{V}$$$.
- consonants — the letters $$$\texttt{b}$$$, $$$\texttt{c}$$$, and $$$\texttt{d}$$$. They are represented by $$$\textsf{C}$$$.

A word in the language is a sequence of syllables. Lura has written a word in the language, but she doesn't know how to split it into syllables. Help her break the word into syllables.

For example, given the word $$$\texttt{bacedbab}$$$, it would be split into syllables as $$$\texttt{ba.ced.bab}$$$ (the dot $$$\texttt{.}$$$ represents a syllable boundary).

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the word.

The second line of each test case contains a string consisting of $$$n$$$ lowercase Latin characters  — the word.

All words given are valid words in the language; that is, they only use the letters $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$, $$$\texttt{d}$$$, $$$\texttt{e}$$$, and each word is made up of several syllables.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For test case, output a string denoting the word split into syllables by inserting a dot $$$\texttt{.}$$$ between every pair of adjacent syllables.

If there are multiple possible splittings, output any of them. The input is given in such a way that at least one possible splitting exists.

## Examples
```input
6
8
bacedbab
4
baba
13
daddecabeddad
3
dac
6
dacdac
22
dababbabababbabbababba
```
```output
ba.ced.bab
ba.ba
dad.de.ca.bed.dad
dac
dac.dac
da.bab.ba.ba.bab.bab.ba.bab.ba
```

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
Iulia has $$$n$$$ glasses arranged in a line. The $$$i$$$-th glass has $$$a_i$$$ units of juice in it. Iulia drinks only from odd-numbered glasses, while her date drinks only from even-numbered glasses.

To impress her date, Iulia wants to find a contiguous subarray of these glasses such that both Iulia and her date will have the same amount of juice in total if only the glasses in this subarray are considered. Please help her to do that.

More formally, find out if there exists two indices $$$l$$$, $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$, and $$$a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r} = a_{l + 1} + a_{l + 3} + \dots + a_{r-1}$$$ if $$$l$$$ and $$$r$$$ have the same parity and $$$a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r - 1} = a_{l + 1} + a_{l + 3} + \dots + a_{r}$$$ otherwise.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the amount of juice in each glass.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output "YES" if there exists a subarray satisfying the condition, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
6
3
1 3 2
6
1 1 1 1 1 1
10
1 6 9 8 55 3 14 2 7 2
8
1 2 11 4 1 5 1 2
6
2 6 1 5 7 8
9
2 5 10 4 4 9 6 7 8
```
```output
YES
YES
NO
YES
NO
YES
```

## Note
In the first test case, Iulia can pick $$$l=1$$$ and $$$r=3$$$. Then she drinks $$$a_1+a_3=1+2=3$$$ units and her date drinks $$$a_2=3$$$ units of juice.

In the second test case, Iulia can pick $$$l=2$$$ and $$$r=5$$$. Then she drinks $$$a_3+a_5=1+1=2$$$ units and her date drinks $$$a_2+a_4=1+1=2$$$ units of juice.

In the third test case no such contiguous subarray works.

In the fourth test case, Iulia can pick $$$l=2$$$ and $$$r=8$$$. Then she drinks $$$a_3+a_5+a_7=11+1+1=13$$$ units and her date drinks $$$a_2+a_4+a_6+a_8=2+4+5+2=13$$$ units of juice.

Now solve the problem and return the code.