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

# Problem
A string is called diverse if it contains consecutive (adjacent) letters of the Latin alphabet and each letter occurs exactly once. For example, the following strings are diverse: "fced", "xyz", "r" and "dabcef". The following string are not diverse: "az", "aa", "bad" and "babc". Note that the letters 'a' and 'z' are not adjacent.

Formally, consider positions of all letters in the string in the alphabet. These positions should form contiguous segment, i.e. they should come one by one without any gaps. And all letters in the string should be distinct (duplicates are not allowed).

You are given a sequence of strings. For each string, if it is diverse, print "Yes". Otherwise, print "No".

## Input Format
The first line contains integer $$$n$$$ ($$$1 \le n \le 100$$$), denoting the number of strings to process. The following $$$n$$$ lines contains strings, one string per line. Each string contains only lowercase Latin letters, its length is between $$$1$$$ and $$$100$$$, inclusive.

## Output Format
Print $$$n$$$ lines, one line per a string in the input. The line should contain "Yes" if the corresponding string is diverse and "No" if the corresponding string is not diverse. You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.

## Examples
```input
8
fced
xyz
r
dabcef
az
aa
bad
babc
```
```output
Yes
Yes
Yes
Yes
No
No
No
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 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
Polycarp has an array $$$a$$$ consisting of $$$n$$$ integers.

He wants to play a game with this array. The game consists of several moves. On the first move he chooses any element and deletes it (after the first move the array contains $$$n-1$$$ elements). For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-... or odd-even-odd-even-...) of the removed elements. Polycarp stops if he can't make a move.

Formally:

- If it is the first move, he chooses any element and deletes it;
- If it is the second or any next move:   if the last deleted element was odd, Polycarp chooses any even element and deletes it;  if the last deleted element was even, Polycarp chooses any odd element and deletes it.
- If after some move Polycarp cannot make a move, the game ends.

Polycarp's goal is to minimize the sum of non-deleted elements of the array after end of the game. If Polycarp can delete the whole array, then the sum of non-deleted elements is zero.

Help Polycarp find this value.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of elements of $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
Print one integer — the minimum possible sum of non-deleted elements of the array after end of the game.

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

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 an array $$$a$$$ consisting of $$$n$$$ integers. You can perform the following operations arbitrary number of times (possibly, zero):

1. Choose a pair of indices $$$(i, j)$$$ such that $$$|i-j|=1$$$ (indices $$$i$$$ and $$$j$$$ are adjacent) and set $$$a_i := a_i + |a_i - a_j|$$$;
2. Choose a pair of indices $$$(i, j)$$$ such that $$$|i-j|=1$$$ (indices $$$i$$$ and $$$j$$$ are adjacent) and set $$$a_i := a_i - |a_i - a_j|$$$.

The value $$$|x|$$$ means the absolute value of $$$x$$$. For example, $$$|4| = 4$$$, $$$|-3| = 3$$$.

Your task is to find the minimum number of operations required to obtain the array of equal elements and print the order of operations to do it.

It is guaranteed that you always can obtain the array of equal elements using such operations.

Note that after each operation each element of the current array should not exceed $$$10^{18}$$$ by absolute value.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
In the first line print one integer $$$k$$$ — the minimum number of operations required to obtain the array of equal elements.

In the next $$$k$$$ lines print operations itself. The $$$p$$$-th operation should be printed as a triple of integers $$$(t_p, i_p, j_p)$$$, where $$$t_p$$$ is either $$$1$$$ or $$$2$$$ ($$$1$$$ means that you perform the operation of the first type, and $$$2$$$ means that you perform the operation of the second type), and $$$i_p$$$ and $$$j_p$$$ are indices of adjacent elements of the array such that $$$1 \le i_p, j_p \le n$$$, $$$|i_p - j_p| = 1$$$. See the examples for better understanding.

Note that after each operation each element of the current array should not exceed $$$10^{18}$$$ by absolute value.

If there are many possible answers, you can print any.

## Examples
```input
5
2 4 6 6 6
```
```output
2
1 2 3 
1 1 2
```
-----
```input
3
2 8 10
```
```output
2
2 2 1 
2 3 2
```
-----
```input
4
1 1 1 1
```
```output
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 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 connected undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. There are no self-loops or multiple edges in the given graph.

You have to direct its edges in such a way that the obtained directed graph does not contain any paths of length two or greater (where the length of path is denoted as the number of traversed edges).

## Input Format
The first line contains two integer numbers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges, respectively.

The following $$$m$$$ lines contain edges: edge $$$i$$$ is given as a pair of vertices $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$). There are no multiple edges in the given graph, i. e. for each pair ($$$u_i, v_i$$$) there are no other pairs ($$$u_i, v_i$$$) and ($$$v_i, u_i$$$) in the list of edges. It is also guaranteed that the given graph is connected (there is a path between any pair of vertex in the given graph).

## Output Format
If it is impossible to direct edges of the given graph in such a way that the obtained directed graph does not contain paths of length at least two, print "NO" in the first line.

