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
You are policeman and you are playing a game with Slavik. The game is turn-based and each turn consists of two phases. During the first phase you make your move and during the second phase Slavik makes his move.

There are $$$n$$$ doors, the $$$i$$$-th door initially has durability equal to $$$a_i$$$.

During your move you can try to break one of the doors. If you choose door $$$i$$$ and its current durability is $$$b_i$$$ then you reduce its durability to $$$max(0, b_i - x)$$$ (the value $$$x$$$ is given).

During Slavik's move he tries to repair one of the doors. If he chooses door $$$i$$$ and its current durability is $$$b_i$$$ then he increases its durability to $$$b_i + y$$$ (the value $$$y$$$ is given). Slavik cannot repair doors with current durability equal to $$$0$$$.

The game lasts $$$10^{100}$$$ turns. If some player cannot make his move then he has to skip it.

Your goal is to maximize the number of doors with durability equal to $$$0$$$ at the end of the game. You can assume that Slavik wants to minimize the number of such doors. What is the number of such doors in the end if you both play optimally?

## Input Format
The first line of the input contains three integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n \le 100$$$, $$$1 \le x, y \le 10^5$$$) — the number of doors, value $$$x$$$ and value $$$y$$$, respectively.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$), where $$$a_i$$$ is the initial durability of the $$$i$$$-th door.

## Output Format
Print one integer — the number of doors with durability equal to $$$0$$$ at the end of the game, if you and Slavik both play optimally.

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

## Note
Clarifications about the optimal strategy will be ignored.

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$$$ consisting of exactly $$$n$$$ characters, and each character is either '0', '1' or '2'. Such strings are called ternary strings.

Your task is to replace minimum number of characters in this string with other characters to obtain a balanced ternary string (balanced ternary string is a ternary string such that the number of characters '0' in this string is equal to the number of characters '1', and the number of characters '1' (and '0' obviously) is equal to the number of characters '2').

Among all possible balanced ternary strings you have to obtain the lexicographically (alphabetically) smallest.

Note that you can neither remove characters from the string nor add characters to the string. Also note that you can replace the given characters only with characters '0', '1' and '2'.

It is guaranteed that the answer exists.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$, $$$n$$$ is divisible by $$$3$$$) — the number of characters in $$$s$$$.

The second line contains the string $$$s$$$ consisting of exactly $$$n$$$ characters '0', '1' and '2'.

## Output Format
Print one string — the lexicographically (alphabetically) smallest balanced ternary string which can be obtained from the given one with minimum number of replacements.

Because $$$n$$$ is divisible by $$$3$$$ it is obvious that the answer exists. And it is obvious that there is only one possible answer.

## Examples
```input
3
121
```
```output
021
```
-----
```input
6
000000
```
```output
001122
```
-----
```input
6
211200
```
```output
211200
```
-----
```input
6
120110
```
```output
120120
```

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. Let's denote monotonic renumeration of array $$$a$$$ as an array $$$b$$$ consisting of $$$n$$$ integers such that all of the following conditions are met:

- $$$b_1 = 0$$$;
- for every pair of indices $$$i$$$ and $$$j$$$ such that $$$1 \le i, j \le n$$$, if $$$a_i = a_j$$$, then $$$b_i = b_j$$$ (note that if $$$a_i \ne a_j$$$, it is still possible that $$$b_i = b_j$$$);
- for every index $$$i \in [1, n - 1]$$$ either $$$b_i = b_{i + 1}$$$ or $$$b_i + 1 = b_{i + 1}$$$.

For example, if $$$a = [1, 2, 1, 2, 3]$$$, then two possible monotonic renumerations of $$$a$$$ are $$$b = [0, 0, 0, 0, 0]$$$ and $$$b = [0, 0, 0, 0, 1]$$$.

Your task is to calculate the number of different monotonic renumerations of $$$a$$$. The answer may be large, so print it modulo $$$998244353$$$.

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

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

## Output Format
Print one integer — the number of different monotonic renumerations of $$$a$$$, taken modulo $$$998244353$$$.

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

# Problem
You are given a matrix $$$a$$$, consisting of $$$n$$$ rows and $$$m$$$ columns. Each cell contains an integer in it.

You can change the order of rows arbitrarily (including leaving the initial order), but you can't change the order of cells in a row. After you pick some order of rows, you traverse the whole matrix the following way: firstly visit all cells of the first column from the top row to the bottom one, then the same for the second column and so on. During the traversal you write down the sequence of the numbers on the cells in the same order you visited them. Let that sequence be $$$s_1, s_2, \dots, s_{nm}$$$.

The traversal is $$$k$$$-acceptable if for all $$$i$$$ ($$$1 \le i \le nm - 1$$$) $$$|s_i - s_{i + 1}| \ge k$$$.

Find the maximum integer $$$k$$$ such that there exists some order of rows of matrix $$$a$$$ that it produces a $$$k$$$-acceptable traversal.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 16$$$, $$$1 \le m \le 10^4$$$, $$$2 \le nm$$$) — the number of rows and the number of columns, respectively.

