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
You are given an array of positive integers $$$a_1, a_2, \ldots, a_n$$$.

Make the product of all the numbers in the array (that is, $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n$$$) divisible by $$$2^n$$$.

You can perform the following operation as many times as you like:

- select an arbitrary index $$$i$$$ ($$$1 \leq i \leq n$$$) and replace the value $$$a_i$$$ with $$$a_i=a_i \cdot i$$$.

You cannot apply the operation repeatedly to a single index. In other words, all selected values of $$$i$$$ must be different.

Find the smallest number of operations you need to perform to make the product of all the elements in the array divisible by $$$2^n$$$. Note that such a set of operations does not always exist.

## Input Format
The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4$$$) — the number test cases.

Then the descriptions of the input data sets follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of array $$$a$$$.

The second line of each test case contains exactly $$$n$$$ integers: $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ values over all test cases in a test does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print the least number of operations to make the product of all numbers in the array divisible by $$$2^n$$$. If the answer does not exist, print -1.

## Examples
```input
6
1
2
2
3 2
3
10 6 11
4
13 17 1 1
5
1 1 12 1 1
6
20 7 14 18 3 5
```
```output
0
1
1
-1
2
1
```

## Note
In the first test case, the product of all elements is initially $$$2$$$, so no operations needed.

In the second test case, the product of elements initially equals $$$6$$$. We can apply the operation for $$$i = 2$$$, and then $$$a_2$$$ becomes $$$2\cdot2=4$$$, and the product of numbers becomes $$$3\cdot4=12$$$, and this product of numbers is divided by $$$2^n=2^2=4$$$.

In the fourth test case, even if we apply all possible operations, we still cannot make the product of numbers divisible by $$$2^n$$$  — it will be $$$(13\cdot1)\cdot(17\cdot2)\cdot(1\cdot3)\cdot(1\cdot4)=5304$$$, which does not divide by $$$2^n=2^4=16$$$.

In the fifth test case, we can apply operations for $$$i = 2$$$ and $$$i = 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
This is an easy version of the problem. The only difference between an easy and a hard version is the constraints on $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$.

You are given $$$4$$$ positive integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ with $$$a < c$$$ and $$$b < d$$$. Find any pair of numbers $$$x$$$ and $$$y$$$ that satisfies the following conditions:

- $$$a < x \leq c$$$, $$$b < y \leq d$$$,
- $$$x \cdot y$$$ is divisible by $$$a \cdot b$$$.

Note that required $$$x$$$ and $$$y$$$ may not exist.

## Input Format
The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10$$$), the number of test cases.

The descriptions of the test cases follow.

The only line of each test case contains four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ ($$$1 \leq a < c \leq 10^5$$$, $$$1 \leq b < d \leq 10^5$$$).

## Output Format
For each test case print a pair of numbers $$$a < x \leq c$$$ and $$$b < y \leq d$$$ such that $$$x \cdot y$$$ is divisible by $$$a \cdot b$$$. If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.

