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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
The only difference between easy and hard versions is the constraint on $$$k$$$.

Gildong loves observing animals, so he bought two cameras to take videos of wild animals in a forest. The color of one camera is red, and the other one's color is blue.

Gildong is going to take videos for $$$n$$$ days, starting from day $$$1$$$ to day $$$n$$$. The forest can be divided into $$$m$$$ areas, numbered from $$$1$$$ to $$$m$$$. He'll use the cameras in the following way:

- On every odd day ($$$1$$$-st, $$$3$$$-rd, $$$5$$$-th, ...), bring the red camera to the forest and record a video for $$$2$$$ days.
- On every even day ($$$2$$$-nd, $$$4$$$-th, $$$6$$$-th, ...), bring the blue camera to the forest and record a video for $$$2$$$ days.
- If he starts recording on the $$$n$$$-th day with one of the cameras, the camera records for only one day.

Each camera can observe $$$k$$$ consecutive areas of the forest. For example, if $$$m=5$$$ and $$$k=3$$$, he can put a camera to observe one of these three ranges of areas for two days: $$$[1,3]$$$, $$$[2,4]$$$, and $$$[3,5]$$$.

Gildong got information about how many animals will be seen in each area on each day. Since he would like to observe as many animals as possible, he wants you to find the best way to place the two cameras for $$$n$$$ days. Note that if the two cameras are observing the same area on the same day, the animals observed in that area are counted only once.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le m \le 2 \cdot 10^4$$$, $$$1 \le k \le m$$$) – the number of days Gildong is going to record, the number of areas of the forest, and the range of the cameras, respectively.

Next $$$n$$$ lines contain $$$m$$$ integers each. The $$$j$$$-th integer in the $$$i+1$$$-st line is the number of animals that can be seen on the $$$i$$$-th day in the $$$j$$$-th area. Each number of animals is between $$$0$$$ and $$$1000$$$, inclusive.

## Output Format
Print one integer – the maximum number of animals that can be observed.

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

## Note
The optimal way to observe animals in the four examples are as follows:

Example 1:

Example 2:

Example 3:

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

# Problem
wHAT DO WE NEED cAPS LOCK FOR?

Caps lock is a computer keyboard key. Pressing it sets an input mode in which typed letters are capital by default. If it is pressed by accident, it leads to accidents like the one we had in the first passage.

Let's consider that a word has been typed with the Caps lock key accidentally switched on, if:

- either it only contains uppercase letters;
- or all letters except for the first one are uppercase.

In this case we should automatically change the case of all letters. For example, the case of the letters that form words "hELLO", "HTTP", "z" should be changed.

Write a program that applies the rule mentioned above. If the rule cannot be applied, the program should leave the word unchanged.

## Input Format
The first line of the input data contains a word consisting of uppercase and lowercase Latin letters. The word's length is from 1 to 100 characters, inclusive.

## Output Format
Print the result of the given word's processing.

## Examples
```input
cAPS
```
```output
Caps
```
-----
```input
Lock
```
```output
Lock
```

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
Everybody knows that opposites attract. That is the key principle of the "Perfect Matching" dating agency. The "Perfect Matching" matchmakers have classified each registered customer by his interests and assigned to the i-th client number ti ( - 10 ≤ ti ≤ 10). Of course, one number can be assigned to any number of customers.

"Perfect Matching" wants to advertise its services and publish the number of opposite couples, that is, the couples who have opposite values of t. Each couple consists of exactly two clients. The customer can be included in a couple an arbitrary number of times. Help the agency and write the program that will find the sought number by the given sequence t1, t2, ..., tn. For example, if t = (1,  - 1, 1,  - 1), then any two elements ti and tj form a couple if i and j have different parity. Consequently, in this case the sought number equals 4.

Of course, a client can't form a couple with him/herself.

## Input Format
The first line of the input data contains an integer n (1 ≤ n ≤ 105) which represents the number of registered clients of the "Couple Matching". The second line contains a sequence of integers t1, t2, ..., tn ( - 10 ≤ ti ≤ 10), ti — is the parameter of the i-th customer that has been assigned to the customer by the result of the analysis of his interests.

## Output Format
Print the number of couples of customs with opposite t. The opposite number for x is number  - x (0 is opposite to itself). Couples that only differ in the clients' order are considered the same.

Note that the answer to the problem can be large enough, so you must use the 64-bit integer type for calculations. Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

## Examples
```input
5
-3 3 0 0 3
```
```output
3
```
-----
```input
3
0 0 0
```
```output
3
```

## Note
In the first sample the couples of opposite clients are: (1,2), (1,5) и (3,4).

In the second sample any couple of clients is opposite.

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 boys and m girls attending a theatre club. To set a play "The Big Bang Theory", they need to choose a group containing exactly t actors containing no less than 4 boys and no less than one girl. How many ways are there to choose a group? Of course, the variants that only differ in the composition of the troupe are considered different.