Each of the next $$$n$$$ lines contains $$$m$$$ integers ($$$1 \le a_{i, j} \le 10^9$$$) — the description of the matrix.

## Output Format
Print a single integer $$$k$$$ — the maximum number such that there exists some order of rows of matrix $$$a$$$ that it produces an $$$k$$$-acceptable traversal.

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

## Note
In the first example you can rearrange rows as following to get the $$$5$$$-acceptable traversal:

Then the sequence $$$s$$$ will be $$$[5, 10, 4, 9, 3, 8, 3, 9]$$$. Each pair of neighbouring elements have at least $$$k = 5$$$ difference between them.

In the second example the maximum $$$k = 0$$$, any order is $$$0$$$-acceptable.

In the third example the given order is already $$$3$$$-acceptable, you can leave it as it is.

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
Lunar New Year is approaching, and you bought a matrix with lots of "crosses".

This matrix $$$M$$$ of size $$$n \times n$$$ contains only 'X' and '.' (without quotes). The element in the $$$i$$$-th row and the $$$j$$$-th column $$$(i, j)$$$ is defined as $$$M(i, j)$$$, where $$$1 \leq i, j \leq n$$$. We define a cross appearing in the $$$i$$$-th row and the $$$j$$$-th column ($$$1 < i, j < n$$$) if and only if $$$M(i, j) = M(i - 1, j - 1) = M(i - 1, j + 1) = M(i + 1, j - 1) = M(i + 1, j + 1) = $$$ 'X'.

The following figure illustrates a cross appearing at position $$$(2, 2)$$$ in a $$$3 \times 3$$$ matrix.

X.X.X.X.X

Your task is to find out the number of crosses in the given matrix $$$M$$$. Two crosses are different if and only if they appear in different rows or columns.

## Input Format
The first line contains only one positive integer $$$n$$$ ($$$1 \leq n \leq 500$$$), denoting the size of the matrix $$$M$$$.

The following $$$n$$$ lines illustrate the matrix $$$M$$$. Each line contains exactly $$$n$$$ characters, each of them is 'X' or '.'. The $$$j$$$-th element in the $$$i$$$-th line represents $$$M(i, j)$$$, where $$$1 \leq i, j \leq n$$$.

## Output Format
Output a single line containing only one integer number $$$k$$$ — the number of crosses in the given matrix $$$M$$$.

## Examples
```input
5
.....
.XXX.
.XXX.
.XXX.
.....
```
```output
1
```
-----
```input
2
XX
XX
```
```output
0
```
-----
```input
6
......
X.X.X.
.X.X.X
X.X.X.
.X.X.X
......
```
```output
4
```

## Note
In the first sample, a cross appears at $$$(3, 3)$$$, so the answer is $$$1$$$.

In the second sample, no crosses appear since $$$n < 3$$$, so the answer is $$$0$$$.

In the third sample, crosses appear at $$$(3, 2)$$$, $$$(3, 4)$$$, $$$(4, 3)$$$, $$$(4, 5)$$$, so the answer is $$$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
Little Petya loves presents. His mum bought him two strings of the same size for his birthday. The strings consist of uppercase and lowercase Latin letters. Now Petya wants to compare those two strings lexicographically. The letters' case does not matter, that is an uppercase letter is considered equivalent to the corresponding lowercase letter. Help Petya perform the comparison.

## Input Format
Each of the first two lines contains a bought string. The strings' lengths range from 1 to 100 inclusive. It is guaranteed that the strings are of the same length and also consist of uppercase and lowercase Latin letters.

## Output Format
If the first string is less than the second one, print "-1". If the second string is less than the first one, print "1". If the strings are equal, print "0". Note that the letters' case is not taken into consideration when the strings are compared.

## Examples
```input
aaaa
aaaA
```
```output
0
```
-----
```input
abs
Abz
```
```output
-1
```
-----
```input
abcdefg
AbCdEfF
```
```output
1
```

## Note
If you want more formal information about the lexicographical order (also known as the "dictionary order" or "alphabetical order"), you can visit the following site:

- http://en.wikipedia.org/wiki/Lexicographical_order

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
Little Petya loves playing with squares. Mum bought him a square 2n × 2n in size. Petya marked a cell inside the square and now he is solving the following task.

The task is to draw a broken line that would go along the grid lines and that would cut the square into two equal parts. The cutting line should not have any common points with the marked cell and the resulting two parts should be equal up to rotation.

Petya wants to determine whether it is possible to cut the square in the required manner given the sizes of the square side and the coordinates of the marked cell. Help him.

## Input Format
The first line contains three space-separated integers 2n, x and y (2 ≤ 2n ≤ 100, 1 ≤ x, y ≤ 2n), representing the length of a square's side and the coordinates of the marked cell. It is guaranteed that 2n is even.

The coordinates of the marked cell are represented by a pair of numbers x y, where x represents the number of the row and y represents the number of the column. The rows and columns are numbered by consecutive integers from 1 to 2n. The rows are numbered from top to bottom and the columns are numbered from the left to the right.

