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
Kolya got an integer array $$$a_1, a_2, \dots, a_n$$$. The array can contain both positive and negative integers, but Kolya doesn't like $$$0$$$, so the array doesn't contain any zeros.

Kolya doesn't like that the sum of some subsegments of his array can be $$$0$$$. The subsegment is some consecutive segment of elements of the array.

You have to help Kolya and change his array in such a way that it doesn't contain any subsegments with the sum $$$0$$$. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, $$$0$$$, any by absolute value, even such a huge that they can't be represented in most standard programming languages).

Your task is to find the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $$$0$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of elements in Kolya's array.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^{9} \le a_i \le 10^{9}, a_i \neq 0$$$) — the description of Kolya's array.

## Output Format
Print the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $$$0$$$.

## Examples
```input
4
1 -5 3 2
```
```output
1
```
-----
```input
5
4 -2 3 -9 2
```
```output
0
```
-----
```input
9
-1 1 -1 1 -1 1 1 -1 -1
```
```output
6
```
-----
```input
8
16 -5 -11 -15 10 5 4 -4
```
```output
3
```

## Note
Consider the first example. There is only one subsegment with the sum $$$0$$$. It starts in the second element and ends in the fourth element. It's enough to insert one element so the array doesn't contain any subsegments with the sum equal to zero. For example, it is possible to insert the integer $$$1$$$ between second and third elements of the array.

There are no subsegments having sum $$$0$$$ in the second example so you don't need to do anything.

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
You are given a string $$$s$$$ consisting of lowercase Latin letters "a", "b" and "c" and question marks "?".

Let the number of question marks in the string $$$s$$$ be $$$k$$$. Let's replace each question mark with one of the letters "a", "b" and "c". Here we can obtain all $$$3^{k}$$$ possible strings consisting only of letters "a", "b" and "c". For example, if $$$s = $$$"ac?b?c" then we can obtain the following strings: $$$[$$$"acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"$$$]$$$.

Your task is to count the total number of subsequences "abc" in all resulting strings. Since the answer can be very large, print it modulo $$$10^{9} + 7$$$.

A subsequence of the string $$$t$$$ is such a sequence that can be derived from the string $$$t$$$ after removing some (possibly, zero) number of letters without changing the order of remaining letters. For example, the string "baacbc" contains two subsequences "abc" — a subsequence consisting of letters at positions $$$(2, 5, 6)$$$ and a subsequence consisting of letters at positions $$$(3, 5, 6)$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ $$$(3 \le n \le 200\,000)$$$ — the length of $$$s$$$.

The second line of the input contains the string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters "a", "b" and "c" and question marks"?".

## Output Format
Print the total number of subsequences "abc" in all strings you can obtain if you replace all question marks with letters "a", "b" and "c", modulo $$$10^{9} + 7$$$.

## Examples
```input
6
ac?b?c
```
```output
24
```
-----
```input
7
???????
```
```output
2835
```
-----
```input
9
cccbbbaaa
```
```output
0
```
-----
```input
5
a???c
```
```output
46
```

## Note
In the first example, we can obtain $$$9$$$ strings:

- "acabac" — there are $$$2$$$ subsequences "abc",
- "acabbc" — there are $$$4$$$ subsequences "abc",
- "acabcc" — there are $$$4$$$ subsequences "abc",
- "acbbac" — there are $$$2$$$ subsequences "abc",
- "acbbbc" — there are $$$3$$$ subsequences "abc",
- "acbbcc" — there are $$$4$$$ subsequences "abc",
- "accbac" — there is $$$1$$$ subsequence "abc",
- "accbbc" — there are $$$2$$$ subsequences "abc",
- "accbcc" — there are $$$2$$$ subsequences "abc".

So, there are $$$2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24$$$ subsequences "abc" in total.

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
You have $$$n$$$ distinct points $$$(x_1, y_1),\ldots,(x_n,y_n)$$$ on the plane and a non-negative integer parameter $$$k$$$. Each point is a microscopic steel ball and $$$k$$$ is the attract power of a ball when it's charged. The attract power is the same for all balls.

In one operation, you can select a ball $$$i$$$ to charge it. Once charged, all balls with Manhattan distance at most $$$k$$$ from ball $$$i$$$ move to the position of ball $$$i$$$. Many balls may have the same coordinate after an operation.

More formally, for all balls $$$j$$$ such that $$$|x_i - x_j| + |y_i - y_j| \le k$$$, we assign $$$x_j:=x_i$$$ and $$$y_j:=y_i$$$.

An example of an operation. After charging the ball in the center, two other balls move to its position. On the right side, the red dot in the center is the common position of those balls.

Your task is to find the minimum number of operations to move all balls to the same position, or report that this is impossible.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$2 \le n \le 100$$$, $$$0 \le k \le 10^6$$$) — the number of balls and the attract power of all balls, respectively.

The following $$$n$$$ lines describe the balls' coordinates. The $$$i$$$-th of these lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^5$$$) — the coordinates of the $$$i$$$-th ball.

It is guaranteed that all points are distinct.

