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

# Problem
As it has been found out recently, all the Berland's current economical state can be described using a simple table n × m in size. n — the number of days in each Berland month, m — the number of months. Thus, a table cell corresponds to a day and a month of the Berland's year. Each cell will contain either 1, or -1, which means the state's gains in a particular month, on a particular day. 1 corresponds to profits, -1 corresponds to losses. It turned out important for successful development to analyze the data on the state of the economy of the previous year, however when the treasurers referred to the archives to retrieve the data, it turned out that the table had been substantially damaged. In some table cells the number values had faded and were impossible to be deciphered. It is known that the number of cells in which the data had been preserved is strictly less than max(n, m). However, there is additional information — the product of the numbers in each line and column equaled -1. Your task is to find out how many different tables may conform to the preserved data. As the answer to the task can be quite large, you have to find it modulo p.

## Input Format
The first line contains integers n and m (1 ≤ n, m ≤ 1000). The second line contains the integer k (0 ≤ k < max(n, m)) — the number of cells in which the data had been preserved. The next k lines contain the data on the state of the table in the preserved cells. Each line is of the form "a b c", where a (1 ≤ a ≤ n) — the number of the table row, b (1 ≤ b ≤ m) — the number of the column, c — the value containing in the cell (1 or -1). They are numbered starting from 1. It is guaranteed that no two lines with same a and b values exist. The last line contains an integer p (2 ≤ p ≤ 109 + 7).

## Output Format
Print the number of different tables that could conform to the preserved data modulo p.

