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
Denote a cyclic sequence of size $$$n$$$ as an array $$$s$$$ such that $$$s_n$$$ is adjacent to $$$s_1$$$. The segment $$$s[r, l]$$$ where $$$l < r$$$ is the concatenation of $$$s[r, n]$$$ and $$$s[1, l]$$$.

You are given an array $$$a$$$ consisting of $$$n$$$ integers. Define $$$b$$$ as the cyclic sequence obtained from concatenating $$$m$$$ copies of $$$a$$$. Note that $$$b$$$ has size $$$n \cdot m$$$.

You are given an integer $$$k$$$ where $$$k = 1$$$ or $$$k$$$ is a prime number. Find the number of different segments in $$$b$$$ where the sum of elements in the segment is divisible by $$$k$$$.

Two segments are considered different if the set of indices of the segments are different. For example, when $$$n = 3$$$ and $$$m = 2$$$, the set of indices for segment $$$s[2, 5]$$$ is $$$\{2, 3, 4, 5\}$$$, and for segment $$$s[5, 2]$$$ is $$$\{5, 6, 1, 2\}$$$. In particular, the segments $$$s[1, 6], s[2,1], \ldots, s[6, 5]$$$ are considered as the same segment.

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

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m, k \leq 2 \cdot 10^5$$$, $$$k = 1$$$ or $$$k$$$ is a prime number).

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

## Output Format
Output an integer denoting the number of different segments in $$$b$$$ where the sum of elements in the segment is divisible by $$$k$$$, modulo $$$10^9 + 7$$$.

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

## Note
In the first example, all valid segments are $$$[1,4]$$$, $$$[2, 3]$$$, $$$[3, 5]$$$, and $$$[4, 2]$$$.

In the second example, one of the valid segments is $$$[1, 5]$$$.

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

# Problem
Mr. Chanek has an integer represented by a string $$$s$$$. Zero or more digits have been erased and are denoted by the character _. There are also zero or more digits marked by the character X, meaning they're the same digit.

Mr. Chanek wants to count the number of possible integer $$$s$$$, where $$$s$$$ is divisible by $$$25$$$. Of course, $$$s$$$ must not contain any leading zero. He can replace the character _ with any digit. He can also replace the character X with any digit, but it must be the same for every character X.

As a note, a leading zero is any 0 digit that comes before the first nonzero digit in a number string in positional notation. For example, 0025 has two leading zeroes. An exception is the integer zero, (0 has no leading zero, but 0000 has three leading zeroes).

## Input Format
One line containing the string $$$s$$$ ($$$1 \leq |s| \leq 8$$$). The string $$$s$$$ consists of the characters 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, _, and X.

## Output Format
Output an integer denoting the number of possible integer $$$s$$$.

## Examples
```input
25
```
```output
1
```
-----
```input
_00
```
```output
9
```
-----
```input
_XX
```
```output
9
```
-----
```input
0
```
```output
1
```
-----
```input
0_25
```
```output
0
```

## Note
In the first example, the only possible $$$s$$$ is $$$25$$$.

In the second and third example, $$$s \in \{100, 200,300,400,500,600,700,800,900\}$$$.

In the fifth example, all possible $$$s$$$ will have at least one leading zero.

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

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

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

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
There is a city park represented as a tree with $$$n$$$ attractions as its vertices and $$$n - 1$$$ rails as its edges. The $$$i$$$-th attraction has happiness value $$$a_i$$$.

Each rail has a color. It is either black if $$$t_i = 0$$$, or white if $$$t_i = 1$$$. Black trains only operate on a black rail track, and white trains only operate on a white rail track. If you are previously on a black train and want to ride a white train, or you are previously on a white train and want to ride a black train, you need to use $$$1$$$ ticket.

The path of a tour must be a simple path — it must not visit an attraction more than once. You do not need a ticket the first time you board a train. You only have $$$k$$$ tickets, meaning you can only switch train types at most $$$k$$$ times. In particular, you do not need a ticket to go through a path consisting of one rail color.

Define $$$f(u, v)$$$ as the sum of happiness values of the attractions in the tour $$$(u, v)$$$, which is a simple path that starts at the $$$u$$$-th attraction and ends at the $$$v$$$-th attraction. Find the sum of $$$f(u,v)$$$ for all valid tours $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$) that does not need more than $$$k$$$ tickets, modulo $$$10^9 + 7$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq n-1$$$) — the number of attractions in the city park and the number of tickets you have.

The second line contains $$$n$$$ integers $$$a_1, a_2,\ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the happiness value of each attraction.

The $$$i$$$-th of the next $$$n - 1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$0 \leq t_i \leq 1$$$) — an edge between vertices $$$u_i$$$ and $$$v_i$$$ with color $$$t_i$$$. The given edges form a tree.

## Output Format
Output an integer denoting the total happiness value for all valid tours $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$), modulo $$$10^9 + 7$$$.

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

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

# Problem
Mr. Chanek opened a letter from his fellow, who is currently studying at Singanesia. Here is what it says.

Define an array $$$b$$$ ($$$0 \leq b_i < k$$$) with $$$n$$$ integers. While there exists a pair $$$(i, j)$$$ such that $$$b_i \ne b_j$$$, do the following operation:

- Randomly pick a number $$$i$$$ satisfying $$$0 \leq i < n$$$. Note that each number $$$i$$$ has a probability of $$$\frac{1}{n}$$$ to be picked.
- Randomly Pick a number $$$j$$$ satisfying $$$0 \leq j < k$$$.
- Change the value of $$$b_i$$$ to $$$j$$$. It is possible for $$$b_i$$$ to be changed to the same value.

Denote $$$f(b)$$$ as the expected number of operations done to $$$b$$$ until all elements of $$$b$$$ are equal.

You are given two integers $$$n$$$ and $$$k$$$, and an array $$$a$$$ ($$$-1 \leq a_i < k$$$) of $$$n$$$ integers.

For every index $$$i$$$ with $$$a_i = -1$$$, replace $$$a_i$$$ with a random number $$$j$$$ satisfying $$$0 \leq j < k$$$. Let $$$c$$$ be the number of occurrences of $$$-1$$$ in $$$a$$$. There are $$$k^c$$$ possibilites of $$$a$$$ after the replacement, each with equal probability of being the final array.

Find the expected value of $$$f(a)$$$ modulo $$$10^9 + 7$$$.

Formally, let $$$M = 10^9 + 7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

After reading the letter, Mr. Chanek gave the task to you. Solve it for the sake of their friendship!

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq 10^9$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i < k$$$).

## Output Format
Output an integer denoting the expected value of $$$f(a)$$$ modulo $$$10^9 + 7$$$.

## Examples
```input
2 2
0 1
```
```output
2
```
-----
```input
2 2
0 -1
```
```output
1
```
-----
```input
3 3
0 1 1
```
```output
12
```
-----
```input
3 3
-1 -1 -1
```
```output
11
```
-----
```input
10 9
-1 0 -1 1 1 2 2 3 3 3
```
```output
652419213
```

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: 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 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 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 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: 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 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: 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 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: 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 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: 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.