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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A TV show called "Guess a number!" is gathering popularity. The whole Berland, the old and the young, are watching the show.

The rules are simple. The host thinks of an integer y and the participants guess it by asking questions to the host. There are four types of acceptable questions:

- Is it true that y is strictly larger than number x?
- Is it true that y is strictly smaller than number x?
- Is it true that y is larger than or equal to number x?
- Is it true that y is smaller than or equal to number x?

On each question the host answers truthfully, "yes" or "no".

Given the sequence of questions and answers, find any integer value of y that meets the criteria of all answers. If there isn't such value, print "Impossible".

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 10000) — the number of questions (and answers). Next n lines each contain one question and one answer to it. The format of each line is like that: "sign x answer", where the sign is:

- ">" (for the first type queries),
- "<" (for the second type queries),
- ">=" (for the third type queries),
- "<=" (for the fourth type queries).

All values of x are integer and meet the inequation  - 109 ≤ x ≤ 109. The answer is an English letter "Y" (for "yes") or "N" (for "no").

Consequtive elements in lines are separated by a single space.

## Output Format
Print any of such integers y, that the answers to all the queries are correct. The printed number y must meet the inequation  - 2·109 ≤ y ≤ 2·109. If there are many answers, print any of them. If such value doesn't exist, print word "Impossible" (without the quotes).

## Examples
```input
4
>= 1 Y
< 3 N
<= -3 N
> 55 N
```
```output
17
```
-----
```input
2
> 100 Y
< -100 Y
```
```output
Impossible
```

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarpus develops an interesting theory about the interrelation of arithmetic progressions with just everything in the world. His current idea is that the population of the capital of Berland changes over time like an arithmetic progression. Well, or like multiple arithmetic progressions.

Polycarpus believes that if he writes out the population of the capital for several consecutive years in the sequence a1, a2, ..., an, then it is convenient to consider the array as several arithmetic progressions, written one after the other. For example, sequence (8, 6, 4, 2, 1, 4, 7, 10, 2) can be considered as a sequence of three arithmetic progressions (8, 6, 4, 2), (1, 4, 7, 10) and (2), which are written one after another.

