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

# Problem
A sequence $$$a_1, a_2, \dots, a_k$$$ is called an arithmetic progression if for each $$$i$$$ from $$$1$$$ to $$$k$$$ elements satisfy the condition $$$a_i = a_1 + c \cdot (i - 1)$$$ for some fixed $$$c$$$.

For example, these five sequences are arithmetic progressions: $$$[5, 7, 9, 11]$$$, $$$[101]$$$, $$$[101, 100, 99]$$$, $$$[13, 97]$$$ and $$$[5, 5, 5, 5, 5]$$$. And these four sequences aren't arithmetic progressions: $$$[3, 1, 2]$$$, $$$[1, 2, 4, 8]$$$, $$$[1, -1, 1, -1]$$$ and $$$[1, 2, 3, 3, 3]$$$.

You are given a sequence of integers $$$b_1, b_2, \dots, b_n$$$. Find any index $$$j$$$ ($$$1 \le j \le n$$$), such that if you delete $$$b_j$$$ from the sequence, you can reorder the remaining $$$n-1$$$ elements, so that you will get an arithmetic progression. If there is no such index, output the number -1.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — length of the sequence $$$b$$$. The second line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — elements of the sequence $$$b$$$.

## Output Format
Print such index $$$j$$$ ($$$1 \le j \le n$$$), so that if you delete the $$$j$$$-th element from the sequence, you can reorder the remaining elements, so that you will get an arithmetic progression. If there are multiple solutions, you are allowed to print any of them. If there is no such index, print -1.

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

## Note
Note to the first example. If you delete the $$$4$$$-th element, you can get the arithmetic progression $$$[2, 4, 6, 8]$$$.

Note to the second example. The original sequence is already arithmetic progression, so you can delete $$$1$$$-st or last element and you will get an arithmetical progression again.

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
Tokitsukaze is one of the characters in the game "Kantai Collection". In this game, every character has a common attribute — health points, shortened to HP.

In general, different values of HP are grouped into $$$4$$$ categories:

- Category $$$A$$$ if HP is in the form of $$$(4 n + 1)$$$, that is, when divided by $$$4$$$, the remainder is $$$1$$$;
- Category $$$B$$$ if HP is in the form of $$$(4 n + 3)$$$, that is, when divided by $$$4$$$, the remainder is $$$3$$$;
- Category $$$C$$$ if HP is in the form of $$$(4 n + 2)$$$, that is, when divided by $$$4$$$, the remainder is $$$2$$$;
- Category $$$D$$$ if HP is in the form of $$$4 n$$$, that is, when divided by $$$4$$$, the remainder is $$$0$$$.

The above-mentioned $$$n$$$ can be any integer.

These $$$4$$$ categories ordered from highest to lowest as $$$A > B > C > D$$$, which means category $$$A$$$ is the highest and category $$$D$$$ is the lowest.

While playing the game, players can increase the HP of the character. Now, Tokitsukaze wants you to increase her HP by at most $$$2$$$ (that is, either by $$$0$$$, $$$1$$$ or $$$2$$$). How much should she increase her HP so that it has the highest possible category?

## Input Format
The only line contains a single integer $$$x$$$ ($$$30 \leq x \leq 100$$$) — the value Tokitsukaze's HP currently.

## Output Format
Print an integer $$$a$$$ ($$$0 \leq a \leq 2$$$) and an uppercase letter $$$b$$$ ($$$b \in \lbrace A, B, C, D \rbrace$$$), representing that the best way is to increase her HP by $$$a$$$, and then the category becomes $$$b$$$.

Note that the output characters are case-sensitive.

## Examples
```input
33
```
```output
0 A
```
-----
```input
98
```
```output
1 B
```

## Note
For the first example, the category of Tokitsukaze's HP is already $$$A$$$, so you don't need to enhance her ability.

For the second example:

