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

# Problem
You found a useless array $$$a$$$ of $$$2n$$$ positive integers. You have realized that you actually don't need this array, so you decided to throw out all elements of $$$a$$$.

It could have been an easy task, but it turned out that you should follow some rules:

1. In the beginning, you select any positive integer $$$x$$$.
2. Then you do the following operation $$$n$$$ times:   select two elements of array with sum equals $$$x$$$;  remove them from $$$a$$$ and replace $$$x$$$ with maximum of that two numbers.

For example, if initially $$$a = [3, 5, 1, 2]$$$, you can select $$$x = 6$$$. Then you can select the second and the third elements of $$$a$$$ with sum $$$5 + 1 = 6$$$ and throw them out. After this operation, $$$x$$$ equals $$$5$$$ and there are two elements in array: $$$3$$$ and $$$2$$$. You can throw them out on the next operation.

Note, that you choose $$$x$$$ before the start and can't change it as you want between the operations.

Determine how should you behave to throw out all elements of $$$a$$$.

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

The first line of each test case contains the single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$).

The second line of each test case contains $$$2n$$$ integers $$$a_1, a_2, \dots, a_{2n}$$$ ($$$1 \leq a_i \leq 10^6$$$) — the initial array $$$a$$$.

It is guaranteed that the total sum of $$$n$$$ over all test cases doesn't exceed $$$1000$$$.

## Output Format
For each test case in the first line print YES if it is possible to throw out all elements of the array and NO otherwise.

If it is possible to throw out all elements, print the initial value of $$$x$$$ you've chosen. Print description of $$$n$$$ operations next. For each operation, print the pair of integers you remove.

## Examples
```input
4
2
3 5 1 2
3
1 1 8 8 64 64
2
1 1 2 4
5
1 2 3 4 5 6 7 14 3 11
```
```output
YES
6
1 5
2 3
NO
NO
YES
21
14 7
3 11
5 6
2 4
3 1
```

## Note
The first test case was described in the statement.

In the second and third test cases, we can show that it is impossible to throw out all elements of array $$$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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Igor had a sequence $$$d_1, d_2, \dots, d_n$$$ of integers. When Igor entered the classroom there was an integer $$$x$$$ written on the blackboard.

Igor generated sequence $$$p$$$ using the following algorithm:

1. initially, $$$p = [x]$$$;
2. for each $$$1 \leq i \leq n$$$ he did the following operation $$$|d_i|$$$ times:   if $$$d_i \geq 0$$$, then he looked at the last element of $$$p$$$ (let it be $$$y$$$) and appended $$$y + 1$$$ to the end of $$$p$$$;  if $$$d_i < 0$$$, then he looked at the last element of $$$p$$$ (let it be $$$y$$$) and appended $$$y - 1$$$ to the end of $$$p$$$.

For example, if $$$x = 3$$$, and $$$d = [1, -1, 2]$$$, $$$p$$$ will be equal $$$[3, 4, 3, 4, 5]$$$.

Igor decided to calculate the length of the longest increasing subsequence of $$$p$$$ and the number of them.

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

A sequence $$$a$$$ is an increasing sequence if each element of $$$a$$$ (except the first one) is strictly greater than the previous element.

For $$$p = [3, 4, 3, 4, 5]$$$, the length of longest increasing subsequence is $$$3$$$ and there are $$$3$$$ of them: $$$[\underline{3}, \underline{4}, 3, 4, \underline{5}]$$$, $$$[\underline{3}, 4, 3, \underline{4}, \underline{5}]$$$, $$$[3, 4, \underline{3}, \underline{4}, \underline{5}]$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the sequence $$$d$$$.

The second line contains a single integer $$$x$$$ ($$$-10^9 \leq x \leq 10^9$$$) — the integer on the blackboard.

The third line contains $$$n$$$ integers $$$d_1, d_2, \ldots, d_n$$$ ($$$-10^9 \leq d_i \leq 10^9$$$).

## Output Format
Print two integers:

- the first integer should be equal to the length of the longest increasing subsequence of $$$p$$$;
- the second should be equal to the number of them modulo $$$998244353$$$.

You should print only the second number modulo $$$998244353$$$.

## Examples
```input
3
3
1 -1 2
```
```output
3 3
```
-----
```input
3
100
5 -3 6
```
```output
9 7
```
-----
```input
3
1
999999999 0 1000000000
```
```output
2000000000 1
```
-----
```input
5
34
1337 -146 42 -69 228
```
```output
1393 3876
```

## Note
The first test case was explained in the statement.

In the second test case $$$p = [100, 101, 102, 103, 104, 105, 104, 103, 102, 103, 104, 105, 106, 107, 108]$$$.

In the third test case $$$p = [1, 2, \ldots, 2000000000]$$$.

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
One day you wanted to read something, so you went to your bookshelf to grab some book. But when you saw how messy the bookshelf was you decided to clean it up first.

There are $$$n$$$ books standing in a row on the shelf, the $$$i$$$-th book has color $$$a_i$$$.

You'd like to rearrange the books to make the shelf look beautiful. The shelf is considered beautiful if all books of the same color are next to each other.

In one operation you can take one book from any position on the shelf and move it to the right end of the shelf.