Perform all calculations in the 64-bit type: long long for С/С++, int64 for Delphi and long for Java.

## Input Format
The only line of the input data contains three integers n, m, t (4 ≤ n ≤ 30, 1 ≤ m ≤ 30, 5 ≤ t ≤ n + m).

## Output Format
Find the required number of ways.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

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

# Problem
A subway scheme, classic for all Berland cities is represented by a set of n stations connected by n passages, each of which connects exactly two stations and does not pass through any others. Besides, in the classic scheme one can get from any station to any other one along the passages. The passages can be used to move in both directions. Between each pair of stations there is no more than one passage.

Berland mathematicians have recently proved a theorem that states that any classic scheme has a ringroad. There can be only one ringroad. In other words, in any classic scheme one can find the only scheme consisting of stations (where any two neighbouring ones are linked by a passage) and this cycle doesn't contain any station more than once.

This invention had a powerful social impact as now the stations could be compared according to their distance from the ringroad. For example, a citizen could say "I live in three passages from the ringroad" and another one could reply "you loser, I live in one passage from the ringroad". The Internet soon got filled with applications that promised to count the distance from the station to the ringroad (send a text message to a short number...).

The Berland government decided to put an end to these disturbances and start to control the situation. You are requested to write a program that can determine the remoteness from the ringroad for each station by the city subway scheme.

## Input Format
The first line contains an integer n (3 ≤ n ≤ 3000), n is the number of stations (and trains at the same time) in the subway scheme. Then n lines contain descriptions of the trains, one per line. Each line contains a pair of integers xi, yi (1 ≤ xi, yi ≤ n) and represents the presence of a passage from station xi to station yi. The stations are numbered from 1 to n in an arbitrary order. It is guaranteed that xi ≠ yi and that no pair of stations contain more than one passage. The passages can be used to travel both ways. It is guaranteed that the given description represents a classic subway scheme.

## Output Format
Print n numbers. Separate the numbers by spaces, the i-th one should be equal to the distance of the i-th station from the ringroad. For the ringroad stations print number 0.

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

# Problem
A queen is the strongest chess piece. In modern chess the queen can move any number of squares in any horizontal, vertical or diagonal direction (considering that there're no other pieces on its way). The queen combines the options given to the rook and the bishop.

There are m queens on a square n × n chessboard. You know each queen's positions, the i-th queen is positioned in the square (ri, ci), where ri is the board row number (numbered from the top to the bottom from 1 to n), and ci is the board's column number (numbered from the left to the right from 1 to n). No two queens share the same position.

For each queen one can count w — the number of other queens that the given queen threatens (attacks). For a fixed attack direction only the first queen in this direction is under attack if there are many queens are on the ray of the attack. Obviously, for any queen w is between 0 and 8, inclusive.

Print the sequence t0, t1, ..., t8, where ti is the number of queens that threaten exactly i other queens, i.e. the number of queens that their w equals i.

## Input Format
The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 105), where n is the size of the board and m is the number of queens on the board. Then m following lines contain positions of the queens, one per line. Each line contains a pair of integers ri, ci (1 ≤ ri, ci ≤ n) — the queen's position. No two queens stand on the same square.

## Output Format
Print the required sequence t0, t1, ..., t8, separating the numbers with spaces.

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

# Problem
How many stars are there in the sky? A young programmer Polycarpus can't get this question out of his head! He took a photo of the starry sky using his digital camera and now he analyzes the resulting monochrome digital picture. The picture is represented by a rectangular matrix consisting of n lines each containing m characters. A character equals '1', if the corresponding photo pixel is white and '0', if it is black.

Polycarpus thinks that he has found a star on the photo if he finds a white pixel surrounded by four side-neighboring pixels that are also white:

1 111 1  a star on the photo

Polycarpus whats to cut out a rectangular area from the photo and give his mom as a present. This area should contain no less than k stars. The stars can intersect, have shared white pixels on the photo. The boy will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.

Now Polycarpus keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Help Polycarpus find this number.

## Input Format
The first line of the input data contains three integers n, m and k (1 ≤ n, m ≤ 500;1 ≤ k ≤ nm). Then follow n lines, containing the description of the given photo as a sequence of lines. Each line contains m characters '0' or '1'.

## Output Format
Print the required number of areas on the given photo.

## Examples
```input
4 6 2
111000
111100
011011
000111
```
```output
6
```
-----
```input
5 5 4
11111
11111
11111
11111
11111
```
```output
9
```

## Note
We'll number the rows and columns below starting from 1, the coordinates (p, q) will denote a cell in row p, column q.

In the first sample Polycarpus should cut out any area containing a rectangle whose opposite corners lie in cells (1, 1) and (3, 4). Only rectangles with opposite corners in (1, 1) and (x, y), where x ≥ 3 and y ≥ 4 fit the conditions.

