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
Even in kindergarten, Sasha liked a girl. Therefore, he wanted to give her a drawing and attract her attention.

As a drawing, he decided to draw a square grid of size $$$n \times n$$$, in which some cells are colored. But coloring the cells is difficult, so he wants to color as few cells as possible. But at the same time, he wants at least $$$k$$$ diagonals to have at least one colored cell. Note that the square grid of size $$$n \times n$$$ has a total of $$$4n - 2$$$ diagonals.

Help little Sasha to make the girl fall in love with him and tell him the minimum number of cells he needs to color.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^8$$$, $$$1 \leq k \leq 4n - 2$$$) — the size of the square grid and the minimum number of diagonals in which there should be at least one colored cell.

## Output Format
For each test case, output a single integer — the minimum number of cells that need to be colored.

## Examples
```input
7
3 4
3 3
3 10
3 9
4 7
7 11
2 3
```
```output
2
2
6
5
4
6
2
```

## Note
In the pictures below, the colored cells are marked in black, and all diagonals are marked in purple.

In the first test case, you can color $$$2$$$ cells so that $$$4$$$ diagonals contain at least one colored cell:

In the third test case, you can color $$$6$$$ cells so that all $$$10$$$ diagonals contain at least one colored cell:

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
Sasha was given a tree$$$^{\dagger}$$$ with $$$n$$$ vertices as a prize for winning yet another competition. However, upon returning home after celebrating his victory, he noticed that some parts of the tree were missing. Sasha remembers that he colored some of the edges of this tree. He is certain that for any of the $$$k$$$ pairs of vertices $$$(a_1, b_1), \ldots, (a_k, b_k)$$$, he colored at least one edge on the simple path$$$^{\ddagger}$$$ between vertices $$$a_i$$$ and $$$b_i$$$.

Sasha does not remember how many edges he exactly colored, so he asks you to tell him the minimum number of edges he could have colored to satisfy the above condition.

$$$^{\dagger}$$$A tree is an undirected connected graph without cycles.

$$$^{\ddagger}$$$A simple path is a path that passes through each vertex at most once.

## Input Format
Each test consists of multiple test cases. The first line contains a single 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 a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices in the tree.

The next $$$(n - 1)$$$ lines describe the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — the numbers of the vertices connected by the $$$i$$$-th edge.

The next line contains a single integer $$$k$$$ ($$$1 \leq k \leq 20$$$) — the number of pairs of vertices between which Sasha colored at least one edge on a simple path.

The next $$$k$$$ lines describe pairs. The $$$j$$$-th line contains two integers $$$a_j$$$ and $$$b_j$$$ ($$$1 \leq a_j, b_j \leq n, a_j \neq b_j$$$) — the vertices in the $$$j$$$-th pair.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$. It is guaranteed that the sum of $$$2^k$$$ over all test cases does not exceed $$$2^{20}$$$.

## Output Format
For each test case, output a single integer — the minimum number of edges Sasha could have colored.

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

## Note
In the first test case, Sasha could have colored only one edge $$$(1, 2)$$$. Then, there would be at least one colored edge on the simple path between vertices $$$1$$$ and $$$3$$$, and vertices $$$4$$$ and $$$1$$$.

In the second test case, Sasha could have colored the edges $$$(1, 6)$$$ and $$$(1, 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
The Master's Assistance Center has announced an entrance exam, which consists of the following.

The candidate is given a set $$$s$$$ of size $$$n$$$ and some strange integer $$$c$$$. For this set, it is needed to calculate the number of pairs of integers $$$(x, y)$$$ such that $$$0 \leq x \leq y \leq c$$$, $$$x + y$$$ is not contained in the set $$$s$$$, and also $$$y - x$$$ is not contained in the set $$$s$$$.

Your friend wants to enter the Center. Help him pass the exam!

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

The first line of each test case contains two integers $$$n$$$ and $$$c$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq c \leq 10^9$$$) — the size of the set and the strange integer.

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_{n}$$$ ($$$0 \leq s_1 < s_2 < \ldots < s_{n} \leq c$$$) — the elements of the set $$$s$$$.

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

