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 a string $$$s$$$, consisting only of characters '0' or '1'. Let $$$|s|$$$ be the length of $$$s$$$.

You are asked to choose some integer $$$k$$$ ($$$k > 0$$$) and find a sequence $$$a$$$ of length $$$k$$$ such that:

- $$$1 \le a_1 < a_2 < \dots < a_k \le |s|$$$;
- $$$a_{i-1} + 1 < a_i$$$ for all $$$i$$$ from $$$2$$$ to $$$k$$$.

The characters at positions $$$a_1, a_2, \dots, a_k$$$ are removed, the remaining characters are concatenated without changing the order. So, in other words, the positions in the sequence $$$a$$$ should not be adjacent.

Let the resulting string be $$$s'$$$. $$$s'$$$ is called sorted if for all $$$i$$$ from $$$2$$$ to $$$|s'|$$$ $$$s'_{i-1} \le s'_i$$$.

Does there exist such a sequence $$$a$$$ that the resulting string $$$s'$$$ is sorted?

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

Then the descriptions of $$$t$$$ testcases follow.

The only line of each testcase contains a string $$$s$$$ ($$$2 \le |s| \le 100$$$). Each character is either '0' or '1'.

## Output Format
For each testcase print "YES" if there exists a sequence $$$a$$$ such that removing the characters at positions $$$a_1, a_2, \dots, a_k$$$ and concatenating the parts without changing the order produces a sorted string.

Otherwise, print "NO".

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

## Examples
```input
5
10101011011
0000
11111
110
1100
```
```output
YES
YES
YES
YES
NO
```

## Note
In the first testcase you can choose a sequence $$$a=[1,3,6,9]$$$. Removing the underlined letters from "10101011011" will produce a string "0011111", which is sorted.

In the second and the third testcases the sequences are already sorted.

In the fourth testcase you can choose a sequence $$$a=[3]$$$. $$$s'=$$$ "11", which is sorted.

In the fifth testcase there is no way to choose a sequence $$$a$$$ such that $$$s'$$$ is sorted.

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given three positive (greater than zero) integers $$$c$$$, $$$d$$$ and $$$x$$$.

You have to find the number of pairs of positive integers $$$(a, b)$$$ such that equality $$$c \cdot lcm(a, b) - d \cdot gcd(a, b) = x$$$ holds. Where $$$lcm(a, b)$$$ is the least common multiple of $$$a$$$ and $$$b$$$ and $$$gcd(a, b)$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$.

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

Each test case consists of one line containing three integer $$$c$$$, $$$d$$$ and $$$x$$$ ($$$1 \le c, d, x \le 10^7$$$).

## Output Format
For each test case, print one integer — the number of pairs ($$$a, b$$$) such that the above equality holds.

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

## Note
In the first example, the correct pairs are: ($$$1, 4$$$), ($$$4,1$$$), ($$$3, 6$$$), ($$$6, 3$$$).

In the second example, the correct pairs are: ($$$1, 2$$$), ($$$2, 1$$$), ($$$3, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$k$$$ and an undirected tree, consisting of $$$n$$$ vertices.

The length of a simple path (a path in which each vertex appears at most once) between some pair of vertices is the number of edges in this path. A diameter of a tree is the maximum length of a simple path between all pairs of vertices of this tree.

You are about to remove a set of edges from the tree. The tree splits into multiple smaller trees when the edges are removed. The set of edges is valid if all the resulting trees have diameter less than or equal to $$$k$$$.

Two sets of edges are different if there is an edge such that it appears in only one of the sets.

Count the number of valid sets of edges modulo $$$998\,244\,353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 5000$$$, $$$0 \le k \le n - 1$$$) — the number of vertices of the tree and the maximum allowed diameter, respectively.

Each of the next $$$n-1$$$ lines contains a description of an edge: two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \neq u$$$).

The given edges form a tree.

## Output Format
Print a single integer — the number of valid sets of edges modulo $$$998\,244\,353$$$.

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

## Note
In the first example the diameter of the given tree is already less than or equal to $$$k$$$. Thus, you can choose any set of edges to remove and the resulting trees will have diameter less than or equal to $$$k$$$. There are $$$2^3$$$ sets, including the empty one.

In the second example you have to remove the only edge. Otherwise, the diameter will be $$$1$$$, which is greater than $$$0$$$.

Here are the trees for the third and the fourth examples:

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: 6.0 seconds
Memory limit: 512.0 MB

# Problem
In the house where Krosh used to live, he had $$$n$$$ cupboards standing in a line, the $$$i$$$-th cupboard had the height of $$$h_i$$$. Krosh moved recently, but he wasn't able to move the cupboards with him. Now he wants to buy $$$n$$$ new cupboards so that they look as similar to old ones as possible.

Krosh does not remember the exact heights of the cupboards, but for every three consecutive cupboards he remembers the height difference between the tallest and the shortest of them. In other words, if the cupboards' heights were $$$h_1, h_2, \ldots, h_n$$$, then Krosh remembers the values $$$w_i = \max(h_{i}, h_{i + 1}, h_{i + 2}) - \min(h_{i}, h_{i + 1}, h_{i + 2})$$$ for all $$$1 \leq i \leq n - 2$$$.