In the second sample any rectangle whose each side is no less than four, will do. The possible rectangle sizes are 4 × 4, 4 × 5, 5 × 4 and 5 × 5. Such figures can be cut in 4 ways, 2 ways, 2 ways and 1 way correspondingly.

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use cin, cout streams or the %I64d specificator.

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
Dreamoon likes strings. Today he created a game about strings:

String $$$s_1, s_2, \ldots, s_n$$$ is beautiful if and only if for each $$$1 \le i < n, s_i \ne s_{i+1}$$$.

Initially, Dreamoon has a string $$$a$$$. In each step Dreamoon can choose a beautiful substring of $$$a$$$ and remove it. Then he should concatenate the remaining characters (in the same order).

Dreamoon wants to use the smallest number of steps to make $$$a$$$ empty. Please help Dreamoon, and print any sequence of the smallest number of steps to make $$$a$$$ empty.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 200\,000$$$), denoting the number of test cases in the input.

For each test case, there's one line with a non-empty string of lowercase Latin letters $$$a$$$.

The total sum of lengths of strings in all test cases is at most $$$200\,000$$$.

## Output Format
For each test case, in the first line, you should print $$$m$$$: the smallest number of steps to make $$$a$$$ empty. Each of the following $$$m$$$ lines should contain two integers $$$l_i, r_i$$$ ($$$1 \leq l_i \leq r_i \leq |a|$$$), denoting, that the $$$i$$$-th step is removing the characters from index $$$l_i$$$ to $$$r_i$$$ in the current string. (indices are numbered starting from $$$1$$$).

Note that after the deletion of the substring, indices of remaining characters may change, and $$$r_i$$$ should be at most the current length of $$$a$$$.

If there are several possible solutions, you can print any.

## Examples
```input
4
aabbcc
aaabbb
aaa
abacad
```
```output
3
3 3
2 4
1 2
3
3 4
2 3
1 2
3
1 1
1 1
1 1
1
1 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 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.5 seconds
Memory limit: 256.0 MB

# Problem
There is a string of length $$$n+1$$$ of characters 'A' and 'B'. The first character and last character of the string are equal to 'A'.

You are given $$$m$$$ indices $$$p_1, p_2, \ldots, p_m$$$ ($$$0$$$-indexation) denoting the other indices of characters 'A' in the string.

Let's denote the minimum distance between two neighboring 'A' as $$$l$$$, and maximum distance between neighboring 'A' as $$$r$$$.

For example, $$$(l,r)$$$ of string "ABBAABBBA" is $$$(1,4)$$$.

And let's denote the balance degree of a string as the value of $$$r-l$$$.

Now Dreamoon wants to change exactly $$$k$$$ characters from 'B' to 'A', and he wants to make the balance degree of the string as small as possible.

Please calculate the required minimum possible value of balance degree.

## Input Format
The first line contains one integer $$$t$$$ denoting the number of test cases ($$$1 \leq t \leq 400\,000$$$).

For each test case, the first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{15}, 0 \leq m \leq 400\,000, 0 \leq k < n - m$$$).

The second line contains $$$m$$$ integers $$$p_1, p_2, \ldots, p_m$$$, ($$$0 < p_1 < p_2 < \ldots < p_m < n$$$).

The total sum of $$$m$$$ is at most $$$400\,000$$$.

## Output Format
For each test case, print one integer: the smallest possible value of balance degree after $$$k$$$ changes of 'B' to 'A'.

## Examples
```input
5
80 3 5
11 24 50
81 7 12
4 10 17 26 37 48 61
25 10 14
3 4 7 12 13 15 17 19 21 23
1 0 0

10 2 0
2 4
```
```output
5
2
0
0
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
You are given a correct solution of the sudoku puzzle. If you don't know what is the sudoku, you can read about it here.

The picture showing the correct sudoku solution:

Blocks are bordered with bold black color.

Your task is to change at most $$$9$$$ elements of this field (i.e. choose some $$$1 \le i, j \le 9$$$ and change the number at the position $$$(i, j)$$$ to any other number in range $$$[1; 9]$$$) to make it anti-sudoku. The anti-sudoku is the $$$9 \times 9$$$ field, in which:

- Any number in this field is in range $$$[1; 9]$$$;
- each row contains at least two equal elements;
- each column contains at least two equal elements;
- each $$$3 \times 3$$$ block (you can read what is the block in the link above) contains at least two equal elements.

It is guaranteed that the answer exists.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of $$$9$$$ lines, each line consists of $$$9$$$ characters from $$$1$$$ to $$$9$$$ without any whitespaces — the correct solution of the sudoku puzzle.

## Output Format
For each test case, print the answer — the initial field with at most $$$9$$$ changed elements so that the obtained field is anti-sudoku. If there are several solutions, you can print any. It is guaranteed that the answer exists.

## Examples
```input
1
154873296
386592714
729641835
863725149
975314628
412968357
631457982
598236471
247189563
```
```output
154873396
336592714
729645835
863725145
979314628
412958357
631457992
998236471
247789563
```

Now solve the problem and return the code.