## Output Format
For each test case, output a single integer — the number of suitable pairs of integers.

## Examples
```input
8
3 3
1 2 3
1 179
57
4 6
0 3 5 6
1 1
1
5 10
0 2 4 8 10
5 10
1 3 5 7 9
4 10
2 4 6 7
3 1000000000
228 1337 998244353
```
```output
3
16139
10
2
33
36
35
499999998999122959
```

## Note
In the first test case, the following pairs are suitable: $$$(0, 0)$$$, $$$(2, 2)$$$, $$$(3, 3)$$$.

In the third test case, the following pairs are suitable: $$$(0, 1)$$$, $$$(0, 2)$$$, $$$(0, 4)$$$, $$$(1, 3)$$$, $$$(2, 6)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, $$$(4, 5)$$$, $$$(4, 6)$$$, $$$(5, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
One day the Codeforces round author sat exams. He had n exams and he needed to get an integer from 2 to 5 for each exam. He will have to re-sit each failed exam, i.e. the exam that gets mark 2.

The author would need to spend too much time and effort to make the sum of his marks strictly more than k. That could have spoilt the Codeforces round. On the other hand, if the sum of his marks is strictly less than k, the author's mum won't be pleased at all.

The Codeforces authors are very smart and they always get the mark they choose themselves. Also, the Codeforces authors just hate re-sitting exams.

Help the author and find the minimum number of exams he will have to re-sit if he passes the exams in the way that makes the sum of marks for all n exams equal exactly k.

## Input Format
The single input line contains space-separated integers n and k (1 ≤ n ≤ 50, 1 ≤ k ≤ 250) — the number of exams and the required sum of marks.

It is guaranteed that there exists a way to pass n exams in the way that makes the sum of marks equal exactly k.

## Output Format
Print the single number — the minimum number of exams that the author will get a 2 for, considering that the sum of marks for all exams must equal k.

## Examples
```input
4 8
```
```output
4
```
-----
```input
4 10
```
```output
2
```
-----
```input
1 3
```
```output
0
```

## Note
In the first sample the author has to get a 2 for all his exams.

In the second sample he should get a 3 for two exams and a 2 for two more.

In the third sample he should get a 3 for one exam.

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 $$$n$$$ sticks of lengths $$$a_1, a_2, \ldots, a_n$$$. Find the maximum number of regular (equal-sided) polygons you can construct simultaneously, such that:

- Each side of a polygon is formed by exactly one stick.
- No stick is used in more than $$$1$$$ polygon.

Note: Sticks cannot be broken.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of sticks available.

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

## Output Format
For each test case, output a single integer on a new line — the maximum number of regular (equal-sided) polygons you can make simultaneously from the sticks available.

## Examples
```input
4
1
1
2
1 1
6
2 2 3 3 3 3
9
4 2 2 2 2 4 2 4 4
```
```output
0
0
1
2
```

## Note
In the first test case, we only have one stick, hence we can't form any polygon.

In the second test case, the two sticks aren't enough to form a polygon either.

In the third test case, we can use the $$$4$$$ sticks of length $$$3$$$ to create a square.

In the fourth test case, we can make a pentagon with side length $$$2$$$, and a square of side length $$$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
Given integers $$$n$$$ and $$$k$$$, construct a sequence of $$$n$$$ non-negative (i.e. $$$\geq 0$$$) integers $$$a_1, a_2, \ldots, a_n$$$ such that

1. $$$\sum\limits_{i = 1}^n a_i = k$$$
2. The number of $$$1$$$s in the binary representation of $$$a_1 | a_2 | \ldots | a_n$$$ is maximized, where $$$|$$$ denotes the bitwise OR operation.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$) — the number of non-negative integers to be printed and the sum respectively.

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, output a sequence $$$a_1, a_2, \ldots, a_n$$$ on a new line that satisfies the conditions given above.

If there are multiple solutions, print any of them.

