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

# Problem
A string $$$s$$$ of length $$$n$$$ ($$$1 \le n \le 26$$$) is called alphabetical if it can be obtained using the following algorithm:

- first, write an empty string to $$$s$$$ (i.e. perform the assignment $$$s$$$ := "");
- then perform the next step $$$n$$$ times;
- at the $$$i$$$-th step take $$$i$$$-th lowercase letter of the Latin alphabet and write it either to the left of the string $$$s$$$ or to the right of the string $$$s$$$ (i.e. perform the assignment $$$s$$$ := $$$c+s$$$ or $$$s$$$ := $$$s+c$$$, where $$$c$$$ is the $$$i$$$-th letter of the Latin alphabet).

In other words, iterate over the $$$n$$$ first letters of the Latin alphabet starting from 'a' and etc. Each time we prepend a letter to the left of the string $$$s$$$ or append a letter to the right of the string $$$s$$$. Strings that can be obtained in that way are alphabetical.

For example, the following strings are alphabetical: "a", "ba", "ab", "bac" and "ihfcbadeg". The following strings are not alphabetical: "z", "aa", "ca", "acb", "xyz" and "ddcba".

From the given string, determine if it is alphabetical.

## 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 is written on a separate line that contains one string $$$s$$$. String $$$s$$$ consists of lowercase letters of the Latin alphabet and has a length between $$$1$$$ and $$$26$$$, inclusive.

## Output Format
Output $$$t$$$ lines, each of them must contain the answer to the corresponding test case. Output YES if the given string $$$s$$$ is alphabetical and NO otherwise.

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

## Examples
```input
11
a
ba
ab
bac
ihfcbadeg
z
aa
ca
acb
xyz
ddcba
```
```output
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
```

## Note
The example contains test cases from the main part of the condition.

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

# Problem
You are given an array of positive integers $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ ($$$n \ge 2$$$).

In one step, the array $$$a$$$ is replaced with another array of length $$$n$$$, in which each element is the greatest common divisor (GCD) of two neighboring elements (the element itself and its right neighbor; consider that the right neighbor of the $$$(n - 1)$$$-th element is the $$$0$$$-th element).

Formally speaking, a new array $$$b = [b_0, b_1, \dots, b_{n - 1}]$$$ is being built from array $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ such that $$$b_i$$$ $$$= \gcd(a_i, a_{(i + 1) \mod n})$$$, where $$$\gcd(x, y)$$$ is the greatest common divisor of $$$x$$$ and $$$y$$$, and $$$x \mod y$$$ is the remainder of $$$x$$$ dividing by $$$y$$$. In one step the array $$$b$$$ is built and then the array $$$a$$$ is replaced with $$$b$$$ (that is, the assignment $$$a$$$ := $$$b$$$ is taking place).

For example, if $$$a = [16, 24, 10, 5]$$$ then $$$b = [\gcd(16, 24)$$$, $$$\gcd(24, 10)$$$, $$$\gcd(10, 5)$$$, $$$\gcd(5, 16)]$$$ $$$= [8, 2, 5, 1]$$$. Thus, after one step the array $$$a = [16, 24, 10, 5]$$$ will be equal to $$$[8, 2, 5, 1]$$$.

For a given array $$$a$$$, find the minimum number of steps after which all values $$$a_i$$$ become equal (that is, $$$a_0 = a_1 = \dots = a_{n - 1}$$$). If the original array $$$a$$$ consists of identical elements then consider the number of steps is equal to $$$0$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

Each test case contains two lines. The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — length of the sequence $$$a$$$. The second line contains $$$n$$$ integers $$$a_0, a_1, \dots, a_{n - 1}$$$ ($$$1 \le a_i \le 10^6$$$).

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

## Output Format
Print $$$t$$$ numbers — answers for each test case.