- If you don't increase her HP, its value is still $$$98$$$, which equals to $$$(4 \times 24 + 2)$$$, and its category is $$$C$$$.
- If you increase her HP by $$$1$$$, its value becomes $$$99$$$, which equals to $$$(4 \times 24 + 3)$$$, and its category becomes $$$B$$$.
- If you increase her HP by $$$2$$$, its value becomes $$$100$$$, which equals to $$$(4 \times 25)$$$, and its category becomes $$$D$$$.

Therefore, the best way is to increase her HP by $$$1$$$ so that the category of her HP becomes $$$B$$$.

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
Tokitsukaze is playing a game derivated from Japanese mahjong. In this game, she has three tiles in her hand. Each tile she owns is a suited tile, which means it has a suit (manzu, pinzu or souzu) and a number (a digit ranged from $$$1$$$ to $$$9$$$). In this problem, we use one digit and one lowercase letter, which is the first character of the suit, to represent a suited tile. All possible suited tiles are represented as 1m, 2m, $$$\ldots$$$, 9m, 1p, 2p, $$$\ldots$$$, 9p, 1s, 2s, $$$\ldots$$$, 9s.

In order to win the game, she must have at least one mentsu (described below) in her hand, so sometimes she should draw extra suited tiles. After drawing a tile, the number of her tiles increases by one. She can draw any tiles she wants, including those already in her hand.

Do you know the minimum number of extra suited tiles she needs to draw so that she can win?

Here are some useful definitions in this game:

- A mentsu, also known as meld, is formed by a koutsu or a shuntsu;
- A koutsu, also known as triplet, is made of three identical tiles, such as [1m, 1m, 1m], however, [1m, 1p, 1s] or [1m, 4m, 7m] is NOT a koutsu;
- A shuntsu, also known as sequence, is made of three sequential numbered tiles in the same suit, such as [1m, 2m, 3m] and [5s, 7s, 6s], however, [9m, 1m, 2m] or [1m, 2p, 3s] is NOT a shuntsu.

Some examples:

- [2m, 3p, 2s, 4m, 1s, 2s, 4s] — it contains no koutsu or shuntsu, so it includes no mentsu;
- [4s, 3m, 3p, 4s, 5p, 4s, 5p] — it contains a koutsu, [4s, 4s, 4s], but no shuntsu, so it includes a mentsu;
- [5p, 5s, 9m, 4p, 1s, 7p, 7m, 6p] — it contains no koutsu but a shuntsu, [5p, 4p, 6p] or [5p, 7p, 6p], so it includes a mentsu.

Note that the order of tiles is unnecessary and you can assume the number of each type of suited tiles she can draw is infinite.

## Input Format
The only line contains three strings — the tiles in Tokitsukaze's hand. For each string, the first character is a digit ranged from $$$1$$$ to $$$9$$$ and the second character is m, p or s.

## Output Format
Print a single integer — the minimum number of extra suited tiles she needs to draw.

## Examples
```input
1s 2s 3s
```
```output
0
```
-----
```input
9m 9m 9m
```
```output
0
```
-----
```input
3p 9m 2p
```
```output
1
```

## Note
In the first example, Tokitsukaze already has a shuntsu.

In the second example, Tokitsukaze already has a koutsu.

In the third example, Tokitsukaze can get a shuntsu by drawing one suited tile — 1p or 4p. The resulting tiles will be [3p, 9m, 2p, 1p] or [3p, 9m, 2p, 4p].

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
Amugae is in a very large round corridor. The corridor consists of two areas. The inner area is equally divided by $$$n$$$ sectors, and the outer area is equally divided by $$$m$$$ sectors. A wall exists between each pair of sectors of same area (inner or outer), but there is no wall between the inner area and the outer area. A wall always exists at the 12 o'clock position.

The inner area's sectors are denoted as $$$(1,1), (1,2), \dots, (1,n)$$$ in clockwise direction. The outer area's sectors are denoted as $$$(2,1), (2,2), \dots, (2,m)$$$ in the same manner. For a clear understanding, see the example image above.

