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
A little bear Limak plays a game. He has five cards. There is one number written on each card. Each number is a positive integer.

Limak can discard (throw out) some cards. His goal is to minimize the sum of numbers written on remaining (not discarded) cards.

He is allowed to at most once discard two or three cards with the same number. Of course, he won't discard cards if it's impossible to choose two or three cards with the same number.

Given five numbers written on cards, cay you find the minimum sum of numbers on remaining cards?

## Input Format
The only line of the input contains five integers t1, t2, t3, t4 and t5 (1 ≤ ti ≤ 100) — numbers written on cards.

## Output Format
Print the minimum possible sum of numbers written on remaining cards.

## Examples
```input
7 3 7 3 20
```
```output
26
```
-----
```input
7 9 3 1 8
```
```output
28
```
-----
```input
10 10 10 10 10
```
```output
20
```

## Note
In the first sample, Limak has cards with numbers 7, 3, 7, 3 and 20. Limak can do one of the following.

- Do nothing and the sum would be 7 + 3 + 7 + 3 + 20 = 40.
- Remove two cards with a number 7. The remaining sum would be 3 + 3 + 20 = 26.
- Remove two cards with a number 3. The remaining sum would be 7 + 7 + 20 = 34.

You are asked to minimize the sum so the answer is 26.

In the second sample, it's impossible to find two or three cards with the same number. Hence, Limak does nothing and the sum is 7 + 9 + 1 + 3 + 8 = 28.

In the third sample, all cards have the same number. It's optimal to discard any three cards. The sum of two remaining numbers is 10 + 10 = 20.

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
There are n cities in Bearland, numbered 1 through n. Cities are arranged in one long row. The distance between cities i and j is equal to |i - j|.

Limak is a police officer. He lives in a city a. His job is to catch criminals. It's hard because he doesn't know in which cities criminals are. Though, he knows that there is at most one criminal in each city.

Limak is going to use a BCD (Bear Criminal Detector). The BCD will tell Limak how many criminals there are for every distance from a city a. After that, Limak can catch a criminal in each city for which he is sure that there must be a criminal.

You know in which cities criminals are. Count the number of criminals Limak will catch, after he uses the BCD.

## Input Format
The first line of the input contains two integers n and a (1 ≤ a ≤ n ≤ 100) — the number of cities and the index of city where Limak lives.

The second line contains n integers t1, t2, ..., tn (0 ≤ ti ≤ 1). There are ti criminals in the i-th city.

## Output Format
Print the number of criminals Limak will catch.

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

## Note
In the first sample, there are six cities and Limak lives in the third one (blue arrow below). Criminals are in cities marked red.

Using the BCD gives Limak the following information:

- There is one criminal at distance 0 from the third city — Limak is sure that this criminal is exactly in the third city.
- There is one criminal at distance 1 from the third city — Limak doesn't know if a criminal is in the second or fourth city.
- There are two criminals at distance 2 from the third city — Limak is sure that there is one criminal in the first city and one in the fifth city.
- There are zero criminals for every greater distance.

So, Limak will catch criminals in cities 1, 3 and 5, that is 3 criminals in total.

In the second sample (drawing below), the BCD gives Limak the information that there is one criminal at distance 2 from Limak's city. There is only one city at distance 2 so Limak is sure where a criminal 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
Vasya has the square chessboard of size n × n and m rooks. Initially the chessboard is empty. Vasya will consequently put the rooks on the board one after another.

The cell of the field is under rook's attack, if there is at least one rook located in the same row or in the same column with this cell. If there is a rook located in the cell, this cell is also under attack.

You are given the positions of the board where Vasya will put rooks. For each rook you have to determine the number of cells which are not under attack after Vasya puts it on the board.

## Input Format
The first line of the input contains two integers n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ min(100 000, n2)) — the size of the board and the number of rooks.

Each of the next m lines contains integers xi and yi (1 ≤ xi, yi ≤ n) — the number of the row and the number of the column where Vasya will put the i-th rook. Vasya puts rooks on the board in the order they appear in the input. It is guaranteed that any cell will contain no more than one rook.

## Output Format
Print m integer, the i-th of them should be equal to the number of cells that are not under attack after first i rooks are put.

## Examples
```input
3 3
1 1
3 1
2 2
```
```output
4 2 0
```
-----
```input
5 2
1 5
5 1
```
```output
16 9
```
-----
```input
100000 1
300 400
```
```output
9999800001
```

## Note
On the picture below show the state of the board after put each of the three rooks. The cells which painted with grey color is not under the attack.

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
Sergei B., the young coach of Pokemons, has found the big house which consists of n flats ordered in a row from left to right. It is possible to enter each flat from the street. It is possible to go out from each flat. Also, each flat is connected with the flat to the left and the flat to the right. Flat number 1 is only connected with the flat number 2 and the flat number n is only connected with the flat number n - 1.

