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
Vasya works as a watchman in the gallery. Unfortunately, one of the most expensive paintings was stolen while he was on duty. He doesn't want to be fired, so he has to quickly restore the painting. He remembers some facts about it.

- The painting is a square 3 × 3, each cell contains a single integer from 1 to n, and different cells may contain either different or equal integers.
- The sum of integers in each of four squares 2 × 2 is equal to the sum of integers in the top left square 2 × 2.
- Four elements a, b, c and d are known and are located as shown on the picture below.

Help Vasya find out the number of distinct squares the satisfy all the conditions above. Note, that this number may be equal to 0, meaning Vasya remembers something wrong.

Two squares are considered to be different, if there exists a cell that contains two different integers in different squares.

## Input Format
The first line of the input contains five integers n, a, b, c and d (1 ≤ n ≤ 100 000, 1 ≤ a, b, c, d ≤ n) — maximum possible value of an integer in the cell and four integers that Vasya remembers.

## Output Format
Print one integer — the number of distinct valid squares.

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

## Note
Below are all the possible paintings for the first sample.

In the second sample, only paintings displayed below satisfy all the rules.

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

# Problem
During the programming classes Vasya was assigned a difficult problem. However, he doesn't know how to code and was unable to find the solution in the Internet, so he asks you to help.

You are given a sequence $$$a$$$, consisting of $$$n$$$ distinct integers, that is used to construct the binary search tree. Below is the formal description of the construction process.

1. First element $$$a_1$$$ becomes the root of the tree.
2. Elements $$$a_2, a_3, \ldots, a_n$$$ are added one by one. To add element $$$a_i$$$ one needs to traverse the tree starting from the root and using the following rules:   The pointer to the current node is set to the root.  If $$$a_i$$$ is greater than the value in the current node, then its right child becomes the current node. Otherwise, the left child of the current node becomes the new current node.  If at some point there is no required child, the new node is created, it is assigned value $$$a_i$$$ and becomes the corresponding child of the current node.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — the length of the sequence $$$a$$$.

The second line contains $$$n$$$ distinct integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — the sequence $$$a$$$ itself.

## Output Format
Output $$$n - 1$$$ integers. For all $$$i > 1$$$ print the value written in the node that is the parent of the node with value $$$a_i$$$ in it.