## Examples
```input
4
1 5
2 3
2 5
6 51
```
```output
5
1 2
5 0
3 1 1 32 2 12
```

## Note
In the first test case, we have to print exactly one integer, hence we can only output $$$5$$$ as the answer.

In the second test case, we output $$$1, 2$$$ which sum up to $$$3$$$, and $$$1 | 2 = (11)_2$$$ has two $$$1$$$s in its binary representation, which is the maximum we can achieve in these constraints.

In the fourth test case, we output $$$3, 1, 1, 32, 2, 12$$$ which sum up to $$$51$$$, and $$$3 | 1 | 1 | 32 | 2 | 12 = (101\,111)_2$$$ has five $$$1$$$s in its binary representation, which is the maximum we can achieve in these constraints.

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 array $$$a_1, a_2, \ldots, a_n$$$. Find the number of tuples ($$$x, y, z$$$) such that:

- $$$1 \leq x \leq y \leq z \leq n$$$, and
- $$$f(x, y) \oplus f(y, z) > f(x, z)$$$.

We define $$$f(l, r) = a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r}$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

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

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

## Output Format
For each test case, output a single integer on a new line — the number of described tuples.

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

## Note
In the first case, there are 4 such tuples in the array $$$[6, 2, 4]$$$:

- ($$$1$$$, $$$2$$$, $$$2$$$): $$$(a_1 \oplus a_2) \oplus (a_2) = 4 \oplus 2 > (a_1 \oplus a_2) = 4$$$
- ($$$1$$$, $$$1$$$, $$$3$$$): $$$(a_1) \oplus (a_1 \oplus a_2 \oplus a_3) = 6 \oplus 0 > (a_1 \oplus a_2 \oplus a_3) = 0$$$
- ($$$1$$$, $$$2$$$, $$$3$$$): $$$(a_1 \oplus a_2) \oplus (a_2 \oplus a_3) = 4 \oplus 6 > (a_1 \oplus a_2 \oplus a_3) = 0$$$
- ($$$1$$$, $$$3$$$, $$$3$$$): $$$(a_1 \oplus a_2 \oplus a_3) \oplus (a_3) = 0 \oplus 4 > (a_1 \oplus a_2 \oplus a_3) = 0$$$

In the second test case, there are no such tuples.

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

# Problem
You are given an integer $$$n$$$. The function $$$C(i,k)$$$ represents the number of distinct ways you can select $$$k$$$ distinct numbers from the set {$$$1, 2, \ldots, i$$$} and arrange them in a circle$$$^\dagger$$$.

Find the value of $$$$$$ \sum\limits_{i=1}^n \sum\limits_{j=1}^i \left( C(i,j) \bmod j \right). $$$$$$ Here, the operation $$$x \bmod y$$$ denotes the remainder from dividing $$$x$$$ by $$$y$$$.

Since this value can be very large, find it modulo $$$10^9+7$$$.

$$$^\dagger$$$ In a circular arrangement, sequences are considered identical if one can be rotated to match the other. For instance, $$$[1, 2, 3]$$$ and $$$[2, 3, 1]$$$ are equivalent in a circle.

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

## Output Format
For each test case, output a single integer on a new line — the value of the expression to be calculated modulo $$$10^9+7$$$.

## Examples
```input
4
1
3
6
314159
```
```output
0
4
24
78926217
```

## Note
In the first test case, $$$C(1,1) \bmod 1 = 0$$$.

In the second test case:

- $$$C(1,1)=1$$$ (the arrangements are: $$$[1]$$$);
- $$$C(2,1)=2$$$ (the arrangements are: $$$[1]$$$, $$$[2]$$$);
- $$$C(2,2)=1$$$ (the arrangements are: $$$[1, 2]$$$);
- $$$C(3,1)=3$$$ (the arrangements are: $$$[1]$$$, $$$[2]$$$, $$$[3]$$$);
- $$$C(3,2)=3$$$ (the arrangements are: $$$[1, 2]$$$, $$$[2, 3]$$$, $$$[3, 1]$$$);
- $$$C(3,3)=2$$$ (the arrangements are: $$$[1, 2, 3]$$$, $$$[1, 3, 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: 4.0 seconds
Memory limit: 512.0 MB

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

You are given an undirected tree of $$$n$$$ nodes. Each node $$$v$$$ has a value $$$a_v$$$ written on it. You have to answer queries related to the tree.

You are given $$$q$$$ queries. In each query, you are given $$$5$$$ integers, $$$u_1, v_1, u_2, v_2, k$$$. Denote the count of nodes with value $$$c$$$ on path $$$u_1 \rightarrow v_1$$$ with $$$x_c$$$, and the count of nodes with value $$$c$$$ on path $$$u_2 \rightarrow v_2$$$ with $$$y_c$$$. If there are $$$z$$$ such values of $$$c$$$ such that $$$x_c \neq y_c$$$, output any $$$\min(z, k)$$$ such values in any order.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of nodes in the tree.

The next line contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — the value written on each node of the tree.

Then $$$n - 1$$$ lines follow. Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n, u \neq v$$$) denoting an edge of the tree. It is guaranteed that the given edges form a tree.

The next line contains one integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow. Each line contains five integers $$$u_1, v_1, u_2, v_2, k$$$ ($$$1 \leq u_1, v_1, u_2, v_2 \leq n$$$, $$$k = 1$$$).

## Output Format
For each query, output on a separate line. For a query, first output $$$\min(z, k)$$$ and then on the same line, output any $$$\min(z, k)$$$ values in any order which occur a different number of times in each path.

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

## Note
For query $$$1$$$, the first path is $$$1 \rightarrow 2 \rightarrow 4$$$, coming across the multiset of values $$$\{5, 2, 4\}$$$. On the second path $$$4 \rightarrow 2 \rightarrow 5$$$, we have the multiset $$$\{4, 2, 3\}$$$. Two numbers — $$$3$$$ and $$$5$$$ occur a different number of times, hence we print one of them.

In query $$$2$$$, there is no difference between the paths, hence we output $$$0$$$.

In query $$$3$$$, the first path is just the node $$$5$$$, resulting in the multiset $$$\{3\}$$$, and the second path $$$4 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$ gives $$$\{4, 2, 5, 3\}$$$. The numbers $$$5$$$, $$$2$$$ and $$$4$$$ occur a different number of times.

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 have a hand of $$$n$$$ cards, where each card has a number written on it, and a fixed integer $$$k$$$. You can perform the following operation any number of times:

- Choose any $$$k$$$ cards from your hand that all have the same number.
- Exchange these cards for $$$k-1$$$ cards, each of which can have any number you choose (including the number written on the cards you just exchanged).

Here is one possible sequence of operations for the first example case, which has $$$k=3$$$:

What is the minimum number of cards you can have in your hand at the end of this process?

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$2 \le k \le 100$$$) — the number of cards you have, and the number of cards you exchange during each operation, respectively.

The next line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots c_n$$$ ($$$1 \le c_i \le 100$$$) — the numbers written on your cards.

## Output Format
For each test case, output a single integer — the minimum number of cards you can have left in your hand after any number of operations.

## Examples
```input
7
5 3
4 1 1 4 4
1 10
7
7 2
4 2 1 100 5 2 3
10 4
1 1 1 1 1 1 1 1 1 1
5 2
3 8 1 48 7
6 2
10 20 30 10 20 40
6 3
10 20 30 10 20 40
```
```output
2
1
1
3
5
1
6
```

## Note
The first example case corresponds to the picture above. The sequence of operations displayed there is optimal, so the answer is $$$2$$$.

In the second example case, no operations can be performed, so the answer is $$$1$$$.

In the fourth example case, you can repeatedly select $$$4$$$ cards numbered with $$$1$$$ and replace them with $$$3$$$ cards numbered with $$$1$$$, until there are $$$3$$$ cards left.

Now solve the problem and return the code.