## Output Format
If the square is possible to cut, print "YES", otherwise print "NO" (without the quotes).

## Examples
```input
4 1 1
```
```output
YES
```
-----
```input
2 2 2
```
```output
NO
```

## Note
A sample test from the statement and one of the possible ways of cutting the square are shown in the picture:

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
Polycarp is going to participate in the contest. It starts at $$$h_1:m_1$$$ and ends at $$$h_2:m_2$$$. It is guaranteed that the contest lasts an even number of minutes (i.e. $$$m_1 \% 2 = m_2 \% 2$$$, where $$$x \% y$$$ is $$$x$$$ modulo $$$y$$$). It is also guaranteed that the entire contest is held during a single day. And finally it is guaranteed that the contest lasts at least two minutes.

Polycarp wants to know the time of the midpoint of the contest. For example, if the contest lasts from $$$10:00$$$ to $$$11:00$$$ then the answer is $$$10:30$$$, if the contest lasts from $$$11:10$$$ to $$$11:12$$$ then the answer is $$$11:11$$$.

## Input Format
The first line of the input contains two integers $$$h_1$$$ and $$$m_1$$$ in the format hh:mm.

The second line of the input contains two integers $$$h_2$$$ and $$$m_2$$$ in the same format (hh:mm).

It is guaranteed that $$$0 \le h_1, h_2 \le 23$$$ and $$$0 \le m_1, m_2 \le 59$$$.

It is guaranteed that the contest lasts an even number of minutes (i.e. $$$m_1 \% 2 = m_2 \% 2$$$, where $$$x \% y$$$ is $$$x$$$ modulo $$$y$$$). It is also guaranteed that the entire contest is held during a single day. And finally it is guaranteed that the contest lasts at least two minutes.

## Output Format
Print two integers $$$h_3$$$ and $$$m_3$$$ ($$$0 \le h_3 \le 23, 0 \le m_3 \le 59$$$) corresponding to the midpoint of the contest in the format hh:mm. Print each number as exactly two digits (prepend a number with leading zero if needed), separate them with ':'.

## Examples
```input
10:00
11:00
```
```output
10:30
```
-----
```input
11:10
11:12
```
```output
11:11
```
-----
```input
01:02
03:02
```
```output
02:02
```

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
International Women's Day is coming soon! Polycarp is preparing for the holiday.

There are $$$n$$$ candy boxes in the shop for sale. The $$$i$$$-th box contains $$$d_i$$$ candies.

Polycarp wants to prepare the maximum number of gifts for $$$k$$$ girls. Each gift will consist of exactly two boxes. The girls should be able to share each gift equally, so the total amount of candies in a gift (in a pair of boxes) should be divisible by $$$k$$$. In other words, two boxes $$$i$$$ and $$$j$$$ ($$$i \ne j$$$) can be combined as a gift if $$$d_i + d_j$$$ is divisible by $$$k$$$.

How many boxes will Polycarp be able to give? Of course, each box can be a part of no more than one gift. Polycarp cannot use boxes "partially" or redistribute candies between them.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le k \le 100$$$) — the number the boxes and the number the girls.

The second line of the input contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^9$$$), where $$$d_i$$$ is the number of candies in the $$$i$$$-th box.

## Output Format
Print one integer — the maximum number of the boxes Polycarp can give as gifts.

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

## Note
In the first example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes):

- $$$(2, 3)$$$;
- $$$(5, 6)$$$;
- $$$(1, 4)$$$.

So the answer is $$$6$$$.

In the second example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes):

- $$$(6, 8)$$$;
- $$$(2, 3)$$$;
- $$$(1, 4)$$$;
- $$$(5, 7)$$$.

So the answer is $$$8$$$.

In the third example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes):

- $$$(1, 2)$$$;
- $$$(6, 7)$$$.

So the answer is $$$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 a coach at your local university. There are $$$n$$$ students under your supervision, the programming skill of the $$$i$$$-th student is $$$a_i$$$.

You have to create a team for a new programming competition. As you know, the more students some team has the more probable its victory is! So you have to create a team with the maximum number of students. But you also know that a team should be balanced. It means that the programming skill of each pair of students in a created team should differ by no more than $$$5$$$.

Your task is to report the maximum possible number of students in a balanced team.

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

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is a programming skill of the $$$i$$$-th student.

## Output Format
Print one integer — the maximum possible number of students in a balanced team.

## Examples
```input
6
1 10 17 12 15 2
```
```output
3
```
-----
```input
10
1337 1337 1337 1337 1337 1337 1337 1337 1337 1337
```
```output
10
```
-----
```input
6
1 1000 10000 10 100 1000000000
```
```output
1
```

## Note
In the first example you can create a team with skills $$$[12, 17, 15]$$$.

In the second example you can take all students in a team because their programming skills are equal.

In the third example you can create a team consisting of a single student (and you cannot create a team consisting of at least two students).

Now solve the problem and return the code.