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: 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 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
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.
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 three integers $$$n$$$, $$$a$$$, and $$$b$$$. Determine if there exist two permutations $$$p$$$ and $$$q$$$ of length $$$n$$$, for which the following conditions hold:

- The length of the longest common prefix of $$$p$$$ and $$$q$$$ is $$$a$$$.
- The length of the longest common suffix of $$$p$$$ and $$$q$$$ is $$$b$$$.

A permutation of length $$$n$$$ is an array containing each integer from $$$1$$$ to $$$n$$$ exactly once. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

The only line of each test case contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1\leq a,b\leq n\leq 100$$$).

## Output Format
For each test case, if such a pair of permutations exists, output "Yes"; otherwise, output "No". You can output each letter in any case (upper or lower).

## Examples
```input
4
1 1 1
2 1 2
3 1 1
4 1 1
```
```output
Yes
No
No
Yes
```

## Note
In the first test case, $$$[1]$$$ and $$$[1]$$$ form a valid pair.

In the second test case and the third case, we can show that such a pair of permutations doesn't exist.

In the fourth test case, $$$[1,2,3,4]$$$ and $$$[1,3,2,4]$$$ form a valid pair.

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
Define a cyclic sequence of size $$$n$$$ as an array $$$s$$$ of length $$$n$$$, in which $$$s_n$$$ is adjacent to $$$s_1$$$.

Muxii has a ring represented by a cyclic sequence $$$a$$$ of size $$$n$$$.

However, the ring itself hates equal adjacent elements. So if two adjacent elements in the sequence are equal at any time, one of them will be erased immediately. The sequence doesn't contain equal adjacent elements initially.

Muxii can perform the following operation until the sequence becomes empty:

- Choose an element in $$$a$$$ and erase it.

For example, if ring is $$$[1, 2, 4, 2, 3, 2]$$$, and Muxii erases element $$$4$$$, then ring would erase one of the elements equal to $$$2$$$, and the ring will become $$$[1, 2, 3, 2]$$$.

Muxii wants to find the maximum number of operations he could perform.

Note that in a ring of size $$$1$$$, its only element isn't considered adjacent to itself (so it's not immediately erased).

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

The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 100$$$) — the size of the cyclic sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) — the sequence itself.

It's guaranteed that $$$a_i\ne a_{i+1}$$$ for $$$1\leq i<n$$$.

It's guaranteed that $$$a_n\ne a_1$$$ when $$$n>1$$$.

## Output Format
For each test case, output a single integer — the maximum number of operations Muxii can perform.

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

## Note
In the first test case, you can erase the second element first, then erase the remaining elements one by one in any order. In total, you can perform the operation $$$4$$$ times. Note that if you erase the first element first, then the sequence will be turned into $$$[2,3,2]$$$ and then immediately become $$$[2,3]$$$.

In the second test case, you can erase the first element first, then the sequence becomes $$$[2,1]$$$. Then you can erase all remaining elements one by one in any order.

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 binary matrix $$$b$$$ (all elements of the matrix are $$$0$$$ or $$$1$$$) of $$$n$$$ rows and $$$n$$$ columns.

You need to construct a $$$n$$$ sets $$$A_1, A_2, \ldots, A_n$$$, for which the following conditions are satisfied:

- Each set is nonempty and consists of distinct integers between $$$1$$$ and $$$n$$$ inclusive.
- All sets are distinct.
- For all pairs $$$(i,j)$$$ satisfying $$$1\leq i, j\leq n$$$, $$$b_{i,j}=1$$$ if and only if $$$A_i\subsetneq A_j$$$. In other words, $$$b_{i, j}$$$ is $$$1$$$ if $$$A_i$$$ is a proper subset of $$$A_j$$$ and $$$0$$$ otherwise.

Set $$$X$$$ is a proper subset of set $$$Y$$$, if $$$X$$$ is a nonempty subset of $$$Y$$$, and $$$X \neq Y$$$.

It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist. Note that it doesn't mean that such $$$n$$$ sets exist for all possible inputs.

If there are multiple solutions, you can output any of them.

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

The first line contains a single integer $$$n$$$ ($$$1\le n\le 100$$$).