Unfortunately, Polycarpus may not have all the data for the n consecutive years (a census of the population doesn't occur every year, after all). For this reason, some values of ai ​​may be unknown. Such values are represented by number -1.

For a given sequence a = (a1, a2, ..., an), which consists of positive integers and values ​​-1, find the minimum number of arithmetic progressions Polycarpus needs to get a. To get a, the progressions need to be written down one after the other. Values ​​-1 may correspond to an arbitrary positive integer and the values ai > 0 must be equal to the corresponding elements of sought consecutive record of the progressions.

Let us remind you that a finite sequence c is called an arithmetic progression if the difference ci + 1 - ci of any two consecutive elements in it is constant. By definition, any sequence of length 1 is an arithmetic progression.

## Input Format
The first line of the input contains integer n (1 ≤ n ≤ 2·105) — the number of elements in the sequence. The second line contains integer values a1, a2, ..., an separated by a space (1 ≤ ai ≤ 109 or ai =  - 1).

## Output Format
Print the minimum number of arithmetic progressions that you need to write one after another to get sequence a. The positions marked as -1 in a can be represented by any positive integers.

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

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Good old Berland has n cities and m roads. Each road connects a pair of distinct cities and is bidirectional. Between any pair of cities, there is at most one road. For each road, we know its length.

We also know that the President will soon ride along the Berland roads from city s to city t. Naturally, he will choose one of the shortest paths from s to t, but nobody can say for sure which path he will choose.

The Minister for Transport is really afraid that the President might get upset by the state of the roads in the country. That is the reason he is planning to repair the roads in the possible President's path.

Making the budget for such an event is not an easy task. For all possible distinct pairs s, t (s < t) find the number of roads that lie on at least one shortest path from s to t.

## Input Format
The first line of the input contains integers n, m (2 ≤ n ≤ 500, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and roads, correspondingly. Then m lines follow, containing the road descriptions, one description per line. Each description contains three integers xi, yi, li (1 ≤ xi, yi ≤ n, xi ≠ yi, 1 ≤ li ≤ 106), where xi, yi are the numbers of the cities connected by the i-th road and li is its length.

## Output Format
Print the sequence of $$n(n-1)/2$$ integers c12, c13, ..., c1n, c23, c24, ..., c2n, ..., cn - 1, n, where cst is the number of roads that can lie on the shortest path from s to t. Print the elements of sequence c in the described order. If the pair of cities s and t don't have a path between them, then cst = 0.

## Examples
```input
5 6
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
4 5 4
```
```output
1 4 1 2 1 5 6 1 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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The police department of your city has just started its journey. Initially, they don’t have any manpower. So, they started hiring new recruits in groups.

Meanwhile, crimes keeps occurring within the city. One member of the police force can investigate only one crime during his/her lifetime.

If there is no police officer free (isn't busy with crime) during the occurrence of a crime, it will go untreated.

Given the chronological order of crime occurrences and recruit hirings, find the number of crimes which will go untreated.

## Input Format
The first line of input will contain an integer n (1 ≤ n ≤ 105), the number of events. The next line will contain n space-separated integers.

If the integer is -1 then it means a crime has occurred. Otherwise, the integer will be positive, the number of officers recruited together at that time. No more than 10 officers will be recruited at a time.

## Output Format
Print a single integer, the number of crimes which will go untreated.

## Examples
```input
3
-1 -1 1
```
```output
2
```
-----
```input
8
1 -1 1 -1 -1 1 1 1
```
```output
1
```
-----
```input
11
-1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1
```
```output
8
```

## Note
Lets consider the second example:

1. Firstly one person is hired.
2. Then crime appears, the last hired person will investigate this crime.
3. One more person is hired.
4. One more crime appears, the last hired person will investigate this crime.
5. Crime appears. There is no free policeman at the time, so this crime will go untreated.
6. One more person is hired.
7. One more person is hired.
8. One more person is hired.

The answer is one, as one crime (on step 5) will go untreated.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
Police headquarter is monitoring signal on different frequency levels. They have got two suspiciously encoded strings s1 and s2 from two different frequencies as signals. They are suspecting that these two strings are from two different criminals and they are planning to do some evil task.

Now they are trying to find a common substring of minimum length between these two strings. The substring must occur only once in the first string, and also it must occur only once in the second string.

Given two strings s1 and s2 consist of lowercase Latin letters, find the smallest (by length) common substring p of both s1 and s2, where p is a unique substring in s1 and also in s2. See notes for formal definition of substring and uniqueness.

## Input Format
The first line of input contains s1 and the second line contains s2 (1 ≤ |s1|, |s2| ≤ 5000). Both strings consist of lowercase Latin letters.

## Output Format
Print the length of the smallest common unique substring of s1 and s2. If there are no common unique substrings of s1 and s2 print -1.

## Examples
```input
apple
pepperoni
```
```output
2
```
-----
```input
lover
driver
```
```output
1
```
-----
```input
bidhan
roy
```
```output
-1
```
-----
```input
testsetses
teeptes
```
```output
3
```

## Note
Imagine we have string a = a1a2a3...a|a|, where |a| is the length of string a, and ai is the ith letter of the string.

We will call string alal + 1al + 2...ar (1 ≤ l ≤ r ≤ |a|) the substring [l, r] of the string a.

The substring [l, r] is unique in a if and only if there is no pair l1, r1 such that l1 ≠ l and the substring [l1, r1] is equal to the substring [l, r] in a.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Imagine that your city is an infinite 2D plane with Cartesian coordinate system. The only crime-affected road of your city is the x-axis. Currently, there are n criminals along the road. No police station has been built on this road yet, so the mayor wants to build one.

As you are going to be in charge of this new police station, the mayor has asked you to choose a suitable position (some integer point) for building it. You should choose the best position for the police station, so that you could minimize the total time of your criminal catching mission. Your mission of catching the criminals will operate only from this station.

The new station will have only one patrol car. You will go to the criminals by this car, carry them on the car, bring them back to the police station and put them in prison. The patrol car can carry at most m criminals at a time. Note that, the criminals don't know about your mission. So, they will stay where they are instead of running away.

Your task is to find the position for the police station, so that total distance you need to cover to catch all the criminals will be minimum possible. Note that, you also can built the police station on the positions where one or more criminals already exist. In such a case all these criminals are arrested instantly.

## Input Format
The first line of the input will have two integers n (1 ≤ n ≤ 106) and m (1 ≤ m ≤ 106) separated by spaces. The next line will contain n integers separated by spaces. The ith integer is the position of the ith criminal on the x-axis. Absolute value of positions will not exceed 109. If a criminal has position x, he/she is located in the point (x, 0) of the plane.

The positions of the criminals will be given in non-decreasing order. Note, that there can be more than one criminal standing at some point of the plane.

Note: since the size of the input/output could be very large, don't use slow input/output techniques in your language. For example, do not use input/output streams (cin, cout) in C++.

## Output Format
Print a single integer, that means the minimum possible distance you need to cover to catch all the criminals.

## Examples
```input
3 6
1 2 3
```
```output
4
```
-----
```input
5 5
-7 -6 -3 -1 1
```
```output
16
```
-----
```input
1 369
0
```
```output
0
```
-----
```input
11 2
-375 -108 1336 1453 1598 1892 2804 3732 4291 4588 4822
```
```output
18716
```

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Valera loves his garden, where n fruit trees grow.

This year he will enjoy a great harvest! On the i-th tree bi fruit grow, they will ripen on a day number ai. Unfortunately, the fruit on the tree get withered, so they can only be collected on day ai and day ai + 1 (all fruits that are not collected in these two days, become unfit to eat).

Valera is not very fast, but there are some positive points. Valera is ready to work every day. In one day, Valera can collect no more than v fruits. The fruits may be either from the same tree, or from different ones. What is the maximum amount of fruit Valera can collect for all time, if he operates optimally well?

## Input Format
The first line contains two space-separated integers n and v (1 ≤ n, v ≤ 3000) — the number of fruit trees in the garden and the number of fruits that Valera can collect in a day.

Next n lines contain the description of trees in the garden. The i-th line contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ 3000) — the day the fruits ripen on the i-th tree and the number of fruits on the i-th tree.

## Output Format
Print a single integer — the maximum number of fruit that Valera can collect.

## Examples
```input
2 3
1 5
2 3
```
```output
8
```
-----
```input
5 10
3 20
2 20
1 20
4 20
5 20
```
```output
60
```

## Note
In the first sample, in order to obtain the optimal answer, you should act as follows.

- On the first day collect 3 fruits from the 1-st tree.
- On the second day collect 1 fruit from the 2-nd tree and 2 fruits from the 1-st tree.
- On the third day collect the remaining fruits from the 2-nd tree.

In the second sample, you can only collect 60 fruits, the remaining fruit will simply wither.

Now solve the problem and return the code.