Amugae wants to know if he can move from one sector to another sector. He has $$$q$$$ questions.

For each question, check if he can move between two given sectors.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 10^{18}$$$, $$$1 \le q \le 10^4$$$) — the number of sectors in the inner area, the number of sectors in the outer area and the number of questions.

Each of the next $$$q$$$ lines contains four integers $$$s_x$$$, $$$s_y$$$, $$$e_x$$$, $$$e_y$$$ ($$$1 \le s_x, e_x \le 2$$$; if $$$s_x = 1$$$, then $$$1 \le s_y \le n$$$, otherwise $$$1 \le s_y \le m$$$; constraints on $$$e_y$$$ are similar). Amague wants to know if it is possible to move from sector $$$(s_x, s_y)$$$ to sector $$$(e_x, e_y)$$$.

## Output Format
For each question, print "YES" if Amugae can move from $$$(s_x, s_y)$$$ to $$$(e_x, e_y)$$$, and "NO" otherwise.

You can print each letter in any case (upper or lower).

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

## Note
Example is shown on the picture in the statement.

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

# Problem
Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is square-shaped consisting of $$$n$$$ rows and $$$n$$$ columns of square cells. The rows are numbered from $$$1$$$ to $$$n$$$, from top to bottom, and the columns are numbered from $$$1$$$ to $$$n$$$, from left to right. The position of a cell at row $$$r$$$ and column $$$c$$$ is represented as $$$(r, c)$$$. There are only two colors for the cells in cfpaint — black and white.

There is a tool named eraser in cfpaint. The eraser has an integer size $$$k$$$ ($$$1 \le k \le n$$$). To use the eraser, Gildong needs to click on a cell $$$(i, j)$$$ where $$$1 \le i, j \le n - k + 1$$$. When a cell $$$(i, j)$$$ is clicked, all of the cells $$$(i', j')$$$ where $$$i \le i' \le i + k - 1$$$ and $$$j \le j' \le j + k - 1$$$ become white. In other words, a square with side equal to $$$k$$$ cells and top left corner at $$$(i, j)$$$ is colored white.

A white line is a row or a column without any black cells.

Gildong has worked with cfpaint for some time, so some of the cells (possibly zero or all) are currently black. He wants to know the maximum number of white lines after using the eraser exactly once. Help Gildong find the answer to his question.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2000$$$) — the number of rows and columns, and the size of the eraser.

The next $$$n$$$ lines contain $$$n$$$ characters each without spaces. The $$$j$$$-th character in the $$$i$$$-th line represents the cell at $$$(i,j)$$$. Each character is given as either 'B' representing a black cell, or 'W' representing a white cell.

## Output Format
Print one integer: the maximum number of white lines after using the eraser exactly once.

## Examples
```input
4 2
BWWW
WBBW
WBBW
WWWB
```
```output
4
```
-----
```input
3 1
BWB
WWB
BWB
```
```output
2
```
-----
```input
5 3
BWBBB
BWBBB
BBBBB
BBBBB
WBBBW
```
```output
2
```
-----
```input
2 2
BW
WB
```
```output
4
```
-----
```input
2 1
WW
WW
```
```output
4
```

## Note
In the first example, Gildong can click the cell $$$(2, 2)$$$, then the working screen becomes:

Then there are four white lines — the $$$2$$$-nd and $$$3$$$-rd row, and the $$$2$$$-nd and $$$3$$$-rd column.

In the second example, clicking the cell $$$(2, 3)$$$ makes the $$$2$$$-nd row a white line.