## Examples
```input
2 2
0
100
```
```output
2
```
-----
```input
2 2
1
1 1 -1
100
```
```output
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
Not so long ago company R2 bought company R1 and consequently, all its developments in the field of multicore processors. Now the R2 laboratory is testing one of the R1 processors.

The testing goes in n steps, at each step the processor gets some instructions, and then its temperature is measured. The head engineer in R2 is keeping a report record on the work of the processor: he writes down the minimum and the maximum measured temperature in his notebook. His assistant had to write down all temperatures into his notebook, but (for unknown reasons) he recorded only m.

The next day, the engineer's assistant filed in a report with all the m temperatures. However, the chief engineer doubts that the assistant wrote down everything correctly (naturally, the chief engineer doesn't doubt his notes). So he asked you to help him. Given numbers n, m, min, max and the list of m temperatures determine whether you can upgrade the set of m temperatures to the set of n temperatures (that is add n - m temperatures), so that the minimum temperature was min and the maximum one was max.

## Input Format
The first line contains four integers n, m, min, max (1 ≤ m < n ≤ 100; 1 ≤ min < max ≤ 100). The second line contains m space-separated integers ti (1 ≤ ti ≤ 100) — the temperatures reported by the assistant.

Note, that the reported temperatures, and the temperatures you want to add can contain equal temperatures.

## Output Format
If the data is consistent, print 'Correct' (without the quotes). Otherwise, print 'Incorrect' (without the quotes).

## Examples
```input
2 1 1 2
1
```
```output
Correct
```
-----
```input
3 1 1 3
2
```
```output
Correct
```
-----
```input
2 1 1 3
2
```
```output
Incorrect
```

## Note
In the first test sample one of the possible initial configurations of temperatures is [1, 2].

In the second test sample one of the possible initial configurations of temperatures is [2, 1, 3].

In the third test sample it is impossible to add one temperature to obtain the minimum equal to 1 and the maximum equal to 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The R2 company has n employees working for it. The work involves constant exchange of ideas, sharing the stories of success and upcoming challenging. For that, R2 uses a famous instant messaging program Spyke.

R2 has m Spyke chats just to discuss all sorts of issues. In each chat, some group of employees exchanges messages daily. An employee can simultaneously talk in multiple chats. If some employee is in the k-th chat, he can write messages to this chat and receive notifications about messages from this chat. If an employee writes a message in the chat, all other participants of the chat receive a message notification.

The R2 company is conducting an audit. Now the specialists study effective communication between the employees. For this purpose, they have a chat log and the description of chat structure. You, as one of audit specialists, are commissioned to write a program that will use this data to determine the total number of message notifications received by each employee.

## Input Format
The first line contains three space-separated integers n, m and k (2 ≤ n ≤ 2·104; 1 ≤ m ≤ 10; 1 ≤ k ≤ 2·105) — the number of the employees, the number of chats and the number of events in the log, correspondingly.

Next n lines contain matrix a of size n × m, consisting of numbers zero and one. The element of this matrix, recorded in the j-th column of the i-th line, (let's denote it as aij) equals 1, if the i-th employee is the participant of the j-th chat, otherwise the element equals 0. Assume that the employees are numbered from 1 to n and the chats are numbered from 1 to m.

Next k lines contain the description of the log events. The i-th line contains two space-separated integers xi and yi (1 ≤ xi ≤ n; 1 ≤ yi ≤ m) which mean that the employee number xi sent one message to chat number yi. It is guaranteed that employee number xi is a participant of chat yi. It is guaranteed that each chat contains at least two employees.

## Output Format
Print in the single line n space-separated integers, where the i-th integer shows the number of message notifications the i-th employee receives.

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

# Problem
'Jeopardy!' is an intellectual game where players answer questions and earn points. Company Q conducts a simplified 'Jeopardy!' tournament among the best IT companies. By a lucky coincidence, the old rivals made it to the finals: company R1 and company R2.

The finals will have n questions, m of them are auction questions and n - m of them are regular questions. Each question has a price. The price of the i-th question is ai points. During the game the players chose the questions. At that, if the question is an auction, then the player who chose it can change the price if the number of his current points is strictly larger than the price of the question. The new price of the question cannot be less than the original price and cannot be greater than the current number of points of the player who chose the question. The correct answer brings the player the points equal to the price of the question. The wrong answer to the question reduces the number of the player's points by the value of the question price.

The game will go as follows. First, the R2 company selects a question, then the questions are chosen by the one who answered the previous question correctly. If no one answered the question, then the person who chose last chooses again.

All R2 employees support their team. They want to calculate what maximum possible number of points the R2 team can get if luck is on their side during the whole game (they will always be the first to correctly answer questions). Perhaps you are not going to be surprised, but this problem was again entrusted for you to solve.

## Input Format
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100; m ≤ min(n, 30)) — the total number of questions and the number of auction questions, correspondingly. The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 107) — the prices of the questions. The third line contains m distinct integers bi (1 ≤ bi ≤ n) — the numbers of auction questions. Assume that the questions are numbered from 1 to n.

## Output Format
In the single line, print the answer to the problem — the maximum points the R2 company can get if it plays optimally well. It is guaranteed that the answer fits into the integer 64-bit signed type.

## Examples
```input
4 1
1 3 7 5
3
```
```output
18
```
-----
```input
3 2
10 3 8
2 3
```
```output
40
```
-----
```input
2 2
100 200
1 2
```
```output
400
```

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
The finalists of the "Russian Code Cup" competition in 2214 will be the participants who win in one of the elimination rounds.

The elimination rounds are divided into main and additional. Each of the main elimination rounds consists of c problems, the winners of the round are the first n people in the rating list. Each of the additional elimination rounds consists of d problems. The winner of the additional round is one person. Besides, k winners of the past finals are invited to the finals without elimination.

As a result of all elimination rounds at least n·m people should go to the finals. You need to organize elimination rounds in such a way, that at least n·m people go to the finals, and the total amount of used problems in all rounds is as small as possible.

## Input Format
The first line contains two integers c and d (1 ≤ c, d ≤ 100) — the number of problems in the main and additional rounds, correspondingly. The second line contains two integers n and m (1 ≤ n, m ≤ 100). Finally, the third line contains an integer k (1 ≤ k ≤ 100) — the number of the pre-chosen winners.

## Output Format
In the first line, print a single integer — the minimum number of problems the jury needs to prepare.

## Examples
```input
1 10
7 2
1
```
```output
2
```
-----
```input
2 2
2 1
2
```
```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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
During the "Russian Code Cup" programming competition, the testing system stores all sent solutions for each participant. We know that many participants use random numbers in their programs and are often sent several solutions with the same source code to check.

Each participant is identified by some unique positive integer k, and each sent solution A is characterized by two numbers: x — the number of different solutions that are sent before the first solution identical to A, and k — the number of the participant, who is the author of the solution. Consequently, all identical solutions have the same x.

It is known that the data in the testing system are stored in the chronological order, that is, if the testing system has a solution with number x (x > 0) of the participant with number k, then the testing system has a solution with number x - 1 of the same participant stored somewhere before.

During the competition the checking system crashed, but then the data of the submissions of all participants have been restored. Now the jury wants to verify that the recovered data is in chronological order. Help the jury to do so.

## Input Format
The first line of the input contains an integer n (1 ≤ n ≤ 105) — the number of solutions. Each of the following n lines contains two integers separated by space x and k (0 ≤ x ≤ 105; 1 ≤ k ≤ 105) — the number of previous unique solutions and the identifier of the participant.