Krosh wants to buy such $$$n$$$ cupboards that all the values $$$w_i$$$ remain the same. Help him determine the required cupboards' heights, or determine that he remembers something incorrectly and there is no suitable sequence of heights.

## Input Format
The first line contains two integers $$$n$$$ and $$$C$$$ ($$$3 \leq n \leq 10^6$$$, $$$0 \leq C \leq 10^{12}$$$) — the number of cupboards and the limit on possible $$$w_i$$$.

The second line contains $$$n - 2$$$ integers $$$w_1, w_2, \ldots, w_{n - 2}$$$ ($$$0 \leq w_i \leq C$$$) — the values defined in the statement.

## Output Format
If there is no suitable sequence of $$$n$$$ cupboards, print "NO".

Otherwise print "YES" in the first line, then in the second line print $$$n$$$ integers $$$h'_1, h'_2, \ldots, h'_n$$$ ($$$0 \le h'_i \le 10^{18}$$$) — the heights of the cupboards to buy, from left to right.

We can show that if there is a solution, there is also a solution satisfying the constraints on heights.

If there are multiple answers, print any.

## Examples
```input
7 20
4 8 12 16 20
```
```output
YES
4 8 8 16 20 4 0
```
-----
```input
11 10
5 7 2 3 4 5 2 1 8
```
```output
YES
1 1 6 8 6 5 2 0 0 1 8
```
-----
```input
6 9
1 6 9 0
```
```output
NO
```

## Note
Consider the first example:

- $$$w_1 = \max(4, 8, 8) - \min(4, 8, 8) = 8 - 4 = 4$$$
- $$$w_2 = \max(8, 8, 16) - \min(8, 8, 16) = 16 - 8 = 8$$$
- $$$w_3 = \max(8, 16, 20) - \min(8, 16, 20) = 20 - 8 = 12$$$
- $$$w_4 = \max(16, 20, 4) - \min(16, 20, 4) = 20 - 4 = 16$$$
- $$$w_5 = \max(20, 4, 0) - \min(20, 4, 0) = 20 - 0 = 20$$$

There are other possible solutions, for example, the following: $$$0, 1, 4, 9, 16, 25, 36$$$.

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 an array $$$a$$$ of length $$$n$$$, tell us whether it has a non-empty subsequence such that the product of its elements is not a perfect square.

A sequence $$$b$$$ is a subsequence of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deleting some (possibly zero) elements.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 10^4$$$) — the elements of the array $$$a$$$.

## Output Format
If there's a subsequence of $$$a$$$ whose product isn't a perfect square, print "YES". Otherwise, print "NO".

## Examples
```input
2
3
1 5 4
2
100 10000
```
```output
YES
NO
```

## Note
In the first example, the product of the whole array ($$$20$$$) isn't a perfect square.

In the second example, all subsequences have a perfect square product.

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
Baby Badawy's first words were "AND 0 SUM BIG", so he decided to solve the following problem. Given two integers $$$n$$$ and $$$k$$$, count the number of arrays of length $$$n$$$ such that:

- all its elements are integers between $$$0$$$ and $$$2^k-1$$$ (inclusive);
- the bitwise AND of all its elements is $$$0$$$;
- the sum of its elements is as large as possible.

Since the answer can be very large, print its remainder when divided by $$$10^9+7$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases you need to solve.

Each test case consists of a line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le k \le 20$$$).

## Output Format
For each test case, print the number of arrays satisfying the conditions. Since the answer can be very large, print its remainder when divided by $$$10^9+7$$$.

## Examples
```input
2
2 2
100000 20
```
```output
4
226732710
```

## Note
In the first example, the $$$4$$$ arrays are:

- $$$[3,0]$$$,
- $$$[0,3]$$$,
- $$$[1,2]$$$,
- $$$[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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Now you get Baby Ehab's first words: "Given an integer $$$n$$$, find the longest subsequence of $$$[1,2, \ldots, n-1]$$$ whose product is $$$1$$$ modulo $$$n$$$." Please solve the problem.

A sequence $$$b$$$ is a subsequence of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deleting some (possibly all) elements. The product of an empty subsequence is equal to $$$1$$$.

## Input Format
The only line contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

## Output Format
The first line should contain a single integer, the length of the longest subsequence.

The second line should contain the elements of the subsequence, in increasing order.

If there are multiple solutions, you can print any.

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

## Note
In the first example, the product of the elements is $$$6$$$ which is congruent to $$$1$$$ modulo $$$5$$$. The only longer subsequence is $$$[1,2,3,4]$$$. Its product is $$$24$$$ which is congruent to $$$4$$$ modulo $$$5$$$. Hence, the answer is $$$[1,2,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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation $$$a$$$ consisting of $$$n$$$ numbers $$$1$$$, $$$2$$$, ..., $$$n$$$ (a permutation is an array in which each element from $$$1$$$ to $$$n$$$ occurs exactly once).

You can perform the following operation: choose some subarray (contiguous subsegment) of $$$a$$$ and rearrange the elements in it in any way you want. But this operation cannot be applied to the whole array.

For example, if $$$a = [2, 1, 4, 5, 3]$$$ and we want to apply the operation to the subarray $$$a[2, 4]$$$ (the subarray containing all elements from the $$$2$$$-nd to the $$$4$$$-th), then after the operation, the array can become $$$a = [2, 5, 1, 4, 3]$$$ or, for example, $$$a = [2, 1, 5, 4, 3]$$$.

Your task is to calculate the minimum number of operations described above to sort the permutation $$$a$$$ in ascending order.

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

The first line of the test case contains a single integer $$$n$$$ ($$$3 \le n \le 50$$$) — the number of elements in the permutation.

The second line of the test case contains $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ — the given permutation $$$a$$$.

## Output Format
For each test case, output a single integer — the minimum number of operations described above to sort the array $$$a$$$ in ascending order.

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

## Note
In the explanations, $$$a[i, j]$$$ defines the subarray of $$$a$$$ that starts from the $$$i$$$-th element and ends with the $$$j$$$-th element.

In the first test case of the example, you can select the subarray $$$a[2, 3]$$$ and swap the elements in it.

In the second test case of the example, the permutation is already sorted, so you don't need to apply any operations.

In the third test case of the example, you can select the subarray $$$a[3, 5]$$$ and reorder the elements in it so $$$a$$$ becomes $$$[2, 1, 3, 4, 5]$$$, and then select the subarray $$$a[1, 2]$$$ and swap the elements in it, so $$$a$$$ becomes $$$[1, 2, 3, 4, 5]$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A sequence $$$(b_1, b_2, \ldots, b_k)$$$ is called strange, if the absolute difference between any pair of its elements is greater than or equal to the maximum element in the sequence. Formally speaking, it's strange if for every pair $$$(i, j)$$$ with $$$1 \le i<j \le k$$$, we have $$$|a_i-a_j|\geq MAX$$$, where $$$MAX$$$ is the largest element of the sequence. In particular, any sequence of length at most $$$1$$$ is strange.

For example, the sequences $$$(-2021, -1, -1, -1)$$$ and $$$(-1, 0, 1)$$$ are strange, but $$$(3, 0, 1)$$$ is not, because $$$|0 - 1| < 3$$$.

Sifid has an array $$$a$$$ of $$$n$$$ integers. Sifid likes everything big, so among all the strange subsequences of $$$a$$$, he wants to find the length of the longest one. Can you help him?

A sequence $$$c$$$ is a subsequence of an array $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by deletion of several (possibly, zero or all) elements.

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

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

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

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

## Output Format
For each test case output a single integer — the length of the longest strange subsequence of $$$a$$$.

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

## Note
In the first test case, one of the longest strange subsequences is $$$(a_1, a_2, a_3, a_4)$$$

In the second test case, one of the longest strange subsequences is $$$(a_1, a_3, a_4, a_5, a_7)$$$.

In the third test case, one of the longest strange subsequences is $$$(a_1, a_3, a_4, a_5)$$$.

In the fourth test case, one of the longest strange subsequences is $$$(a_2)$$$.

In the fifth test case, one of the longest strange subsequences is $$$(a_1, a_2, a_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: 512.0 MB

# Problem
Немногие знают, что сотрудники ВКонтакте могут менять цвет подсветки в куполе знаменитого Дома Зингера, где расположена штаб-квартира ВКонтакте. Для этого нужно всего лишь отправить сообщение с цветом в специальный чат «Зингер | color», а бот его распознает и сменит подсветку. При этом на время городских мероприятий смена цвета блокируется.

Формально, бот обрабатывает три типа сообщений:

- lock: заблокировать изменение цвета. Если оно и так заблокировано на данный момент, сообщение игнорируется.
- unlock: разблокировать изменение цвета. Если оно и так разблокировано на данный момент, сообщение игнорируется.
- red / orange / yellow / green / blue / indigo / violet: изменить цвет купола на заданный, если изменение цвета на данный момент не заблокировано.

Вам дана история сообщений, полученных ботом, в хронологическом порядке. Считайте, что перед получением первого сообщения купол подсвечивается голубым (blue), а изменение цвета не заблокировано.

Определите, какой цвет будет у купола Дома Зингера после обработки этих сообщений.

## Input Format
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — число сообщений, полученных ботом.

В следующих $$$n$$$ строках заданы сообщения, полученные ботом, в хронологическом порядке, по одному сообщению в строке. Каждое сообщение — строка из следующего набора: lock, unlock, red, orange, yellow, green, blue, indigo, violet.

## Output Format
Выведите цвет купола после обработки сообщений ботом.

## Examples
```input
7
red
violet
unlock
red
orange
lock
indigo
```
```output
orange
```
-----
```input
5
lock
unlock
lock
unlock
unlock
```
```output
blue
```

Now solve the problem and return the code.