apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Mr. Chanek has an array $$$a$$$ of $$$n$$$ integers. The prettiness value of $$$a$$$ is denoted as:

$$$$$$\sum_{i=1}^{n} {\sum_{j=1}^{n} {\gcd(a_i, a_j) \cdot \gcd(i, j)}}$$$$$$

where $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

In other words, the prettiness value of an array $$$a$$$ is the total sum of $$$\gcd(a_i, a_j) \cdot \gcd(i, j)$$$ for all pairs $$$(i, j)$$$.

Help Mr. Chanek find the prettiness value of $$$a$$$, and output the result modulo $$$10^9 + 7$$$!

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$).

## Output Format
Output an integer denoting the prettiness value of $$$a$$$ modulo $$$10^9 + 7$$$.

## Examples
```input
5
3 6 2 1 4
```
```output
77
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
The Winter holiday will be here soon. Mr. Chanek wants to decorate his house's wall with ornaments. The wall can be represented as a binary string $$$a$$$ of length $$$n$$$. His favorite nephew has another binary string $$$b$$$ of length $$$m$$$ ($$$m \leq n$$$).

Mr. Chanek's nephew loves the non-negative integer $$$k$$$. His nephew wants exactly $$$k$$$ occurrences of $$$b$$$ as substrings in $$$a$$$.

However, Mr. Chanek does not know the value of $$$k$$$. So, for each $$$k$$$ ($$$0 \leq k \leq n - m + 1$$$), find the minimum number of elements in $$$a$$$ that have to be changed such that there are exactly $$$k$$$ occurrences of $$$b$$$ in $$$a$$$.

A string $$$s$$$ occurs exactly $$$k$$$ times in $$$t$$$ if there are exactly $$$k$$$ different pairs $$$(p,q)$$$ such that we can obtain $$$s$$$ by deleting $$$p$$$ characters from the beginning and $$$q$$$ characters from the end of $$$t$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 500$$$) — size of the binary string $$$a$$$ and $$$b$$$ respectively.

The second line contains a binary string $$$a$$$ of length $$$n$$$.

The third line contains a binary string $$$b$$$ of length $$$m$$$.

## Output Format
Output $$$n - m + 2$$$ integers — the $$$(k+1)$$$-th integer denotes the minimal number of elements in $$$a$$$ that have to be changed so there are exactly $$$k$$$ occurrences of $$$b$$$ as a substring in $$$a$$$.

## Examples
```input
9 3
100101011
101
```
```output
1 1 0 1 6 -1 -1 -1
```

## Note
For $$$k = 0$$$, to make the string $$$a$$$ have no occurrence of 101, you can do one character change as follows.

100101011 $$$\rightarrow$$$ 100100011

For $$$k = 1$$$, you can also change a single character.

100101011 $$$\rightarrow$$$ 100001011

For $$$k = 2$$$, no changes are needed.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Mr. Chanek has a new game called Dropping Balls. Initially, Mr. Chanek has a grid $$$a$$$ of size $$$n \times m$$$

Each cell $$$(x,y)$$$ contains an integer $$$a_{x,y}$$$ denoting the direction of how the ball will move.

- $$$a_{x,y}=1$$$ — the ball will move to the right (the next cell is $$$(x, y + 1)$$$);
- $$$a_{x,y}=2$$$ — the ball will move to the bottom (the next cell is $$$(x + 1, y)$$$);
- $$$a_{x,y}=3$$$ — the ball will move to the left (the next cell is $$$(x, y - 1)$$$).

Every time a ball leaves a cell $$$(x,y)$$$, the integer $$$a_{x,y}$$$ will change to $$$2$$$. Mr. Chanek will drop $$$k$$$ balls sequentially, each starting from the first row, and on the $$$c_1, c_2, \dots, c_k$$$-th ($$$1 \leq c_i \leq m$$$) columns.

Determine in which column each ball will end up in (position of the ball after leaving the grid).

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m \leq 1000$$$, $$$1 \leq k \leq 10^5$$$) — the size of the grid and the number of balls dropped by Mr. Chanek.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i,1},a_{i,2},\ldots,a_{i,m}$$$ ($$$1 \leq a_{i,j} \leq 3$$$). It will satisfy $$$a_{i, 1} \ne 3$$$ and $$$a_{i, m} \ne 1$$$.

The next line contains $$$k$$$ integers $$$c_1, c_2, \ldots, c_k$$$ ($$$1 \leq c_i \leq m$$$) — the balls' column positions dropped by Mr. Chanek sequentially.

## Output Format
Output $$$k$$$ integers — the $$$i$$$-th integer denoting the column where the $$$i$$$-th ball will end.

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

## Note
In the first example, the first ball will drop as follows. Note that the cell $$$(1, 1)$$$ will change direction to the bottom direction.

The second and third balls will drop as follows.

All balls will be dropped from the first row and on the $$$c_1, c_2, \dots, c_k$$$-th columns respectively. A ball will stop dropping once it leaves the grid.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Mr. Chanek wants to knit a batik, a traditional cloth from Indonesia. The cloth forms a grid $$$a$$$ with size $$$n \times m$$$. There are $$$k$$$ colors, and each cell in the grid can be one of the $$$k$$$ colors.

Define a sub-rectangle as an ordered pair of two cells $$$((x_1, y_1), (x_2, y_2))$$$, denoting the top-left cell and bottom-right cell (inclusively) of a sub-rectangle in $$$a$$$. Two sub-rectangles $$$((x_1, y_1), (x_2, y_2))$$$ and $$$((x_3, y_3), (x_4, y_4))$$$ have the same pattern if and only if the following holds:

- they have the same width ($$$x_2 - x_1 = x_4 - x_3$$$);
- they have the same height ($$$y_2 - y_1 = y_4 - y_3$$$);
- for every pair $$$(i, j)$$$ where $$$0 \leq i \leq x_2 - x_1$$$ and $$$0 \leq j \leq y_2 - y_1$$$, the color of cells $$$(x_1 + i, y_1 + j)$$$ and $$$(x_3 + i, y_3 + j)$$$ are equal.

Count the number of possible batik color combinations, such that the subrectangles $$$((a_x, a_y),(a_x + r - 1, a_y + c - 1))$$$ and $$$((b_x, b_y),(b_x + r - 1, b_y + c - 1))$$$ have the same pattern.

Output the answer modulo $$$10^9 + 7$$$.

## Input Format
The first line contains five integers $$$n$$$, $$$m$$$, $$$k$$$, $$$r$$$, and $$$c$$$ ($$$1 \leq n, m \leq 10^9$$$, $$$1 \leq k \leq 10^9$$$, $$$1 \leq r \leq \min(10^6, n)$$$, $$$1 \leq c \leq \min(10^6, m)$$$) — the size of the batik, the number of colors, and size of the sub-rectangle.

The second line contains four integers $$$a_x$$$, $$$a_y$$$, $$$b_x$$$, and $$$b_y$$$ ($$$1 \leq a_x, b_x \leq n$$$, $$$1 \leq a_y, b_y \leq m$$$) — the top-left corners of the first and second sub-rectangle. Both of the sub-rectangles given are inside the grid ($$$1 \leq a_x + r - 1$$$, $$$b_x + r - 1 \leq n$$$, $$$1 \leq a_y + c - 1$$$, $$$b_y + c - 1 \leq m$$$).

## Output Format
Output an integer denoting the number of possible batik color combinations modulo $$$10^9 + 7$$$.

## Examples
```input
3 3 2 2 2
1 1 2 2
```
```output
32
```
-----
```input
4 5 170845 2 2
1 4 3 1
```
```output
756680455
```

## Note
The following are all $$$32$$$ possible color combinations in the first example.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Mr. Chanek gives you a sequence $$$a$$$ indexed from $$$1$$$ to $$$n$$$. Define $$$f(a)$$$ as the number of indices where $$$a_i = i$$$.

You can pick an element from the current sequence and remove it, then concatenate the remaining elements together. For example, if you remove the $$$3$$$-rd element from the sequence $$$[4, 2, 3, 1]$$$, the resulting sequence will be $$$[4, 2, 1]$$$.

You want to remove some elements from $$$a$$$ in order to maximize $$$f(a)$$$, using zero or more operations. Find the largest possible $$$f(a)$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the initial length of the sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2 \cdot 10^5$$$) — the initial sequence $$$a$$$.

## Output Format
Output an integer denoting the largest $$$f(a)$$$ that can be obtained by doing zero or more operations.

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

## Note
In the first example, $$$f(A) = 3$$$ by doing the following operations.

$$$[2,1,\textbf{4},2,5,3,7] \rightarrow [\textbf{2},1,2,5,3,7] \rightarrow [1,2,5,3,\textbf{7}] \rightarrow [1,2,\textbf{5},3] \rightarrow [1,2,3]$$$

In the second example, $$$f(A) = 2$$$ and no additional operation is needed.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Mr. Chanek's city can be represented as a plane. He wants to build a housing complex in the city.

There are some telephone poles on the plane, which is represented by a grid $$$a$$$ of size $$$(n + 1) \times (m + 1)$$$. There is a telephone pole at $$$(x, y)$$$ if $$$a_{x, y} = 1$$$.

For each point $$$(x, y)$$$, define $$$S(x, y)$$$ as the square of the Euclidean distance between the nearest pole and $$$(x, y)$$$. Formally, the square of the Euclidean distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is $$$(x_2 - x_1)^2 + (y_2 - y_1)^2$$$.

To optimize the building plan, the project supervisor asks you the sum of all $$$S(x, y)$$$ for each $$$0 \leq x \leq n$$$ and $$$0 \leq y \leq m$$$. Help him by finding the value of $$$\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}}$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$0 \leq n, m < 2000$$$) — the size of the grid.

Then $$$(n + 1)$$$ lines follow, each containing $$$(m + 1)$$$ integers $$$a_{i, j}$$$ ($$$0 \leq a_{i, j} \leq 1$$$) — the grid denoting the positions of telephone poles in the plane. There is at least one telephone pole in the given grid.

## Output Format
Output an integer denoting the value of $$$\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}}$$$.

## Examples
```input
2 2
101
000
000
```
```output
18
```
-----
```input
5 4
10010
00000
01000
00001
00100
00010
```
```output
36
```

## Note
In the first example, the nearest telephone pole for the points $$$(0,0)$$$, $$$(1,0)$$$, $$$(2,0)$$$, $$$(0,1)$$$, $$$(1,1)$$$, and $$$(2,1)$$$ is at $$$(0, 0)$$$. While the nearest telephone pole for the points $$$(0, 2)$$$, $$$(1,2)$$$, and $$$(2,2)$$$ is at $$$(0, 2)$$$. Thus, $$$\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}} = (0 + 1 + 4) + (1 + 2 + 5) + (0 + 1 + 4) = 18$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 8.0 seconds
Memory limit: 256.0 MB

# Problem
XYMXYM and CQXYM will prepare $$$n$$$ problems for Codeforces. The difficulty of the problem $$$i$$$ will be an integer $$$a_i$$$, where $$$a_i \geq 0$$$. The difficulty of the problems must satisfy $$$a_i+a_{i+1}<m$$$ ($$$1 \leq i < n$$$), and $$$a_1+a_n<m$$$, where $$$m$$$ is a fixed integer. XYMXYM wants to know how many plans of the difficulty of the problems there are modulo $$$998\,244\,353$$$.

Two plans of difficulty $$$a$$$ and $$$b$$$ are different only if there is an integer $$$i$$$ ($$$1 \leq i \leq n$$$) satisfying $$$a_i \neq b_i$$$.

## Input Format
A single line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 50\,000$$$, $$$1 \leq m \leq 10^9$$$).

## Output Format
Print a single integer — the number of different plans.

## Examples
```input
3 2
```
```output
4
```
-----
```input
5 9
```
```output
8105
```
-----
```input
21038 3942834
```
```output
338529212
```

## Note
In the first test case, the valid $$$a$$$ are: $$$[0,0,0]$$$, $$$[0,0,1]$$$, $$$[0,1,0]$$$, $$$[1,0,0]$$$.

$$$[1,0,1]$$$ is invalid since $$$a_1+a_n \geq m$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarpus has n markers and m marker caps. Each marker is described by two numbers: xi is the color and yi is the diameter. Correspondingly, each cap is described by two numbers: aj is the color and bj is the diameter. Cap (aj, bj) can close marker (xi, yi) only if their diameters match, that is, bj = yi. Besides, a marker is considered to be beautifully closed, if the cap color and the marker color match, that is, aj = xi.

Find the way to close the maximum number of markers. If there are several such ways, then choose the one that has the maximum number of beautifully closed markers.

## Input Format
The first input line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the number of markers and the number of caps, correspondingly.

Next n lines describe the markers. The i-th line contains two space-separated integers xi, yi (1 ≤ xi, yi ≤ 1000) — the i-th marker's color and diameter, correspondingly.

Next m lines describe the caps. The j-th line contains two space-separated integers aj, bj (1 ≤ aj, bj ≤ 1000) — the color and diameter of the j-th cap, correspondingly.

## Output Format
Print two space-separated integers u, v, where u is the number of closed markers and v is the number of beautifully closed markers in the sought optimal way. Remember that you have to find the way to close the maximum number of markers, and if there are several such ways, you should choose the one where the number of beautifully closed markers is maximum.

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

## Note
In the first test sample the first marker should be closed by the fourth cap, the second marker should be closed by the first cap and the third marker should be closed by the second cap. Thus, three markers will be closed, and two of them will be beautifully closed — the first and the third markers.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
One popular website developed an unusual username editing procedure. One can change the username only by deleting some characters from it: to change the current name s, a user can pick number p and character c and delete the p-th occurrence of character c from the name. After the user changed his name, he can't undo the change.

For example, one can change name "arca" by removing the second occurrence of character "a" to get "arc".

Polycarpus learned that some user initially registered under nickname t, where t is a concatenation of k copies of string s. Also, Polycarpus knows the sequence of this user's name changes. Help Polycarpus figure out the user's final name.

## Input Format
The first line contains an integer k (1 ≤ k ≤ 2000). The second line contains a non-empty string s, consisting of lowercase Latin letters, at most 100 characters long. The third line contains an integer n (0 ≤ n ≤ 20000) — the number of username changes. Each of the next n lines contains the actual changes, one per line. The changes are written as "pi ci" (without the quotes), where pi (1 ≤ pi ≤ 200000) is the number of occurrences of letter ci, ci is a lowercase Latin letter. It is guaranteed that the operations are correct, that is, the letter to be deleted always exists, and after all operations not all letters are deleted from the name. The letters' occurrences are numbered starting from 1.

## Output Format
Print a single string — the user's final name after all changes are applied to it.

## Examples
```input
2
bac
3
2 a
1 b
2 c
```
```output
acb
```
-----
```input
1
abacaba
4
1 a
1 a
1 c
2 b
```
```output
baa
```

## Note
Let's consider the first sample. Initially we have name "bacbac"; the first operation transforms it into "bacbc", the second one — to "acbc", and finally, the third one transforms it into "acb".

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a non-empty string s consisting of lowercase letters. Find the number of pairs of non-overlapping palindromic substrings of this string.

In a more formal way, you have to find the quantity of tuples (a, b, x, y) such that 1 ≤ a ≤ b < x ≤ y ≤ |s| and substrings s[a... b], s[x... y] are palindromes.

A palindrome is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.

A substring s[i... j] (1 ≤ i ≤ j ≤ |s|) of string s = s1s2... s|s| is a string sisi + 1... sj. For example, substring s[2...4] of string s = "abacaba" equals "bac".

## Input Format
The first line of input contains a non-empty string s which consists of lowercase letters ('a'...'z'), s contains at most 2000 characters.

## Output Format
Output a single number — the quantity of pairs of non-overlapping palindromic substrings of s.

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

## Examples
```input
aa
```
```output
1
```
-----
```input
aaa
```
```output
5
```
-----
```input
abacaba
```
```output
36
```

Now solve the problem and return the code.