## Output Format
For each test case print a single integer — the minimum number of operations to move all balls to the same position, or $$$-1$$$ if it is impossible.

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

## Note
In the first test case, there are three balls at $$$(0, 0)$$$, $$$(3, 3)$$$, and $$$(1, 1)$$$ and the attract power is $$$2$$$. It is possible to move two balls together with one operation, but not all three balls together with any number of operations.

In the second test case, there are three balls at $$$(6, 7)$$$, $$$(8, 8)$$$, and $$$(6, 9)$$$ and the attract power is $$$3$$$. If we charge any ball, the other two will move to the same position, so we only require one operation.

In the third test case, there are four balls at $$$(0, 0)$$$, $$$(0, 1)$$$, $$$(0, 2)$$$, and $$$(0, 3)$$$, and the attract power is $$$1$$$. We can show that it is impossible to move all balls to the same position with a sequence of operations.

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
There is a game called "Unique Bid Auction". You can read more about it here: https://en.wikipedia.org/wiki/Unique_bid_auction (though you don't have to do it to solve this problem).

Let's simplify this game a bit. Formally, there are $$$n$$$ participants, the $$$i$$$-th participant chose the number $$$a_i$$$. The winner of the game is such a participant that the number he chose is unique (i. e. nobody else chose this number except him) and is minimal (i. e. among all unique values of $$$a$$$ the minimum one is the winning one).

Your task is to find the index of the participant who won the game (or -1 if there is no winner). Indexing is $$$1$$$-based, i. e. the participants are numbered from $$$1$$$ to $$$n$$$.

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

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

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of participants. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the $$$i$$$-th participant chosen number.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

## Output Format
For each test case, print the answer — the index of the participant who won the game (or -1 if there is no winner). Note that the answer is always unique.

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

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

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

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

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$n$$$ ($$$n > 1$$$).

Your task is to find a sequence of integers $$$a_1, a_2, \ldots, a_k$$$ such that:

- each $$$a_i$$$ is strictly greater than $$$1$$$;
- $$$a_1 \cdot a_2 \cdot \ldots \cdot a_k = n$$$ (i. e. the product of this sequence is $$$n$$$);
- $$$a_{i + 1}$$$ is divisible by $$$a_i$$$ for each $$$i$$$ from $$$1$$$ to $$$k-1$$$;
- $$$k$$$ is the maximum possible (i. e. the length of this sequence is the maximum possible).

If there are several such sequences, any of them is acceptable. It can be proven that at least one valid sequence always exists for any integer $$$n > 1$$$.

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

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

The only line of the test case contains one integer $$$n$$$ ($$$2 \le n \le 10^{10}$$$).

It is guaranteed that the sum of $$$n$$$ does not exceed $$$10^{10}$$$ ($$$\sum n \le 10^{10}$$$).

## Output Format
For each test case, print the answer: in the first line, print one positive integer $$$k$$$ — the maximum possible length of $$$a$$$. In the second line, print $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ — the sequence of length $$$k$$$ satisfying the conditions from the problem statement.

If there are several answers, you can print any. It can be proven that at least one valid sequence always exists for any integer $$$n > 1$$$.

## Examples
```input
4
2
360
4999999937
4998207083
```
```output
1
2 
3
2 2 90 
1
4999999937 
1
4998207083
```

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 an array $$$a$$$ consisting of $$$n$$$ integers.

Let $$$min(l, r)$$$ be the minimum value among $$$a_l, a_{l + 1}, \ldots, a_r$$$ and $$$max(l, r)$$$ be the maximum value among $$$a_l, a_{l + 1}, \ldots, a_r$$$.

Your task is to choose three positive (greater than $$$0$$$) integers $$$x$$$, $$$y$$$ and $$$z$$$ such that:

- $$$x + y + z = n$$$;
- $$$max(1, x) = min(x + 1, x + y) = max(x + y + 1, n)$$$.

In other words, you have to split the array $$$a$$$ into three consecutive non-empty parts that cover the whole array and the maximum in the first part equals the minimum in the second part and equals the maximum in the third part (or determine it is impossible to find such a partition).

Among all such triples (partitions), you can choose any.

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

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

The first line of the test case contains one integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of $$$a$$$.

The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

## Output Format
For each test case, print the answer: NO in the only line if there is no such partition of $$$a$$$ that satisfies the conditions from the problem statement. Otherwise, print YES in the first line and three integers $$$x$$$, $$$y$$$ and $$$z$$$ ($$$x + y + z = n$$$) in the second line.

If there are several answers, you can print any.