## Examples
```input
5
4
16 24 10 5
4
42 42 42 42
3
4 6 4
5
1 2 3 4 5
6
9 9 27 9 9 63
```
```output
3
0
2
1
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 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a strictly convex polygon with $$$n$$$ vertices.

You will make $$$k$$$ cuts that meet the following conditions:

- each cut is a segment that connects two different nonadjacent vertices;
- two cuts can intersect only at vertices of the polygon.

Your task is to maximize the area of the smallest region that will be formed by the polygon and those $$$k$$$ cuts.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$3 \le n \le 200$$$, $$$0 \le k \le n-3$$$).

The following $$$n$$$ lines describe vertices of the polygon in anticlockwise direction. The $$$i$$$-th line contains two integers $$$x_i$$$, $$$y_i$$$ ($$$|x_i|, |y_i| \le 10^8$$$) — the coordinates of the $$$i$$$-th vertex.

It is guaranteed that the polygon is convex and that no two adjacent sides are parallel.

## Output Format
Print one integer: the maximum possible area of the smallest region after making $$$k$$$ cuts multiplied by $$$2$$$.

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

## Note
In the first example, it's optimal to make cuts between the following pairs of vertices:

- $$$(-2, -4)$$$ and $$$(4, 2)$$$,
- $$$(-2, -4)$$$ and $$$(1, 5)$$$,
- $$$(-5, -1)$$$ and $$$(1, 5)$$$,
- $$$(-5, 0)$$$ and $$$(0, 5)$$$.

Points $$$(-5, -1)$$$, $$$(1, 5)$$$, $$$(0, 5)$$$, $$$(-5, 0)$$$ determine the smallest region with double area of $$$11$$$.

In the second example, it's optimal to make cuts between the following pairs of vertices:

- $$$(2, -1)$$$ and $$$(0, 2)$$$,
- $$$(2, -1)$$$ and $$$(1, 0)$$$,
- $$$(-1, 0)$$$ and $$$(0, 2)$$$.

Points $$$(2, -2)$$$, $$$(2, -1)$$$, $$$(-1, 0)$$$ determine one of the smallest regions with double area of $$$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 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
You are given a string $$$s$$$. You need to find two non-empty strings $$$a$$$ and $$$b$$$ such that the following conditions are satisfied:

1. Strings $$$a$$$ and $$$b$$$ are both subsequences of $$$s$$$.
2. For each index $$$i$$$, character $$$s_i$$$ of string $$$s$$$ must belong to exactly one of strings $$$a$$$ or $$$b$$$.
3. String $$$a$$$ is lexicographically minimum possible; string $$$b$$$ may be any possible string.

Given string $$$s$$$, print any valid $$$a$$$ and $$$b$$$.

Reminder:

A string $$$a$$$ ($$$b$$$) is a subsequence of a string $$$s$$$ if $$$a$$$ ($$$b$$$) can be obtained from $$$s$$$ by deletion of several (possibly, zero) elements. For example, "dores", "cf", and "for" are subsequences of "codeforces", while "decor" and "fork" are not.

A string $$$x$$$ is lexicographically smaller than a string $$$y$$$ if and only if one of the following holds:

- $$$x$$$ is a prefix of $$$y$$$, but $$$x \ne y$$$;
- in the first position where $$$x$$$ and $$$y$$$ differ, the string $$$x$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$y$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The first and only line of each test case contains one string $$$s$$$ ($$$2 \le |s| \le 100$$$ where $$$|s|$$$ means the length of $$$s$$$). String $$$s$$$ consists of lowercase Latin letters.

## Output Format
For each test case, print the strings $$$a$$$ and $$$b$$$ that satisfy the given conditions. If there are multiple answers, print any.

## Examples
```input
3
fc
aaaa
thebrightboiler
```
```output
c f
a aaa
b therightboiler
```

## Note
In the first test case, there are only two choices: either $$$a =$$$ f and $$$b = $$$ c or $$$a = $$$ c and $$$b = $$$ f. And $$$a = $$$c is lexicographically smaller than $$$a = $$$ f.

In the second test case, a is the only character in the string.

In the third test case, it can be proven that b is the lexicographically smallest subsequence of $$$s$$$. The second string can be of two variants; one of them is given here.

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: 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 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
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 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: 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 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
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.
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
Andrew has $$$n$$$ piles with stones. The $$$i$$$-th pile contains $$$a_i$$$ stones. He wants to make his table clean so he decided to put every stone either to the $$$1$$$-st or the $$$n$$$-th pile.

Andrew can perform the following operation any number of times: choose $$$3$$$ indices $$$1 \le i < j < k \le n$$$, such that the $$$j$$$-th pile contains at least $$$2$$$ stones, then he takes $$$2$$$ stones from the pile $$$j$$$ and puts one stone into pile $$$i$$$ and one stone into pile $$$k$$$.

Tell Andrew what is the minimum number of operations needed to move all the stones to piles $$$1$$$ and $$$n$$$, or determine if it's impossible.

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

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

The second line 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 the values $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case print the minimum number of operations needed to move stones to piles $$$1$$$ and $$$n$$$, or print $$$-1$$$ if it's impossible.

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

## Note
In the first test case, it is optimal to do the following:

1. Select $$$(i, j, k) = (1, 2, 5)$$$. The array becomes equal to $$$[2, 0, 2, 3, 7]$$$.
2. Select $$$(i, j, k) = (1, 3, 4)$$$. The array becomes equal to $$$[3, 0, 0, 4, 7]$$$.
3. Twice select $$$(i, j, k) = (1, 4, 5)$$$. The array becomes equal to $$$[5, 0, 0, 0, 9]$$$. This array satisfy the statement, because every stone is moved to piles $$$1$$$ and $$$5$$$.

In the second test case, it's impossible to put all stones into piles with numbers $$$1$$$ and $$$3$$$:

1. At the beginning there's only one possible operation with $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 1, 2]$$$.
2. Now there is no possible operation and the array doesn't satisfy the statement, so the answer is $$$-1$$$.

In the third test case, it's optimal to do the following:

1. Select $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 0, 2]$$$. This array satisfies the statement, because every stone is moved to piles $$$1$$$ and $$$3$$$.

In the fourth test case, it's impossible to do any operation, and the array doesn't satisfy the statement, so the answer is $$$-1$$$.

Now solve the problem and return the code.