There is exactly one Pokemon of some type in each of these flats. Sergei B. asked residents of the house to let him enter their flats in order to catch Pokemons. After consulting the residents of the house decided to let Sergei B. enter one flat from the street, visit several flats and then go out from some flat. But they won't let him visit the same flat more than once.

Sergei B. was very pleased, and now he wants to visit as few flats as possible in order to collect Pokemons of all types that appear in this house. Your task is to help him and determine this minimum number of flats he has to visit.

## Input Format
The first line contains the integer n (1 ≤ n ≤ 100 000) — the number of flats in the house.

The second line contains the row s with the length n, it consists of uppercase and lowercase letters of English alphabet, the i-th letter equals the type of Pokemon, which is in the flat number i.

## Output Format
Print the minimum number of flats which Sergei B. should visit in order to catch Pokemons of all types which there are in the house.

## Examples
```input
3
AaA
```
```output
2
```
-----
```input
7
bcAAcbc
```
```output
3
```
-----
```input
6
aaBCCe
```
```output
5
```

## Note
In the first test Sergei B. can begin, for example, from the flat number 1 and end in the flat number 2.

In the second test Sergei B. can begin, for example, from the flat number 4 and end in the flat number 6.

In the third test Sergei B. must begin from the flat number 2 and end in the flat number 6.

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

# Problem
ZS the Coder is given two permutations p and q of {1, 2, ..., n}, but some of their elements are replaced with 0. The distance between two permutations p and q is defined as the minimum number of moves required to turn p into q. A move consists of swapping exactly 2 elements of p.

ZS the Coder wants to determine the number of ways to replace the zeros with positive integers from the set {1, 2, ..., n} such that p and q are permutations of {1, 2, ..., n} and the distance between p and q is exactly k.

ZS the Coder wants to find the answer for all 0 ≤ k ≤ n - 1. Can you help him?

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 250) — the number of elements in the permutations.

The second line contains n integers, p1, p2, ..., pn (0 ≤ pi ≤ n) — the permutation p. It is guaranteed that there is at least one way to replace zeros such that p is a permutation of {1, 2, ..., n}.

The third line contains n integers, q1, q2, ..., qn (0 ≤ qi ≤ n) — the permutation q. It is guaranteed that there is at least one way to replace zeros such that q is a permutation of {1, 2, ..., n}.

## Output Format
Print n integers, i-th of them should denote the answer for k = i - 1. Since the answer may be quite large, and ZS the Coder loves weird primes, print them modulo 998244353 = 223·7·17 + 1, which is a prime.

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

## Note
In the first sample case, there is the only way to replace zeros so that it takes 0 swaps to convert p into q, namely p = (1, 2, 3), q = (1, 2, 3).

There are two ways to replace zeros so that it takes 1 swap to turn p into q. One of these ways is p = (1, 2, 3), q = (3, 2, 1), then swapping 1 and 3 from p transform it into q. The other way is p = (1, 3, 2), q = (1, 2, 3). Swapping 2 and 3 works in this case.

Finally, there is one way to replace zeros so that it takes 2 swaps to turn p into q, namely p = (1, 3, 2), q = (3, 2, 1). Then, we can transform p into q like following: $$(1,3,2)\to(2,3,1)\to(3,2,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 names of two days of the week.

Please, determine whether it is possible that during some non-leap year the first day of some month was equal to the first day of the week you are given, while the first day of the next month was equal to the second day of the week you are given. Both months should belong to one year.

In this problem, we consider the Gregorian calendar to be used. The number of months in this calendar is equal to 12. The number of days in months during any non-leap year is: 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31.

Names of the days of the week are given with lowercase English letters: "monday", "tuesday", "wednesday", "thursday", "friday", "saturday", "sunday".

## Input Format
The input consists of two lines, each of them containing the name of exactly one day of the week. It's guaranteed that each string in the input is from the set "monday", "tuesday", "wednesday", "thursday", "friday", "saturday", "sunday".

## Output Format
Print "YES" (without quotes) if such situation is possible during some non-leap year. Otherwise, print "NO" (without quotes).

## Examples
```input
monday
tuesday
```
```output
NO
```
-----
```input
sunday
sunday
```
```output
YES
```
-----
```input
saturday
tuesday
```
```output
YES
```

## Note
In the second sample, one can consider February 1 and March 1 of year 2015. Both these days were Sundays.

In the third sample, one can consider July 1 and August 1 of year 2017. First of these two days is Saturday, while the second one is Tuesday.

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 table consisting of n rows and m columns.

Numbers in each row form a permutation of integers from 1 to m.

You are allowed to pick two elements in one row and swap them, but no more than once for each row. Also, no more than once you are allowed to pick two columns and swap them. Thus, you are allowed to perform from 0 to n + 1 actions in total. Operations can be performed in any order.

You have to check whether it's possible to obtain the identity permutation 1, 2, ..., m in each row. In other words, check if one can perform some of the operation following the given rules and make each row sorted in increasing order.

## Input Format
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 20) — the number of rows and the number of columns in the given table.

Each of next n lines contains m integers — elements of the table. It's guaranteed that numbers in each line form a permutation of integers from 1 to m.

