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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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.