## Examples
```input
5
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66
```
```output
2 2
4 6
12 12
-1 -1
-1 -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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
This is an hard version of the problem. The only difference between an easy and a hard version is the constraints on $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$.

You are given $$$4$$$ positive integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ with $$$a < c$$$ and $$$b < d$$$. Find any pair of numbers $$$x$$$ and $$$y$$$ that satisfies the following conditions:

- $$$a < x \leq c$$$, $$$b < y \leq d$$$,
- $$$x \cdot y$$$ is divisible by $$$a \cdot b$$$.

Note that required $$$x$$$ and $$$y$$$ may not exist.

## Input Format
The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10$$$), the number of test cases.

The descriptions of the test cases follow.

The only line of each test case contains four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ ($$$1 \leq a < c \leq 10^9$$$, $$$1 \leq b < d \leq 10^9$$$).

## Output Format
For each test case print a pair of numbers $$$a < x \leq c$$$ and $$$b < y \leq d$$$ such that $$$x \cdot y$$$ is divisible by $$$a \cdot b$$$. If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.

## Examples
```input
10
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66
1024 729 373248 730
1024 729 373247 730
5040 40320 40319 1000000000
999999999 999999999 1000000000 1000000000
268435456 268435456 1000000000 1000000000
```
```output
2 2
4 6
12 12
-1 -1
-1 -1
373248 730
-1 -1
15120 53760
-1 -1
536870912 536870912
```

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 permutation $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$ of numbers $$$0, \ldots, n - 1$$$. Count the number of subsegments $$$1 \leq l \leq r \leq n$$$ of this permutation such that $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$.

$$$mex$$$ of $$$S$$$ is the smallest non-negative integer that does not occur in $$$S$$$. For example:

- $$$mex({0, 1, 2, 3}) = 4$$$
- $$$mex({0, 4, 1, 3}) = 2$$$
- $$$mex({5, 4, 0, 1, 2}) = 3$$$

$$$med$$$ of the set $$$S$$$ is the median of the set, i.e. the element that, after sorting the elements in non-decreasing order, will be at position number $$$\left \lfloor{ \frac{|S| + 1}{2} } \right \rfloor$$$ (array elements are numbered starting from $$$1$$$ and here $$$\left \lfloor{v} \right \rfloor$$$ denotes rounding $$$v$$$ down.). For example:

- $$$med({0, 1, 2, 3}) = 1$$$
- $$$med({0, 4, 1, 3}) = 1$$$
- $$$med({5, 4, 0, 1, 2}) = 2$$$

A sequence of $$$n$$$ numbers is called a permutation if it contains all the numbers from $$$0$$$ to $$$n - 1$$$ exactly once.

## Input Format
The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4$$$), the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the permutation $$$p$$$.

The second line of each test case contains exactly $$$n$$$ integers: $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \leq p_i \leq n - 1$$$), elements of permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case print the answer in a single line: the number of subsegments $$$1 \leq l \leq r \leq n$$$ of this permutation such that $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$.

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

## Note
The first test case contains exactly one subsegment and $$$mex({0}) = 1 > med({0}) = 0$$$ on it.

In the third test case, on the following subsegments: $$$[1, 0]$$$, $$$[0]$$$, $$$[1, 0, 2]$$$ and $$$[0, 2]$$$, $$$mex$$$ is greater than $$$med$$$.

In the fourth test case, on the following subsegments: $$$[0, 2]$$$, $$$[0]$$$, $$$[0, 2, 1]$$$ and $$$[0, 2, 1, 3]$$$, $$$mex$$$ greater than $$$med$$$.

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
A binary string is a string consisting only of the characters 0 and 1. You are given a binary string $$$s$$$.

For some non-empty substring$$$^\dagger$$$ $$$t$$$ of string $$$s$$$ containing $$$x$$$ characters 0 and $$$y$$$ characters 1, define its cost as:

- $$$x \cdot y$$$, if $$$x > 0$$$ and $$$y > 0$$$;
- $$$x^2$$$, if $$$x > 0$$$ and $$$y = 0$$$;
- $$$y^2$$$, if $$$x = 0$$$ and $$$y > 0$$$.

Given a binary string $$$s$$$ of length $$$n$$$, find the maximum cost across all its non-empty substrings.

$$$^\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the maximum cost across all substrings.

## Examples
```input
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0
```
```output
9
12
16
12
9
1
```

## Note
In the first test case, we can take a substring $$$111$$$. It contains $$$3$$$ characters 1 and $$$0$$$ characters 0. So $$$a = 3$$$, $$$b = 0$$$ and its cost is $$$3^2 = 9$$$.

In the second test case, we can take the whole string. It contains $$$4$$$ characters 1 and $$$3$$$ characters 0. So $$$a = 4$$$, $$$b = 3$$$ and its cost is $$$4 \cdot 3 = 12$$$.

In the third test case, we can can take a substring $$$1111$$$ and its cost is $$$4^2 = 16$$$.

In the fourth test case, we can take the whole string and cost is $$$4 \cdot 3 = 12$$$.

In the fifth test case, we can take a substring $$$000$$$ and its cost is $$$3 \cdot 3 = 9$$$.

In the sixth test case, we can only take the substring $$$0$$$ and its cost is $$$1 \cdot 1 = 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
You are given two integers $$$n$$$ and $$$m$$$ and an array $$$a$$$ of $$$n$$$ integers. For each $$$1 \le i \le n$$$ it holds that $$$1 \le a_i \le m$$$.

Your task is to count the number of different arrays $$$b$$$ of length $$$n$$$ such that:

- $$$1 \le b_i \le m$$$ for each $$$1 \le i \le n$$$, and
- $$$\gcd(b_1,b_2,b_3,...,b_i) = a_i$$$ for each $$$1 \le i \le n$$$.

Here $$$\gcd(a_1,a_2,\dots,a_i)$$$ denotes the greatest common divisor (GCD) of integers $$$a_1,a_2,\ldots,a_i$$$.

Since this number can be too large, print it modulo $$$998\,244\,353$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — the length of the array $$$a$$$ and the maximum possible value of the element.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of different arrays satisfying the conditions above. Since this number can be large, print it modulo $$$998\,244\,353$$$.

## Examples
```input
5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2
```
```output
3
1
0
595458194
200000000
```

## Note
In the first test case, the possible arrays $$$b$$$ are:

- $$$[4,2,1]$$$;
- $$$[4,2,3]$$$;
- $$$[4,2,5]$$$.

In the second test case, the only array satisfying the demands is $$$[1,1]$$$.

In the third test case, it can be proven no such array exists.

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

# Problem
Everyone was happy coding, until suddenly a power shortage happened and the best competitive programming site went down. Fortunately, a system administrator bought some new equipment recently, including some UPSs. Thus there are some servers that are still online, but we need all of them to be working in order to keep the round rated.

Imagine the servers being a binary string $$$s$$$ of length $$$n$$$. If the $$$i$$$-th server is online, then $$$s_i = 1$$$, and $$$s_i = 0$$$ otherwise.

A system administrator can do the following operation called electricity spread, that consists of the following phases:

- Select two servers at positions $$$1 \le i < j \le n$$$ such that both are online (i.e. $$$s_i=s_j=1$$$). The spread starts only from online servers.
- Check if we have enough power to make the spread. We consider having enough power if the number of turned on servers in range $$$[i, j]$$$ is at least the number of turned off servers in range $$$[i, j]$$$. More formally, check whether $$$2 \cdot (s_i + s_{i+1} + \ldots + s_j) \ge j - i + 1$$$.
- If the check is positive, turn on all the offline servers in range $$$[i, j]$$$. More formally, make $$$s_k := 1$$$ for all $$$k$$$ from $$$i$$$ to $$$j$$$.

We call a binary string $$$s$$$ of length $$$n$$$ rated if we can turn on all servers (i.e. make $$$s_i = 1$$$ for $$$1 \le i \le n$$$) using the electricity spread operation any number of times (possibly, $$$0$$$). Your task is to find the number of rated strings of length $$$n$$$ modulo $$$m$$$.

## Input Format
The first and only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5000$$$, $$$10 \le m \le 10^9$$$) — the length of the string and the required module.

## Output Format
Print a single integer — the number of rated binary strings of length $$$n$$$. Since this number can be large, print it modulo $$$m$$$.

## Examples
```input
2 100
```
```output
1
```
-----
```input
3 10
```
```output
2
```
-----
```input
4 3271890
```
```output
4
```
-----
```input
17 123456
```
```output
32347
```

## Note
In the first example, the only rated string is 11. So the answer is $$$1$$$.

In the second example, the rated strings are:

- 111;
- 101, because we can perform an operation with $$$i = 1$$$ and $$$j = 3$$$.

In the third sample, the rated strings are:

- 1001;
- 1111;
- 1011;
- 1101.

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a binary string $$$s$$$ of length $$$n$$$. We define a maximal substring as a substring that cannot be extended while keeping all elements equal. For example, in the string $$$11000111$$$ there are three maximal substrings: $$$11$$$, $$$000$$$ and $$$111$$$.

In one operation, you can select two maximal adjacent substrings. Since they are maximal and adjacent, it's easy to see their elements must have different values. Let $$$a$$$ be the length of the sequence of ones and $$$b$$$ be the length of the sequence of zeros. Then do the following:

- If $$$a \ge b$$$, then replace $$$b$$$ selected zeros with $$$b$$$ ones.
- If $$$a < b$$$, then replace $$$a$$$ selected ones with $$$a$$$ zeros.

As an example, for $$$1110000$$$ we make it $$$0000000$$$, for $$$0011$$$ we make it $$$1111$$$. We call a string being good if it can be turned into $$$1111...1111$$$ using the aforementioned operation any number of times (possibly, zero). Find the number of good substrings among all $$$\frac{n(n+1)}{2}$$$ non-empty substrings of $$$s$$$.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.

The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that sum of $$$n$$$ across all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of good substrings.

## Examples
```input
4
6
100011
3
101
5
11111
6
010101
```
```output
8
5
15
18
```

## Note
Let's define a substring from index $$$l$$$ to index $$$r$$$ as $$$[l, r]$$$.

For the first test case, the good substrings are:

- $$$[1,1]$$$,
- $$$[1,2]$$$,
- $$$[3,6]$$$,
- $$$[4,5]$$$,
- $$$[4,6]$$$,
- $$$[5,5]$$$,
- $$$[5,6]$$$,
- $$$[6,6]$$$.

In the second test case, all substrings are good except $$$[2,2]$$$.

In the third test case, all substrings are good.

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
A palindrome is a string that reads the same backward as forward. For example, the strings $$$\texttt{z}$$$, $$$\texttt{aaa}$$$, $$$\texttt{aba}$$$, and $$$\texttt{abccba}$$$ are palindromes, but $$$\texttt{codeforces}$$$ and $$$\texttt{ab}$$$ are not.

The double of a string $$$s$$$ is obtained by writing each character twice. For example, the double of $$$\texttt{seeing}$$$ is $$$\texttt{sseeeeiinngg}$$$.

Given a string $$$s$$$, rearrange its double to form a palindrome. Output the rearranged string. It can be proven that such a rearrangement always exists.

## Input Format
The first line of input contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The only line of each test case contains a single string $$$s$$$ ($$$1 \leq |s| \leq 100$$$) consisting only of lowercase English letters.

Note that the sum of $$$|s|$$$ over all test cases is not bounded.

## Output Format
For each test case, output a palindromic string of length $$$2 \cdot |s|$$$ that is a rearrangement of the double of $$$s$$$.

## Examples
```input
4
a
sururu
errorgorn
anutforajaroftuna
```
```output
aa
suurruurruus
rgnororerrerorongr
aannuuttffoorraajjaarrooffttuunnaa
```

## Note
In the first test case, the double of $$$\texttt{a}$$$ is $$$\texttt{aa}$$$, which is already a palindrome.

In the second test case, the double of $$$\texttt{sururu}$$$ is $$$\texttt{ssuurruurruu}$$$. If we move the first $$$\texttt{s}$$$ to the end, we get $$$\texttt{suurruurruus}$$$, which is a palindrome.

In the third test case, the double of $$$\texttt{errorgorn}$$$ is $$$\texttt{eerrrroorrggoorrnn}$$$. We can rearrange the characters to form $$$\texttt{rgnororerrerorongr}$$$, which is a palindrome.

Now solve the problem and return the code.