## Output Format
If there is a way to obtain the identity permutation in each row by following the given rules, print "YES" (without quotes) in the only line of the output. Otherwise, print "NO" (without quotes).

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

## Note
In the first sample, one can act in the following way:

1. Swap second and third columns. Now the table is 1 2 3 4 1 4 3 2
2. In the second row, swap the second and the fourth elements. Now the table is 1 2 3 4 1 2 3 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 a string s, consisting of lowercase English letters, and the integer m.

One should choose some symbols from the given string so that any contiguous subsegment of length m has at least one selected symbol. Note that here we choose positions of symbols, not the symbols themselves.

Then one uses the chosen symbols to form a new string. All symbols from the chosen position should be used, but we are allowed to rearrange them in any order.

Formally, we choose a subsequence of indices 1 ≤ i1 < i2 < ... < it ≤ |s|. The selected sequence must meet the following condition: for every j such that 1 ≤ j ≤ |s| - m + 1, there must be at least one selected index that belongs to the segment [j,  j + m - 1], i.e. there should exist a k from 1 to t, such that j ≤ ik ≤ j + m - 1.

Then we take any permutation p of the selected indices and form a new string sip1sip2... sipt.

Find the lexicographically smallest string, that can be obtained using this procedure.

## Input Format
The first line of the input contains a single integer m (1 ≤ m ≤ 100 000).

The second line contains the string s consisting of lowercase English letters. It is guaranteed that this string is non-empty and its length doesn't exceed 100 000. It is also guaranteed that the number m doesn't exceed the length of the string s.

## Output Format
Print the single line containing the lexicographically smallest string, that can be obtained using the procedure described above.

## Examples
```input
3
cbabc
```
```output
a
```
-----
```input
2
abcab
```
```output
aab
```
-----
```input
3
bcabcbaccba
```
```output
aaabb
```

## Note
In the first sample, one can choose the subsequence {3} and form a string "a".

In the second sample, one can choose the subsequence {1, 2, 4} (symbols on this positions are 'a', 'b' and 'a') and rearrange the chosen symbols to form a string "aab".

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
A tree is a connected graph without cycles.

Two trees, consisting of n vertices each, are called isomorphic if there exists a permutation p: {1, ..., n} → {1, ..., n} such that the edge (u, v) is present in the first tree if and only if the edge (pu, pv) is present in the second tree.

Vertex of the tree is called internal if its degree is greater than or equal to two.

Count the number of different non-isomorphic trees, consisting of n vertices, such that the degree of each internal vertex is exactly d. Print the answer over the given prime modulo mod.

## Input Format
The single line of the input contains three integers n, d and mod (1 ≤ n ≤ 1000, 2 ≤ d ≤ 10, 108 ≤ mod ≤ 109)  — the number of vertices in the tree, the degree of internal vertices and the prime modulo.

## Output Format
Print the number of trees over the modulo mod.

## Examples
```input
5 2 433416647
```
```output
1
```
-----
```input
10 3 409693891
```
```output
2
```
-----
```input
65 4 177545087
```
```output
910726
```

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
A group of n friends enjoys playing popular video game Toda 2. There is a rating system describing skill level of each player, initially the rating of the i-th friend is ri.

The friends decided to take part in the championship as a team. But they should have equal ratings to be allowed to compose a single team consisting of all n friends. So the friends are faced with the problem: how to make all their ratings equal.

One way to change ratings is to willingly lose in some matches. Friends can form a party consisting of two to five (but not more than n) friends and play a match in the game. When the party loses, the rating of each of its members decreases by 1. A rating can't become negative, so ri = 0 doesn't change after losing.

The friends can take part in multiple matches, each time making a party from any subset of friends (but remember about constraints on party size: from 2 to 5 members).

The friends want to make their ratings equal but as high as possible.

Help the friends develop a strategy of losing the matches so that all their ratings become equal and the resulting rating is maximum possible.

## Input Format
The first line contains a single integer n (2 ≤ n ≤ 100) — the number of friends.

The second line contains n non-negative integers r1, r2, ..., rn (0 ≤ ri ≤ 100), where ri is the initial rating of the i-th friend.

## Output Format
In the first line, print a single integer R — the final rating of each of the friends.

In the second line, print integer t — the number of matches the friends have to play. Each of the following t lines should contain n characters '0' or '1', where the j-th character of the i-th line is equal to:

- '0', if friend j should not play in match i,
- '1', if friend j should play in match i.

Each line should contain between two and five characters '1', inclusive.

The value t should not exceed 104, it is guaranteed that such solution exists.

Remember that you shouldn't minimize the value t, but you should maximize R. If there are multiple solutions, print any of them.

## Examples
```input
5
4 5 1 7 4
```
```output
1
8
01010
00011
01010
10010
00011
11000
00011
11000
```
-----
```input
2
1 2
```
```output
0
2
11
11
```
-----
```input
3
1 1 1
```
```output
1
0
```

Now solve the problem and return the code.