## Examples
```input
6
11
1 2 3 3 3 4 4 3 4 2 1
8
2 9 1 7 3 9 4 1
9
2 1 4 2 4 3 3 1 2
7
4 2 1 1 4 1 4
5
1 1 1 1 1
7
4 3 4 3 3 3 4
```
```output
YES
6 1 4
NO
YES
2 5 2
YES
4 1 2
YES
1 1 3
YES
2 1 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Holidays are coming up really soon. Rick realized that it's time to think about buying a traditional spruce tree. But Rick doesn't want real trees to get hurt so he decided to find some in an $$$n \times m$$$ matrix consisting of "*" and ".".

To find every spruce first let's define what a spruce in the matrix is. A set of matrix cells is called a spruce of height $$$k$$$ with origin at point $$$(x, y)$$$ if:

- All cells in the set contain an "*".
- For each $$$1 \le i \le k$$$ all cells with the row number $$$x+i-1$$$ and columns in range $$$[y - i + 1, y + i - 1]$$$ must be a part of the set. All other cells cannot belong to the set.

Examples of correct and incorrect spruce trees:

Now Rick wants to know how many spruces his $$$n \times m$$$ matrix contains. Help Rick solve this problem.

## Input Format
Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$).

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 500$$$) — matrix size.

Next $$$n$$$ lines of each test case contain $$$m$$$ characters $$$c_{i, j}$$$ — matrix contents. It is guaranteed that $$$c_{i, j}$$$ is either a "." or an "*".

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$500^2$$$ ($$$\sum n \cdot m \le 500^2$$$).

## Output Format
For each test case, print single integer — the total number of spruces in the matrix.

## Examples
```input
4
2 3
.*.
***
2 3
.*.
**.
4 5
.***.
*****
*****
*.*.*
5 7
..*.*..
.*****.
*******
.*****.
..*.*..
```
```output
5
3
23
34
```

## Note
In the first test case the first spruce of height $$$2$$$ has its origin at point $$$(1, 2)$$$, the second spruce of height $$$1$$$ has its origin at point $$$(1, 2)$$$, the third spruce of height $$$1$$$ has its origin at point $$$(2, 1)$$$, the fourth spruce of height $$$1$$$ has its origin at point $$$(2, 2)$$$, the fifth spruce of height $$$1$$$ has its origin at point $$$(2, 3)$$$.

In the second test case the first spruce of height $$$1$$$ has its origin at point $$$(1, 2)$$$, the second spruce of height $$$1$$$ has its origin at point $$$(2, 1)$$$, the third spruce of height $$$1$$$ has its origin at point $$$(2, 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
Barbara was late for her math class so as a punishment the teacher made her solve the task on a sheet of paper. Barbara looked at the sheet of paper and only saw $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$ without any mathematical symbols. The teacher explained to Barbara that she has to place the available symbols between the numbers in a way that would make the resulting expression's value as large as possible. To find out which symbols were available the teacher has given Barbara a string $$$s$$$ which contained that information.

It's easy to notice that Barbara has to place $$$n - 1$$$ symbols between numbers in total. The expression must start with a number and all symbols must be allowed (i.e. included in $$$s$$$). Note that multiplication takes precedence over addition or subtraction, addition and subtraction have the same priority and performed from left to right. Help Barbara and create the required expression!

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the amount of numbers on the paper.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

The third line of the input contains the string $$$s$$$ ($$$1 \le |s| \le 3$$$) — symbols allowed in the expression. It is guaranteed that the string may only consist of symbols "-", "+" and "*". It is also guaranteed that all symbols in the string are distinct.

## Output Format
Print $$$n$$$ numbers separated by $$$n - 1$$$ symbols — a mathematical expression with the greatest result. If there are multiple equally valid results — output any one of them.

## Examples
```input
3
2 2 0
+-*
```
```output
2*2-0
```
-----
```input
4
2 1 1 2
+*
```
```output
2+1+1+2
```

## Note
The following answers also fit the first example: "2+2+0", "2+2-0", "2*2+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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two positive (greater than zero) integers $$$x$$$ and $$$y$$$. There is a variable $$$k$$$ initially set to $$$0$$$.

You can perform the following two types of operations:

- add $$$1$$$ to $$$k$$$ (i. e. assign $$$k := k + 1$$$);
- add $$$x \cdot 10^{p}$$$ to $$$k$$$ for some non-negative $$$p$$$ (i. e. assign $$$k := k + x \cdot 10^{p}$$$ for some $$$p \ge 0$$$).

Find the minimum number of operations described above to set the value of $$$k$$$ to $$$y$$$.

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

Each test case consists of one line containing two integer $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 10^9$$$).

## Output Format
For each test case, print one integer — the minimum number of operations to set the value of $$$k$$$ to $$$y$$$.

## Examples
```input
3
2 7
3 42
25 1337
```
```output
4
5
20
```

## Note
In the first test case you can use the following sequence of operations:

1. add $$$1$$$;
2. add $$$2 \cdot 10^0 = 2$$$;
3. add $$$2 \cdot 10^0 = 2$$$;
4. add $$$2 \cdot 10^0 = 2$$$.

In the second test case you can use the following sequence of operations:

1. add $$$3 \cdot 10^1 = 30$$$;
2. add $$$3 \cdot 10^0 = 3$$$;
3. add $$$3 \cdot 10^0 = 3$$$;
4. add $$$3 \cdot 10^0 = 3$$$;
5. add $$$3 \cdot 10^0 = 3$$$.

Now solve the problem and return the code.