Otherwise print "YES" in the first line, and then print any suitable orientation of edges: a binary string (the string consisting only of '0' and '1') of length $$$m$$$. The $$$i$$$-th element of this string should be '0' if the $$$i$$$-th edge of the graph should be directed from $$$u_i$$$ to $$$v_i$$$, and '1' otherwise. Edges are numbered in the order they are given in the input.

## Examples
```input
6 5
1 5
2 1
1 4
3 1
6 1
```
```output
YES
10100
```

## Note
The picture corresponding to the first example:

And one of possible answers:

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 are given an integer $$$n$$$ and an integer $$$k$$$.

In one step you can do one of the following moves:

- decrease $$$n$$$ by $$$1$$$;
- divide $$$n$$$ by $$$k$$$ if $$$n$$$ is divisible by $$$k$$$.

For example, if $$$n = 27$$$ and $$$k = 3$$$ you can do the following steps: $$$27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$.

You are asked to calculate the minimum number of steps to reach $$$0$$$ from $$$n$$$.

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

The only line of each query contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$2 \le k \le 10^{18}$$$).

## Output Format
For each query print the minimum number of steps to reach $$$0$$$ from $$$n$$$ in single line.

## Examples
```input
2
59 3
1000000000000000000 10
```
```output
8
19
```

## Note
Steps for the first test case are: $$$59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$.

In the second test case you have to divide $$$n$$$ by $$$k$$$ $$$18$$$ times and then decrease $$$n$$$ by $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a function $$$f$$$ written in some basic language. The function accepts an integer value, which is immediately written into some variable $$$x$$$. $$$x$$$ is an integer variable and can be assigned values from $$$0$$$ to $$$2^{32}-1$$$. The function contains three types of commands:

- for $$$n$$$ — for loop;
- end — every command between "for $$$n$$$" and corresponding "end" is executed $$$n$$$ times;
- add — adds 1 to $$$x$$$.

After the execution of these commands, value of $$$x$$$ is returned.

Every "for $$$n$$$" is matched with "end", thus the function is guaranteed to be valid. "for $$$n$$$" can be immediately followed by "end"."add" command can be outside of any for loops.

Notice that "add" commands might overflow the value of $$$x$$$! It means that the value of $$$x$$$ becomes greater than $$$2^{32}-1$$$ after some "add" command.

Now you run $$$f(0)$$$ and wonder if the resulting value of $$$x$$$ is correct or some overflow made it incorrect.

If overflow happened then output "OVERFLOW!!!", otherwise print the resulting value of $$$x$$$.

## Input Format
The first line contains a single integer $$$l$$$ ($$$1 \le l \le 10^5$$$) — the number of lines in the function.

Each of the next $$$l$$$ lines contains a single command of one of three types:

- for $$$n$$$ ($$$1 \le n \le 100$$$) — for loop;
- end — every command between "for $$$n$$$" and corresponding "end" is executed $$$n$$$ times;
- add — adds 1 to $$$x$$$.

## Output Format
If overflow happened during execution of $$$f(0)$$$, then output "OVERFLOW!!!", otherwise print the resulting value of $$$x$$$.

## Examples
```input
9
add
for 43
end
for 10
for 15
add
end
add
end
```
```output
161
```
-----
```input
2
for 62
end
```
```output
0
```
-----
```input
11
for 100
for 100
for 100
for 100
for 100
add
end
end
end
end
end
```
```output
OVERFLOW!!!
```

## Note
In the first example the first "add" is executed 1 time, the second "add" is executed 150 times and the last "add" is executed 10 times. Note that "for $$$n$$$" can be immediately followed by "end" and that "add" can be outside of any for loops.

In the second example there are no commands "add", thus the returning value is 0.

In the third example "add" command is executed too many times, which causes $$$x$$$ to go over $$$2^{32}-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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
At first, there was a legend related to the name of the problem, but now it's just a formal statement.

You are given $$$n$$$ points $$$a_1, a_2, \dots, a_n$$$ on the $$$OX$$$ axis. Now you are asked to find such an integer point $$$x$$$ on $$$OX$$$ axis that $$$f_k(x)$$$ is minimal possible.

The function $$$f_k(x)$$$ can be described in the following way:

- form a list of distances $$$d_1, d_2, \dots, d_n$$$ where $$$d_i = |a_i - x|$$$ (distance between $$$a_i$$$ and $$$x$$$);
- sort list $$$d$$$ in non-descending order;
- take $$$d_{k + 1}$$$ as a result.

If there are multiple optimal answers you can print any of them.

## Input Format
The first line contains single integer $$$T$$$ ($$$ 1 \le T \le 2 \cdot 10^5$$$) — number of queries. Next $$$2 \cdot T$$$ lines contain descriptions of queries. All queries are independent.

The first line of each query contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k < n$$$) — the number of points and constant $$$k$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 < a_2 < \dots < a_n \le 10^9$$$) — points in ascending order.

It's guaranteed that $$$\sum{n}$$$ doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
Print $$$T$$$ integers — corresponding points $$$x$$$ which have minimal possible value of $$$f_k(x)$$$. If there are multiple answers you can print any of them.