## Output Format
A single line of the output should contain «YES» if the data is in chronological order, and «NO» otherwise.

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

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
Sereja showed an interesting game to his friends. The game goes like that. Initially, there is a table with an empty cup and n water mugs on it. Then all players take turns to move. During a move, a player takes a non-empty mug of water and pours all water from it into the cup. If the cup overfills, then we assume that this player lost.

As soon as Sereja's friends heard of the game, they wanted to play it. Sereja, on the other hand, wanted to find out whether his friends can play the game in such a way that there are no losers. You are given the volumes of all mugs and the cup. Also, you know that Sereja has (n - 1) friends. Determine if Sereja's friends can play the game so that nobody loses.

## Input Format
The first line contains integers n and s (2 ≤ n ≤ 100; 1 ≤ s ≤ 1000) — the number of mugs and the volume of the cup. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10). Number ai means the volume of the i-th mug.

## Output Format
In a single line, print "YES" (without the quotes) if his friends can play in the described manner, and "NO" (without the quotes) otherwise.

## Examples
```input
3 4
1 1 1
```
```output
YES
```
-----
```input
3 4
3 1 3
```
```output
YES
```
-----
```input
3 4
4 4 4
```
```output
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let's assume that we are given a matrix b of size x × y, let's determine the operation of mirroring matrix b. The mirroring of matrix b is a 2x × y matrix c which has the following properties:

- the upper half of matrix c (rows with numbers from 1 to x) exactly matches b;
- the lower half of matrix c (rows with numbers from x + 1 to 2x) is symmetric to the upper one; the symmetry line is the line that separates two halves (the line that goes in the middle, between rows x and x + 1).

Sereja has an n × m matrix a. He wants to find such matrix b, that it can be transformed into matrix a, if we'll perform on it several (possibly zero) mirrorings. What minimum number of rows can such matrix contain?

## Input Format
The first line contains two integers, n and m (1 ≤ n, m ≤ 100). Each of the next n lines contains m integers — the elements of matrix a. The i-th line contains integers ai1, ai2, ..., aim (0 ≤ aij ≤ 1) — the i-th row of the matrix a.

## Output Format
In the single line, print the answer to the problem — the minimum number of rows of matrix b.

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

## Note
In the first test sample the answer is a 2 × 3 matrix b:

If we perform a mirroring operation with this matrix, we get the matrix a that is given in the input:

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
Polycarpus adores TV series. Right now he is ready to finish watching a season of a popular sitcom "Graph Theory". In total, the season has n episodes, numbered with integers from 1 to n.

Polycarpus watches episodes not one by one but in a random order. He has already watched all the episodes except for one. Which episode has Polycaprus forgotten to watch?

## Input Format
The first line of the input contains integer n (2 ≤ n ≤ 100000) — the number of episodes in a season. Assume that the episodes are numbered by integers from 1 to n.

The second line contains n - 1 integer a1, a2, ..., an (1 ≤ ai ≤ n) — the numbers of episodes that Polycarpus has watched. All values of ai are distinct.

## Output Format
Print the number of the episode that Polycarpus hasn't watched.

## Examples
```input
10
3 8 10 1 7 9 6 5 2
```
```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: 0.5 seconds
Memory limit: 256.0 MB

# Problem
Petya has k matches, placed in n matchboxes lying in a line from left to right. We know that k is divisible by n. Petya wants all boxes to have the same number of matches inside. For that, he can move a match from its box to the adjacent one in one move. How many such moves does he need to achieve the desired configuration?

## Input Format
The first line contains integer n (1 ≤ n ≤ 50000). The second line contains n non-negative numbers that do not exceed 109, the i-th written number is the number of matches in the i-th matchbox. It is guaranteed that the total number of matches is divisible by n.

## Output Format
Print the total minimum number of moves.

## Examples
```input
6
1 6 2 5 3 7
```
```output
12
```

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
Today Vasya visited a widely known site and learned that the continuation of his favourite game Codecraft II will appear after exactly k months. He looked at the calendar and learned that at the moment is the month number s. Vasya immediately got interested in what month Codecraft III will appear. Help him understand that.

All the twelve months in Vasya's calendar are named using their usual English names: January, February, March, April, May, June, July, August, September, October, November, December.

## Input Format
The first input line contains the name of the current month. It is guaranteed that it is a proper English name of one of twelve months. The first letter is uppercase, the rest are lowercase. The second line contains integer k (0 ≤ k ≤ 100) — the number of months left till the appearance of Codecraft III.

## Output Format
Print starting from an uppercase letter the name of the month in which the continuation of Codeforces II will appear. The printed name must be contained in the list January, February, March, April, May, June, July, August, September, October, November, December.

## Examples
```input
November
3
```
```output
February
```
-----
```input
May
24
```
```output
May
```

Now solve the problem and return the code.