In the third example, both the $$$2$$$-nd column and $$$5$$$-th row become white lines by clicking the cell $$$(3, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Amugae has a sentence consisting of $$$n$$$ words. He want to compress this sentence into one word. Amugae doesn't like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges "sample" and "please" into "samplease".

Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of the words in Amugae's sentence.

The second line contains $$$n$$$ words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits ('A', 'B', ..., 'Z', 'a', 'b', ..., 'z', '0', '1', ..., '9'). The total length of the words does not exceed $$$10^6$$$.

## Output Format
In the only line output the compressed word after the merging process ends as described in the problem.

## Examples
```input
5
I want to order pizza
```
```output
Iwantorderpizza
```
-----
```input
5
sample please ease in out
```
```output
sampleaseinout
```

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: 8.0 seconds
Memory limit: 128.0 MB

# Problem
While roaming the mystic areas of Stonefalls, in order to drop legendary loot, an adventurer was given a quest as follows. He was given an array $$$A = {a_1,a_2,...,a_N }$$$ of length $$$N$$$, and a number $$$K$$$.

Define array $$$B$$$ as $$$B(q, A) = $$$ { $$$q-a_1, q-a_2, ..., q-a_N$$$ }. Define function $$$F$$$ as $$$F(B,K)$$$ being sum of products of all $$$K$$$-tuples of elements in array $$$B$$$. For example, if the array $$$B$$$ is $$$[2,3,4,5]$$$, and with $$$K=3$$$, sum of products of all 3-tuples is $$$$$$F(B, 3) = 2*3*4+2*3*5+3*4*5+2*4*5$$$$$$

He was then given a number Q, number of queries of two types:

- Type 1: Given $$$q$$$, $$$i$$$, and $$$d$$$ calculate $$$F(B(q, A), K)$$$ where we make change to initial array as $$$A[i] = d$$$.
- Type 2: Given $$$q$$$, $$$L$$$, $$$R$$$, and $$$d$$$ calculate $$$F(B(q, A), K)$$$ where we make change to initial array as $$$A[i] = A[i] + d$$$ for all $$$i$$$ in range $$$[L, R]$$$ inclusive.

All changes are temporarily made to initial array, and don't propagate to following queries. Help the adventurer calculate the answer to a quest, and finally get that loot!

## Input Format
In the first two lines, numbers $$$N$$$ ($$$1 \leq N \leq 2*10^4$$$) and $$$K$$$ ($$$1 \leq K \leq N$$$), the length of initial array $$$A$$$, and tuple size, followed by $$$a_1,a_2,a_3,…,a_N$$$ ($$$0 \leq a_i \leq 10^9$$$) , elements of array $$$A$$$, in the next line. Then follows number $$$Q$$$ ($$$Q \leq 10$$$), number of queries. In the next $$$Q$$$ lines come queries of the form:

- 1 q i d, for type 1,
- 2 q L R d, for type 2,

as explained above ($$$0 \leq q, d \leq 10^9, 1 \leq i,L,R \leq N$$$)

## Output Format
Print $$$Q$$$ lines, the answers to queries, modulo $$$998244353$$$.

## Examples
```input
5
2
1 2 3 4 5
3
1 6 1 1
1 6 5 2
2 6 2 3 1
```
```output
85
127
63
```

## Note
In the first query array A = [1, 2, 3, 4, 5], B = [5, 4, 3, 2, 1], sum of products of 2-tuples = 85.

In second query array A = [1, 2, 3, 4, 2], B = [5, 4, 3, 2, 4], sum of products of 2-tuples = 127

In third query array A = [1, 3, 4, 4, 5], B = [5, 3, 2, 2, 1], sum of products of 2-tuples = 63

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

# Problem
Three planets $$$X$$$, $$$Y$$$ and $$$Z$$$ within the Alpha planetary system are inhabited with an advanced civilization. The spaceports of these planets are connected by interplanetary space shuttles. The flight scheduler should decide between $$$1$$$, $$$2$$$ and $$$3$$$ return flights for every existing space shuttle connection. Since the residents of Alpha are strong opponents of the symmetry, there is a strict rule that any two of the spaceports connected by a shuttle must have a different number of flights.

For every pair of connected spaceports, your goal is to propose a number $$$1$$$, $$$2$$$ or $$$3$$$ for each shuttle flight, so that for every two connected spaceports the overall number of flights differs.

You may assume that:

1) Every planet has at least one spaceport

