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

# Problem
An integer array $$$a_1, a_2, \ldots, a_n$$$ is being transformed into an array of lowercase English letters using the following prodecure:

While there is at least one number in the array:

- Choose any number $$$x$$$ from the array $$$a$$$, and any letter of the English alphabet $$$y$$$.
- Replace all occurrences of number $$$x$$$ with the letter $$$y$$$.

For example, if we initially had an array $$$a = [2, 3, 2, 4, 1]$$$, then we could transform it the following way:

- Choose the number $$$2$$$ and the letter c. After that $$$a = [c, 3, c, 4, 1]$$$.
- Choose the number $$$3$$$ and the letter a. After that $$$a = [c, a, c, 4, 1]$$$.
- Choose the number $$$4$$$ and the letter t. After that $$$a = [c, a, c, t, 1]$$$.
- Choose the number $$$1$$$ and the letter a. After that $$$a = [c, a, c, t, a]$$$.

After the transformation all letters are united into a string, in our example we get the string "cacta".

Having the array $$$a$$$ and the string $$$s$$$ determine if the string $$$s$$$ could be got from the array $$$a$$$ after the described transformation?

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

Then the description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the array $$$a$$$ and the string $$$s$$$.

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

The third line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

## Output Format
For each test case, output "YES", if we can get the string $$$s$$$ from the array $$$a$$$, and "NO" otherwise. You can output each letter in any case.

## Examples
```input
7
5
2 3 2 4 1
cacta
1
50
a
2
11 22
ab
4
1 2 2 1
aaab
5
1 2 3 2 1
aaaaa
6
1 10 2 9 3 8
azzfdb
7
1 2 3 4 1 1 2
abababb
```
```output
YES
YES
YES
NO
YES
YES
NO
```

## Note
The first test case corresponds to the sample described in the statement.

In the second test case we can choose the number $$$50$$$ and the letter a.

In the third test case we can choose the number $$$11$$$ and the letter a, after that $$$a = [a, 22]$$$. Then we choose the number $$$22$$$ and the letter b and get $$$a = [a, b]$$$.

In the fifth test case we can change all numbers one by one to the letter a.

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

# Problem
You are given $$$n$$$ of integers $$$a_1, a_2, \ldots, a_n$$$. Process $$$q$$$ queries of two types:

- query of the form "0 $$$x_j$$$": add the value $$$x_j$$$ to all even elements of the array $$$a$$$,
- query of the form "1 $$$x_j$$$": add the value $$$x_j$$$ to all odd elements of the array $$$a$$$.

Note that when processing the query, we look specifically at the odd/even value of $$$a_i$$$, not its index.

After processing each query, print the sum of the elements of the array $$$a$$$.

Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

## Input Format
The first line of the input contains an 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 two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n$$$, $$$q \leq 10^5$$$) — the length of array $$$a$$$ and the number of queries.

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$$$) — elements of the array $$$a$$$.

The following $$$q$$$ lines contain queries as two integers $$$type_j$$$ and $$$x_j$$$ $$$(0 \leq type_j \leq 1$$$, $$$1 \leq x_j \leq 10^4$$$).

It is guaranteed that the sum of values $$$n$$$ over all test cases in a test does not exceed $$$10^5$$$. Similarly, the sum of values $$$q$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, print $$$q$$$ numbers: the sum of the elements of the array $$$a$$$ after processing a query.

## Examples
```input
4
1 1
1
1 1
3 3
1 2 4
0 2
1 3
0 5
6 7
1 3 2 4 10 48
1 6
0 5
0 4
0 5
1 3
0 12
0 1
6 7
1000000000 1000000000 1000000000 11 15 17
0 17
1 10000
1 51
0 92
0 53
1 16
0 1
```
```output
2
11
14
29
80
100
100
100
118
190
196
3000000094
3000060094
3000060400
3000060952
3000061270
3000061366
3000061366
```

## Note
In the first test case, the array $$$a = [2]$$$ after the first query.

In the third test case, the array $$$a$$$ is modified as follows: $$$[1, 3, 2, 4, 10, 48]$$$ $$$\rightarrow$$$ $$$[7, 9, 2, 4, 10, 48]$$$ $$$\rightarrow$$$ $$$[7, 9, 7, 9, 15, 53]$$$ $$$\rightarrow$$$ $$$[7, 9, 7, 9, 15, 53]$$$ $$$\rightarrow$$$ $$$[10, 12, 10, 12, 18, 56]$$$ $$$\rightarrow$$$ $$$[22, 24, 22, 24, 30, 68]$$$ $$$\rightarrow$$$ $$$[23, 25, 23, 25, 31, 69]$$$.

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

# Problem
You are given an integer $$$n$$$. Find a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ such that $$$1 \leq a_i \leq 10^9$$$ for all $$$i$$$ and $$$$$$a_1 \oplus a_2 \oplus \dots \oplus a_n = \frac{a_1 + a_2 + \dots + a_n}{n},$$$$$$ where $$$\oplus$$$ represents the bitwise XOR.

It can be proven that there exists a sequence of integers that satisfies all the conditions above.

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

The first and only line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the sequence you have to find.

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ satisfying the conditions in the statement.

If there are several possible answers, you can output any of them.

## Examples
```input
3
1
4
3
```
```output
69
13 2 8 1
7 7 7
```

## Note
In the first test case, $$$69 = \frac{69}{1} = 69$$$.

In the second test case, $$$13 \oplus 2 \oplus 8 \oplus 1 = \frac{13 + 2 + 8 + 1}{4} = 6$$$.

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

# Problem
Given two integers $$$n$$$ and $$$x$$$, a permutation$$$^{\dagger}$$$ $$$p$$$ of length $$$n$$$ is called funny if $$$p_i$$$ is a multiple of $$$i$$$ for all $$$1 \leq i \leq n - 1$$$, $$$p_n = 1$$$, and $$$p_1 = x$$$.

Find the lexicographically minimal$$$^{\ddagger}$$$ funny permutation, or report that no such permutation exists.

$$$^{\dagger}$$$ A permutation of length $$$n$$$ is an array consisting of each of the integers from $$$1$$$ to $$$n$$$ exactly once.

$$$^{\ddagger}$$$ Let $$$a$$$ and $$$b$$$ be permutations of length $$$n$$$. Then $$$a$$$ is lexicographically smaller than $$$b$$$ if in the first position $$$i$$$ where $$$a$$$ and $$$b$$$ differ, $$$a_i < b_i$$$. A permutation is lexicographically minimal if it is lexicographically smaller than all other permutations.

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

The only line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$; $$$1 < x \leq n$$$).

The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, if the answer exists, output $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the lexicographically minimal funny permutation $$$p$$$. Otherwise, output $$$-1$$$.

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

## Note
In the first test case, the permutation $$$[3,2,1]$$$ satisfies all the conditions: $$$p_1=3$$$, $$$p_3=1$$$, and:

- $$$p_1=3$$$ is a multiple of $$$1$$$.
- $$$p_2=2$$$ is a multiple of $$$2$$$.

In the second test case, the permutation $$$[2,4,3,1]$$$ satisfies all the conditions: $$$p_1=2$$$, $$$p_4=1$$$, and:

- $$$p_1=2$$$ is a multiple of $$$1$$$.
- $$$p_2=4$$$ is a multiple of $$$2$$$.
- $$$p_3=3$$$ is a multiple of $$$3$$$.

We can show that these permutations are lexicographically minimal.

No such permutations exist in the third test case.

Now solve the problem and return the code.