The following $$$n$$$ lines contain a binary matrix $$$b$$$, the $$$j$$$-th character of $$$i$$$-th line denotes $$$b_{i,j}$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist.

## Output Format
For each test case, output $$$n$$$ lines.

For the $$$i$$$-th line, first output $$$s_i$$$ $$$(1 \le s_i \le n)$$$  — the size of the set $$$A_i$$$. Then, output $$$s_i$$$ distinct integers from $$$1$$$ to $$$n$$$  — the elements of the set $$$A_i$$$.

If there are multiple solutions, you can output any of them.

It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist.

## Examples
```input
2
4
0001
1001
0001
0000
3
011
001
000
```
```output
3 1 2 3
2 1 3
2 2 4
4 1 2 3 4
1 1
2 1 2
3 1 2 3
```

## Note
In the first test case, we have $$$A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}$$$. Sets $$$A_1, A_2, A_3$$$ are proper subsets of $$$A_4$$$, and also set $$$A_2$$$ is a proper subset of $$$A_1$$$. No other set is a proper subset of any other set.

In the second test case, we have $$$A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}$$$. $$$A_1$$$ is a proper subset of $$$A_2$$$ and $$$A_3$$$, and $$$A_2$$$ is a proper subset of $$$A_3$$$.

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
Let $$$f(x,y)$$$ be the number of carries of $$$x+y$$$ in binary (i. e. $$$f(x,y)=g(x)+g(y)-g(x+y)$$$, where $$$g(x)$$$ is the number of ones in the binary representation of $$$x$$$).

Given two integers $$$n$$$ and $$$k$$$, find the number of ordered pairs $$$(a,b)$$$ such that $$$0 \leq a,b < 2^n$$$, and $$$f(a,b)$$$ equals $$$k$$$. Note that for $$$a\ne b$$$, $$$(a,b)$$$ and $$$(b,a)$$$ are considered as two different pairs.

As this number may be large, output it modulo $$$10^9+7$$$.

## Input Format
The only line of each test contains two integers $$$n$$$ and $$$k$$$ ($$$0\leq k<n\leq 10^6$$$).

## Output Format
Output a single integer  — the answer modulo $$$10^9+7$$$.

## Examples
```input
3 1
```
```output
15
```
-----
```input
3 0
```
```output
27
```
-----
```input
998 244
```
```output
573035660
```

## Note
Here are some examples for understanding carries:

$$$$$$ \begin{aligned} &\begin{array}{r} 1_{\ \ }1_{\ \ }1\\ +\ _{1}1_{\ \ }0_{\ \ }0\\ \hline \ 1_{\ \ }0_{\ \ }1_{\ \ }1 \end{array} &\begin{array}{r} \ 1_{\ \ }0_{\ \ }1\\ +\ _{\ \ }0_{\ \ }0_{1}1\\ \hline \ 0_{\ \ }1_{\ \ }1_{\ \ }0 \end{array} & &\begin{array}{r} \ 1_{\ \ }0_{\ \ }1\\ +\ _{1}0_{1}1_{1}1\\ \hline \ 1_{\ \ }0_{\ \ }0_{\ \ }0 \end{array} \end{aligned} $$$$$$

So $$$f(7,4)=1$$$, $$$f(5,1)=1$$$ and $$$f(5,3)=3$$$.

In the first test case, all the pairs meeting the constraints are $$$(1,1),(1,5),(2,2),(2,3),(3,2),(4,4),(4,5),(4,6),(4,7),(5,1),(5,4),(5,6),(6,4),(6,5),(7,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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

Let's call an array $$$a$$$ of odd length $$$2m+1$$$ (with $$$m \ge 1$$$) bad, if element $$$a_{m+1}$$$ is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at $$$m+1$$$-st position remains the same.

Let's call a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$ anti-median, if every its subarray of odd length $$$\ge 3$$$ is not bad.

You are already given values of some elements of the permutation. Find the number of ways to set unknown values to obtain an anti-median permutation. As this number can be very large, find it modulo $$$10^9+7$$$.

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

The first line of each test case contains a single integer $$$n$$$ $$$(2 \le n \le 1000)$$$  — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, or $$$p_i = -1$$$)  — the elements of the permutation. If $$$p_i \neq -1$$$, it's given, else it's unknown. It's guaranteed that if for some $$$i \neq j$$$ holds $$$p_i \neq -1, p_j \neq -1$$$, then $$$p_i \neq p_j$$$.

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