## Examples
```input
3
3 2
1 2 5
2 1
1 1000000000
1 0
4
```
```output
3
500000000
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 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 an array $$$a_1, a_2, \dots, a_n$$$ and an integer $$$k$$$.

You are asked to divide this array into $$$k$$$ non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray. Let $$$f(i)$$$ be the index of subarray the $$$i$$$-th element belongs to. Subarrays are numbered from left to right and from $$$1$$$ to $$$k$$$.

Let the cost of division be equal to $$$\sum\limits_{i=1}^{n} (a_i \cdot f(i))$$$. For example, if $$$a = [1, -2, -3, 4, -5, 6, -7]$$$ and we divide it into $$$3$$$ subbarays in the following way: $$$[1, -2, -3], [4, -5], [6, -7]$$$, then the cost of division is equal to $$$1 \cdot 1 - 2 \cdot 1 - 3 \cdot 1 + 4 \cdot 2 - 5 \cdot 2 + 6 \cdot 3 - 7 \cdot 3 = -9$$$.

Calculate the maximum cost you can obtain by dividing the array $$$a$$$ into $$$k$$$ non-empty consecutive subarrays.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$ |a_i| \le 10^6$$$).

## Output Format
Print the maximum cost you can obtain by dividing the array $$$a$$$ into $$$k$$$ nonempty consecutive subarrays.

## Examples
```input
5 2
-1 -2 5 -4 8
```
```output
15
```
-----
```input
7 6
-3 0 -1 -2 -2 -4 -1
```
```output
-45
```
-----
```input
4 1
3 -1 6 0
```
```output
8
```

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 $$$n$$$ intervals in form $$$[l; r]$$$ on a number line.

You are also given $$$m$$$ queries in form $$$[x; y]$$$. What is the minimal number of intervals you have to take so that every point (not necessarily integer) from $$$x$$$ to $$$y$$$ is covered by at least one of them?

If you can't choose intervals so that every point from $$$x$$$ to $$$y$$$ is covered, then print -1 for that query.

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

Each of the next $$$n$$$ lines contains two integer numbers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i < r_i \le 5 \cdot 10^5$$$) — the given intervals.

Each of the next $$$m$$$ lines contains two integer numbers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i < y_i \le 5 \cdot 10^5$$$) — the queries.

## Output Format
Print $$$m$$$ integer numbers. The $$$i$$$-th number should be the answer to the $$$i$$$-th query: either the minimal number of intervals you have to take so that every point (not necessarily integer) from $$$x_i$$$ to $$$y_i$$$ is covered by at least one of them or -1 if you can't choose intervals so that every point from $$$x_i$$$ to $$$y_i$$$ is covered.

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

## Note
In the first example there are three queries:

1. query $$$[1; 3]$$$ can be covered by interval $$$[1; 3]$$$;
2. query $$$[1; 4]$$$ can be covered by intervals $$$[1; 3]$$$ and $$$[2; 4]$$$. There is no way to cover $$$[1; 4]$$$ by a single interval;
3. query $$$[3; 4]$$$ can be covered by interval $$$[2; 4]$$$. It doesn't matter that the other points are covered besides the given query.

In the second example there are four queries:

1. query $$$[1; 2]$$$ can be covered by interval $$$[1; 3]$$$. Note that you can choose any of the two given intervals $$$[1; 3]$$$;
2. query $$$[1; 3]$$$ can be covered by interval $$$[1; 3]$$$;
3. query $$$[1; 4]$$$ can't be covered by any set of intervals;
4. query $$$[1; 5]$$$ can't be covered by any set of intervals. Note that intervals $$$[1; 3]$$$ and $$$[4; 5]$$$ together don't cover $$$[1; 5]$$$ because even non-integer points should be covered. Here $$$3.5$$$, for example, isn't covered.

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 $$$a_1, a_2, \dots, a_n$$$.

Let's call some subarray $$$a_l, a_{l + 1}, \dots , a_r$$$ of this array a subpermutation if it contains all integers from $$$1$$$ to $$$r-l+1$$$ exactly once. For example, array $$$a = [2, 2, 1, 3, 2, 3, 1]$$$ contains $$$6$$$ subarrays which are subpermutations: $$$[a_2 \dots a_3]$$$, $$$[a_2 \dots a_4]$$$, $$$[a_3 \dots a_3]$$$, $$$[a_3 \dots a_5]$$$, $$$[a_5 \dots a_7]$$$, $$$[a_7 \dots a_7]$$$.

You are asked to calculate the number of subpermutations.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le n$$$).

This array can contain the same integers.

## Output Format
Print the number of subpermutations of the array $$$a$$$.

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

## Note
There are $$$7$$$ subpermutations in the first test case. Their segments of indices are $$$[1, 4]$$$, $$$[3, 3]$$$, $$$[3, 6]$$$, $$$[4, 7]$$$, $$$[6, 7]$$$, $$$[7, 7]$$$ and $$$[7, 8]$$$.

In the second test case $$$6$$$ subpermutations exist: $$$[1, 1]$$$, $$$[2, 2]$$$, $$$[2, 3]$$$, $$$[3, 4]$$$, $$$[4, 4]$$$ and $$$[4, 5]$$$.

Now solve the problem and return the code.