2) There exist only shuttle flights between spaceports of different planets

3) For every two spaceports there is a series of shuttle flights enabling traveling between them

4) Spaceports are not connected by more than one shuttle

## Input Format
The first row of the input is the integer number $$$N$$$ $$$(3 \leq N \leq 100 000)$$$, representing overall number of spaceports. The second row is the integer number $$$M$$$ $$$(2 \leq M \leq 100 000)$$$ representing number of shuttle flight connections.

Third row contains $$$N$$$ characters from the set $$$\{X, Y, Z\}$$$. Letter on $$$I^{th}$$$ position indicates on which planet is situated spaceport $$$I$$$. For example, "XYYXZZ" indicates that the spaceports $$$0$$$ and $$$3$$$ are located at planet $$$X$$$, spaceports $$$1$$$ and $$$2$$$ are located at $$$Y$$$, and spaceports $$$4$$$ and $$$5$$$ are at $$$Z$$$.

Starting from the fourth row, every row contains two integer numbers separated by a whitespace. These numbers are natural numbers smaller than $$$N$$$ and indicate the numbers of the spaceports that are connected. For example, "$$$12\ 15$$$" indicates that there is a shuttle flight between spaceports $$$12$$$ and $$$15$$$.

## Output Format
The same representation of shuttle flights in separate rows as in the input, but also containing a third number from the set $$$\{1, 2, 3\}$$$ standing for the number of shuttle flights between these spaceports.

## Examples
```input
10
15
XXXXYYYZZZ
0 4
0 5
0 6
4 1
4 8
1 7
1 9
7 2
7 5
5 3
6 2
6 9
8 2
8 3
9 3
```
```output
0 4 2
0 5 2
0 6 2
4 1 1
4 8 1
1 7 2
1 9 3
7 2 2
7 5 1
5 3 1
6 2 1
6 9 1
8 2 3
8 3 1
9 3 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
In this problem, a $$$n \times m$$$ rectangular matrix $$$a$$$ is called increasing if, for each row of $$$i$$$, when go from left to right, the values strictly increase (that is, $$$a_{i,1}<a_{i,2}<\dots<a_{i,m}$$$) and for each column $$$j$$$, when go from top to bottom, the values strictly increase (that is, $$$a_{1,j}<a_{2,j}<\dots<a_{n,j}$$$).

In a given matrix of non-negative integers, it is necessary to replace each value of $$$0$$$ with some positive integer so that the resulting matrix is increasing and the sum of its elements is maximum, or find that it is impossible.

It is guaranteed that in a given value matrix all values of $$$0$$$ are contained only in internal cells (that is, not in the first or last row and not in the first or last column).

## Input Format
The first line contains integers $$$n$$$ and $$$m$$$ ($$$3 \le n, m \le 500$$$) — the number of rows and columns in the given matrix $$$a$$$.

The following lines contain $$$m$$$ each of non-negative integers — the values in the corresponding row of the given matrix: $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$0 \le a_{i,j} \le 8000$$$).

It is guaranteed that for all $$$a_{i,j}=0$$$, $$$1 < i < n$$$ and $$$1 < j < m$$$ are true.

## Output Format
If it is possible to replace all zeros with positive numbers so that the matrix is increasing, print the maximum possible sum of matrix elements. Otherwise, print -1.

## Examples
```input
4 5
1 3 5 6 7
3 0 7 0 9
5 0 0 0 10
8 9 10 11 12
```
```output
144
```
-----
```input
3 3
1 2 3
2 0 4
4 5 6
```
```output
30
```
-----
```input
3 3
1 2 3
3 0 4
4 5 6
```
```output
-1
```
-----
```input
3 3
1 2 3
2 3 4
3 4 2
```
```output
-1
```

## Note
In the first example, the resulting matrix is as follows:

In the second example, the value $$$3$$$ must be put in the middle cell.

In the third example, the desired resultant matrix does not exist.

Now solve the problem and return the code.