## Output Format
For each test case, output a single integer  — the number of ways to set unknown values to obtain an anti-median permutation, modulo $$$10^9+7$$$.

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

## Note
In the first test case, both $$$[1, 2]$$$ and $$$[2, 1]$$$ are anti-median.

In the second test case, permutations $$$[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$$$ are anti-median. The remaining two permutations, $$$[1, 2, 3]$$$, $$$[3, 2, 1]$$$, are bad arrays on their own, as their median, $$$2$$$, is in their middle.

In the third test case, $$$[1, 2, 3, 4]$$$ isn't anti-median, as it contains bad subarray $$$[1, 2, 3]$$$.

In the fourth test case, the only anti-median array you can get is $$$[5, 6, 3, 4, 1, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

Let's call an array $$$a$$$ of odd length $$$2m+1$$$ (with $$$m \ge 1$$$) bad, if element $$$a_{m+1}$$$ is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at $$$m+1$$$-st position remains the same.

Let's call a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$ anti-median, if every its subarray of odd length $$$\ge 3$$$ is not bad.

You are already given values of some elements of the permutation. Find the number of ways to set unknown values to obtain an anti-median permutation. As this number can be very large, find it modulo $$$10^9+7$$$.

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

The first line of each test case contains a single integer $$$n$$$ $$$(2 \le n \le 10^6)$$$  — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, or $$$p_i = -1$$$)  — the elements of the permutation. If $$$p_i \neq -1$$$, it's given, else it's unknown. It's guaranteed that if for some $$$i \neq j$$$ holds $$$p_i \neq -1, p_j \neq -1$$$, then $$$p_i \neq p_j$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case, output a single integer  — the number of ways to set unknown values to obtain an anti-median permutation, modulo $$$10^9+7$$$.

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

## Note
In the first test case, both $$$[1, 2]$$$ and $$$[2, 1]$$$ are anti-median.

In the second test case, permutations $$$[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$$$ are anti-median. The remaining two permutations, $$$[1, 2, 3]$$$, $$$[3, 2, 1]$$$, are bad arrays on their own, as their median, $$$2$$$, is in their middle.

In the third test case, $$$[1, 2, 3, 4]$$$ isn't anti-median, as it contains bad subarray $$$[1, 2, 3]$$$.

In the fourth test case, the only anti-median array you can get is $$$[5, 6, 3, 4, 1, 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
Petya and his friend, robot Petya++, like to solve exciting math problems.

One day Petya++ came up with the numbers $$$n$$$ and $$$x$$$ and wrote the following equality on the board: $$$$$$n\ \&\ (n+1)\ \&\ \dots\ \&\ m = x,$$$$$$ where $$$\&$$$ denotes the bitwise AND operation. Then he suggested his friend Petya find such a minimal $$$m$$$ ($$$m \ge n$$$) that the equality on the board holds.

Unfortunately, Petya couldn't solve this problem in his head and decided to ask for computer help. He quickly wrote a program and found the answer.

Can you solve this difficult problem?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2000$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$, $$$x$$$ ($$$0\le n, x \le 10^{18}$$$).

## Output Format
For every test case, output the smallest possible value of $$$m$$$ such that equality holds.

If the equality does not hold for any $$$m$$$, print $$$-1$$$ instead.

We can show that if the required $$$m$$$ exists, it does not exceed $$$5 \cdot 10^{18}$$$.

## Examples
```input
5
10 8
10 10
10 42
20 16
1000000000000000000 0
```
```output
12
10
-1
24
1152921504606846976
```

## Note
In the first example, $$$10\ \&\ 11 = 10$$$, but $$$10\ \&\ 11\ \&\ 12 = 8$$$, so the answer is $$$12$$$.

In the second example, $$$10 = 10$$$, so the answer is $$$10$$$.

In the third example, we can see that the required $$$m$$$ does not exist, so we have to print $$$-1$$$.

Now solve the problem and return the code.