What is the minimum number of operations you need to make the shelf beautiful?

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of books.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the book colors.

## Output Format
Output the minimum number of operations to make the shelf beautiful.

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

## Note
In the first example, we have the bookshelf $$$[1, 2, 2, 1, 3]$$$ and can, for example:

1. take a book on position $$$4$$$ and move to the right end: we'll get $$$[1, 2, 2, 3, 1]$$$;
2. take a book on position $$$1$$$ and move to the right end: we'll get $$$[2, 2, 3, 1, 1]$$$.

In the second example, we can move the first book to the end of the bookshelf and get $$$[2,2,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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Kilani and Abd are neighbors for 3000 years, but then the day came and Kilani decided to move to another house. As a farewell gift, Kilani is going to challenge Abd with a problem written by their other neighbor with the same name Abd.

The problem is:

You are given a connected tree rooted at node $$$1$$$.

You should assign a character a or b to every node in the tree so that the total number of a's is equal to $$$x$$$ and the total number of b's is equal to $$$n - x$$$.

Let's define a string for each node $$$v$$$ of the tree as follows:

- if $$$v$$$ is root then the string is just one character assigned to $$$v$$$:
- otherwise, let's take a string defined for the $$$v$$$'s parent $$$p_v$$$ and add to the end of it a character assigned to $$$v$$$.

You should assign every node a character in a way that minimizes the number of distinct strings among the strings of all nodes.

## Input Format
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 10^5$$$; $$$0 \leq x \leq n$$$) — the number of vertices in the tree the number of a's.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, \dots, p_{n}$$$ ($$$1 \leq p_i \leq n$$$; $$$p_i \neq i$$$), where $$$p_i$$$ is the parent of node $$$i$$$.

It is guaranteed that the input describes a connected tree.

## Output Format
In the first line, print the minimum possible total number of distinct strings.

In the second line, print $$$n$$$ characters, where all characters are either a or b and the $$$i$$$-th character is the character assigned to the $$$i$$$-th node.

Make sure that the total number of a's is equal to $$$x$$$ and the total number of b's is equal to $$$n - x$$$.

If there is more than one answer you can print any of them.

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

## Note
The tree from the sample is shown below:

The tree after assigning characters to every node (according to the output) is the following:

Strings for all nodes are the following:

- string of node $$$1$$$ is: a
- string of node $$$2$$$ is: aa
- string of node $$$3$$$ is: aab
- string of node $$$4$$$ is: aab
- string of node $$$5$$$ is: aabb
- string of node $$$6$$$ is: aabb
- string of node $$$7$$$ is: aabb
- string of node $$$8$$$ is: aabb
- string of node $$$9$$$ is: aa

The set of unique strings is $$$\{\text{a}, \text{aa}, \text{aab}, \text{aabb}\}$$$, so the number of distinct strings is $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have a board represented as a grid with $$$2 \times n$$$ cells.

The first $$$k_1$$$ cells on the first row and first $$$k_2$$$ cells on the second row are colored in white. All other cells are colored in black.

You have $$$w$$$ white dominoes ($$$2 \times 1$$$ tiles, both cells are colored in white) and $$$b$$$ black dominoes ($$$2 \times 1$$$ tiles, both cells are colored in black).

You can place a white domino on the board if both board's cells are white and not occupied by any other domino. In the same way, you can place a black domino if both cells are black and not occupied by any other domino.

Can you place all $$$w + b$$$ dominoes on the board if you can place dominoes both horizontally and vertically?

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

The first line of each test case contains three integers $$$n$$$, $$$k_1$$$ and $$$k_2$$$ ($$$1 \le n \le 1000$$$; $$$0 \le k_1, k_2 \le n$$$).

The second line of each test case contains two integers $$$w$$$ and $$$b$$$ ($$$0 \le w, b \le n$$$).

## Output Format
For each test case, print YES if it's possible to place all $$$w + b$$$ dominoes on the board and NO, otherwise.

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
1 0 1
1 0
1 1 1
0 0
3 0 0
1 3
4 3 1
2 2
5 4 3
3 1
```
```output
NO
YES
NO
YES
YES
```

## Note
In the first test case, $$$n = 1$$$, $$$k_1 = 0$$$ and $$$k_2 = 1$$$. It means that $$$2 \times 1$$$ board has black cell $$$(1, 1)$$$ and white cell $$$(2, 1)$$$. So, you can't place any white domino, since there is only one white cell.

In the second test case, the board of the same size $$$2 \times 1$$$, but both cell are white. Since $$$w = 0$$$ and $$$b = 0$$$, so you can place $$$0 + 0 = 0$$$ dominoes on the board.

In the third test case, board $$$2 \times 3$$$, but fully colored in black (since $$$k_1 = k_2 = 0$$$), so you can't place any white domino.

In the fourth test case, cells $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, and $$$(2, 1)$$$ are white and other cells are black. You can place $$$2$$$ white dominoes at positions $$$((1, 1), (2, 1))$$$ and $$$((1, 2), (1, 3))$$$ and $$$2$$$ black dominoes at positions $$$((1, 4), (2, 4))$$$ $$$((2, 2), (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 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 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 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: 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 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 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 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 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 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
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.