## Examples
```input
3
1 2 3
```
```output
1 2
```
-----
```input
5
4 2 3 1 6
```
```output
4 2 2 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 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: 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 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: 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 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
Kolya is going to make fresh orange juice. He has n oranges of sizes a1, a2, ..., an. Kolya will put them in the juicer in the fixed order, starting with orange of size a1, then orange of size a2 and so on. To be put in the juicer the orange must have size not exceeding b, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than d. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

## Input Format
The first line of the input contains three integers n, b and d (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value d, which determines the condition when the waste section should be emptied.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000 000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

## Output Format
Print one integer — the number of times Kolya will have to empty the waste section.

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

## Note
In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.

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

# Problem
ZS the Coder and Chris the Baboon arrived at the entrance of Udayland. There is a n × n magic grid on the entrance which is filled with integers. Chris noticed that exactly one of the cells in the grid is empty, and to enter Udayland, they need to fill a positive integer into the empty cell.

Chris tried filling in random numbers but it didn't work. ZS the Coder realizes that they need to fill in a positive integer such that the numbers in the grid form a magic square. This means that he has to fill in a positive integer so that the sum of the numbers in each row of the grid ($$\sum_{r,i}a_{r,i}$$), each column of the grid ($$\sum_{i,c}a_{i,c}$$), and the two long diagonals of the grid (the main diagonal — $$\sum_{i}a_{i,i}$$ and the secondary diagonal — $$\sum_{i}a_{i,n-i+1}$$) are equal.

Chris doesn't know what number to fill in. Can you help Chris find the correct positive integer to fill in or determine that it is impossible?

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 500) — the number of rows and columns of the magic grid.

n lines follow, each of them contains n integers. The j-th number in the i-th of them denotes ai, j (1 ≤ ai, j ≤ 109 or ai, j = 0), the number in the i-th row and j-th column of the magic grid. If the corresponding cell is empty, ai, j will be equal to 0. Otherwise, ai, j is positive.

It is guaranteed that there is exactly one pair of integers i, j (1 ≤ i, j ≤ n) such that ai, j = 0.

## Output Format
Output a single integer, the positive integer x (1 ≤ x ≤ 1018) that should be filled in the empty cell so that the whole grid becomes a magic square. If such positive integer x does not exist, output  - 1 instead.

If there are multiple solutions, you may print any of them.

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

## Note
In the first sample case, we can fill in 9 into the empty cell to make the resulting grid a magic square. Indeed,

The sum of numbers in each row is:

4 + 9 + 2 = 3 + 5 + 7 = 8 + 1 + 6 = 15.

The sum of numbers in each column is:

4 + 3 + 8 = 9 + 5 + 1 = 2 + 7 + 6 = 15.

The sum of numbers in the two diagonals is:

4 + 5 + 6 = 2 + 5 + 8 = 15.

In the third sample case, it is impossible to fill a number in the empty square such that the resulting grid is a magic square.

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

# Problem
ZS the Coder has recently found an interesting concept called the Birthday Paradox. It states that given a random set of 23 people, there is around 50% chance that some two of them share the same birthday. ZS the Coder finds this very interesting, and decides to test this with the inhabitants of Udayland.

In Udayland, there are 2n days in a year. ZS the Coder wants to interview k people from Udayland, each of them has birthday in one of 2n days (each day with equal probability). He is interested in the probability of at least two of them have the birthday at the same day.

ZS the Coder knows that the answer can be written as an irreducible fraction $$\frac{\overline{A}}{\overline{B}}$$. He wants to find the values of A and B (he does not like to deal with floating point numbers). Can you help him?

## Input Format
The first and only line of the input contains two integers n and k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 1018), meaning that there are 2n days in a year and that ZS the Coder wants to interview exactly k people.

## Output Format
If the probability of at least two k people having the same birthday in 2n days long year equals $$\frac{\overline{A}}{\overline{B}}$$ (A ≥ 0, B ≥ 1, $$\gcd(A,B)=1$$), print the A and B in a single line.

Since these numbers may be too large, print them modulo 106 + 3. Note that A and B must be coprime before their remainders modulo 106 + 3 are taken.

## Examples
```input
3 2
```
```output
1 8
```
-----
```input
1 3
```
```output
1 1
```
-----
```input
4 3
```
```output
23 128
```

## Note
In the first sample case, there are 23 = 8 days in Udayland. The probability that 2 people have the same birthday among 2 people is clearly $${ \frac { 1 } { 8 } }$$, so A = 1, B = 8.

In the second sample case, there are only 21 = 2 days in Udayland, but there are 3 people, so it is guaranteed that two of them have the same birthday. Thus, the probability is 1 and A = B = 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: 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 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Little girl Masha likes winter sports, today she's planning to take part in slalom skiing.

The track is represented as a grid composed of n × m squares. There are rectangular obstacles at the track, composed of grid squares. Masha must get from the square (1, 1) to the square (n, m). She can move from a square to adjacent square: either to the right, or upwards. If the square is occupied by an obstacle, it is not allowed to move to that square.

One can see that each obstacle can actually be passed in two ways: either it is to the right of Masha's path, or to the left. Masha likes to try all ways to do things, so she would like to know how many ways are there to pass the track. Two ways are considered different if there is an obstacle such that it is to the right of the path in one way, and to the left of the path in the other way.

Help Masha to find the number of ways to pass the track. The number of ways can be quite big, so Masha would like to know it modulo 109 + 7.

The pictures below show different ways to pass the track in sample tests.

## Input Format
The first line of input data contains three positive integers: n, m and k (3 ≤ n, m ≤ 106, 0 ≤ k ≤ 105) — the size of the track and the number of obstacles.

The following k lines contain four positive integers each: x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) — coordinates of bottom left, and top right squares of the obstacle.

It is guaranteed that there are no obstacles at squares (1, 1) and (n, m), and no obstacles overlap (but some of them may touch).

## Output Format
Output one integer — the number of ways to pass the track modulo 109 + 7.

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

# Problem
Misha has an array of integers of length n. He wants to choose k different continuous subarrays, so that each element of the array belongs to at least one of the chosen subarrays.

Misha wants to choose the subarrays in such a way that if he calculated the sum of elements for each subarray, and then add up all these sums, the resulting value was maximum possible.

## Input Format
The first line of input contains two integers: n, k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ n·(n + 1) / 2) — the number of elements in the array and the number of different subarrays that must be chosen.

The second line contains n integers ai ( - 50 000 ≤ ai ≤ 50 000) — the elements of the array.

## Output Format
Output one integer — the maximum possible value Misha can get by choosing k different subarrays.

## Examples
```input
5 4
6 -4 -10 -4 7
```
```output
11
```

Now solve the problem and return the code.