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 tree consisting of $$$n$$$ vertices. A tree is a connected undirected graph with $$$n-1$$$ edges. Each vertex $$$v$$$ of this tree has a color assigned to it ($$$a_v = 1$$$ if the vertex $$$v$$$ is white and $$$0$$$ if the vertex $$$v$$$ is black).

You have to solve the following problem for each vertex $$$v$$$: what is the maximum difference between the number of white and the number of black vertices you can obtain if you choose some subtree of the given tree that contains the vertex $$$v$$$? The subtree of the tree is the connected subgraph of the given tree. More formally, if you choose the subtree that contains $$$cnt_w$$$ white vertices and $$$cnt_b$$$ black vertices, you have to maximize $$$cnt_w - cnt_b$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$), where $$$a_i$$$ is the color of the $$$i$$$-th vertex.

Each of the next $$$n-1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$, the labels of vertices it connects $$$(1 \le u_i, v_i \le n, u_i \ne v_i$$$).

It is guaranteed that the given edges form a tree.

## Output Format
Print $$$n$$$ integers $$$res_1, res_2, \dots, res_n$$$, where $$$res_i$$$ is the maximum possible difference between the number of white and black vertices in some subtree that contains the vertex $$$i$$$.

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

## Note
The first example is shown below:

The black vertices have bold borders.

In the second example, the best subtree for vertices $$$2, 3$$$ and $$$4$$$ are vertices $$$2, 3$$$ and $$$4$$$ correspondingly. And the best subtree for the vertex $$$1$$$ is the subtree consisting of vertices $$$1$$$ and $$$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
Dreamoon is a big fan of the Codeforces contests.

One day, he claimed that he will collect all the places from $$$1$$$ to $$$54$$$ after two more rated contests. It's amazing!

Based on this, you come up with the following problem:

There is a person who participated in $$$n$$$ Codeforces rounds. His place in the first round is $$$a_1$$$, his place in the second round is $$$a_2$$$, ..., his place in the $$$n$$$-th round is $$$a_n$$$.

You are given a positive non-zero integer $$$x$$$.

Please, find the largest $$$v$$$ such that this person can collect all the places from $$$1$$$ to $$$v$$$ after $$$x$$$ more rated contests.

In other words, you need to find the largest $$$v$$$, such that it is possible, that after $$$x$$$ more rated contests, for each $$$1 \leq i \leq v$$$, there will exist a contest where this person took the $$$i$$$-th place.

For example, if $$$n=6$$$, $$$x=2$$$ and $$$a=[3,1,1,5,7,10]$$$ then answer is $$$v=5$$$, because if on the next two contest he will take places $$$2$$$ and $$$4$$$, then he will collect all places from $$$1$$$ to $$$5$$$, so it is possible to get $$$v=5$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5$$$) denoting the number of test cases in the input.

Each test case contains two lines. The first line contains two integers $$$n, x$$$ ($$$1 \leq n, x \leq 100$$$). The second line contains $$$n$$$ positive non-zero integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$).

## Output Format
For each test case print one line containing the largest $$$v$$$, such that it is possible that after $$$x$$$ other contests, for each $$$1 \leq i \leq v$$$, there will exist a contest where this person took the $$$i$$$-th place.

## Examples
```input
5
6 2
3 1 1 5 7 10
1 100
100
11 1
1 1 1 1 1 1 1 1 1 1 1
1 1
1
4 57
80 60 40 20
```
```output
5
101
2
2
60
```

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

In the second test case, the person has one hundred future contests, so he can take place $$$1,2,\ldots,99$$$ and place $$$101$$$ on them in some order, to collect places $$$1,2,\ldots,101$$$.

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 sequence of positive integers a1, a2, ..., an. Find all such indices i, that the i-th element equals the arithmetic mean of all other elements (that is all elements except for this one).

## Input Format
The first line contains the integer n (2 ≤ n ≤ 2·105). The second line contains elements of the sequence a1, a2, ..., an (1 ≤ ai ≤ 1000). All the elements are positive integers.

## Output Format
Print on the first line the number of the sought indices. Print on the second line the sought indices in the increasing order. All indices are integers from 1 to n.

If the sought elements do not exist, then the first output line should contain number 0. In this case you may either not print the second line or print an empty line.

## Examples
```input
5
1 2 3 4 5
```
```output
1
3
```
-----
```input
4
50 50 50 50
```
```output
4
1 2 3 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let's assume that we have a pair of numbers (a, b). We can get a new pair (a + b, b) or (a, a + b) from the given pair in a single step.

Let the initial pair of numbers be (1,1). Your task is to find number k, that is, the least number of steps needed to transform (1,1) into the pair where at least one number equals n.

## Input Format
The input contains the only integer n (1 ≤ n ≤ 106).

## Output Format
Print the only integer k.

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

## Note
The pair (1,1) can be transformed into a pair containing 5 in three moves: (1,1)  →  (1,2)  →  (3,2)  →  (5,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
There are n players sitting at a round table. All of them have s cards of n colors in total. Besides, initially the first person had cards of only the first color, the second one had cards of only the second color and so on. They can swap the cards by the following rules:

- as the players swap, a player can give a card of his color only;
- a player can't accept a card of a color he already has (particularly, he can't take cards of his color, no matter whether he has given out all of them or not);
- during one swap a pair of people swaps cards (each person gives one card and takes one card).

The aim of all n people is as follows: each of them should give out all the cards he had initially (that is, all cards of his color). Your task is to denote whether such sequence of swaps is possible. If the answer is positive, you should list all the swaps.

## Input Format
The first line contains integers n (1 ≤ n ≤ 200000) and s (1 ≤ s ≤ 200000). The second line contains n numbers, the i-th number stands for how many cards the i-th player has by the moment the game starts. It is possible that a player has no cards initially.

## Output Format
On the first line print "No" if such sequence of swaps is impossible. Otherwise, print "Yes". If the answer is positive, next print number k — the number of the swaps. Then on k lines describe the swaps by pairs of indices of the swapping players. Print the swaps and the numbers of the swaps in any order.

## Examples
```input
4 8
2 2 2 2
```
```output
Yes
4
4 3
4 2
1 3
1 2
```
-----
```input
6 12
1 1 2 2 3 3
```
```output
Yes
6
6 5
6 4
6 3
5 4
5 3
2 1
```
-----
```input
5 5
0 0 0 0 5
```
```output
No
```

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
Hmm, how long has it been since the last color revolution? 5 years?! It's totally the time to make a new one!

So the general idea is the following. Division $$$1$$$ should have $$$n_1$$$ participants. Division $$$2$$$ should have $$$n_2$$$ and be exactly $$$k$$$ times bigger than division $$$1$$$ ($$$n_2 = k \cdot n_1$$$). Division $$$3$$$ should have $$$n_3 = k \cdot n_2$$$ participants. Finally, division $$$4$$$ should have $$$n_4 = k \cdot n_3$$$ participants.

There are $$$n$$$ participants on Codeforces in total. So $$$n_1 + n_2 + n_3 + n_4$$$ should be exactly equal to $$$n$$$.

You know the values of $$$n$$$ and $$$k$$$. You also know that $$$n$$$ and $$$k$$$ are chosen in such a way that there exist values $$$n_1, n_2, n_3$$$ and $$$n_4$$$ such that all the conditions are satisfied.

What will be the number of participants in each division ($$$n_1, n_2, n_3$$$ and $$$n_4$$$) after the revolution?

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

Each of the next $$$t$$$ lines contains two integers $$$n$$$ and $$$k$$$ ($$$4 \le n \le 10^9$$$; $$$1 \le k \le 500$$$) — the total number of participants on Codeforces and the size multiplier for the corresponding testcase. In each testcase, $$$n$$$ and $$$k$$$ are chosen in such a way that the answer exists.

## Output Format
For each testcase print four integers $$$n_1, n_2, n_3$$$ and $$$n_4$$$ such that $$$n_2 = k \cdot n_1$$$, $$$n_3 = k \cdot n_2$$$, $$$n_4 = k \cdot n_3$$$ and $$$n_1 + n_2 + n_3 + n_4 = n$$$.

## Examples
```input
4
40 3
1200 7
320802005 400
4 1
```
```output
1 3 9 27
3 21 147 1029
5 2000 800000 320000000
1 1 1 1
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Berland State University (BSU) is conducting a programming boot camp. The boot camp will last for $$$n$$$ days, and the BSU lecturers are planning to give some number of lectures during these days.

Some days of the boot camp are already planned as excursion days, and no lectures should be held during these days. To make sure the participants don't get too tired of learning to program, the number of lectures for each day should not exceed $$$k_1$$$, and the number of lectures for each pair of consecutive days should not exceed $$$k_2$$$.

Can you calculate the maximum number of lectures that can be conducted during the boot camp? Formally, find the maximum integer $$$m$$$ such that it is possible to choose $$$n$$$ non-negative integers $$$c_1$$$, $$$c_2$$$, ..., $$$c_n$$$ (where $$$c_i$$$ is the number of lectures held during day $$$i$$$) so that:

- $$$c_1 + c_2 + \dots + c_n = m$$$;
- for each excursion day $$$d$$$, $$$c_d = 0$$$;
- for each day $$$i$$$, $$$c_i \le k_1$$$;
- for each pair of consecutive days $$$(i, i + 1)$$$, $$$c_i + c_{i + 1} \le k_2$$$.

Note that there might be some non-excursion days without lectures (i. e., it is possible that $$$c_i = 0$$$ even if $$$i$$$ is not an excursion day).

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

Then the testcases follow, each consists of two lines. The first line contains three integers $$$n$$$, $$$k_1$$$, $$$k_2$$$ ($$$1 \le n \le 5000$$$; $$$1 \le k_1 \le k_2 \le 200\,000$$$).

The second line contains one string $$$s$$$ consisting of exactly $$$n$$$ characters, each character is either 0 or 1. If $$$s_i = 0$$$, then day $$$i$$$ is an excursion day (so there should be no lectures during that day); if $$$s_i = 1$$$, then day $$$i$$$ is not an excursion day.

## Output Format
For each test case, print one integer — the maximum possible value of $$$m$$$ (the number of lectures that can be conducted).

## Examples
```input
4
4 5 7
1011
4 4 10
0101
5 3 4
11011
6 4 6
011101
```
```output
12
8
8
14
```

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
Masha is going to participate in a talent show conducted by the university she studies at. She wants to impress the audience with lots of different magic tricks!

For one of her tricks, she uses $$$n$$$ sponge balls, one of which is a special one. First, she arranges the balls in a row in such a way that the special ball is put on position $$$k$$$ (positions are numbered from $$$1$$$ to $$$n$$$ from left to right). After that, she performs $$$m$$$ swaps: during the $$$i$$$-th swap, she chooses the ball on position $$$x_i$$$ and the ball on position $$$y_i$$$, and swaps them.

Since Masha is a magician, she fakes some of her actions to trick the audience — when she starts performing a swap, she may fake it, so it is not performed (but it looks like it is performed for the audience). There are no constraints on which swaps Masha should fake or should actually perform — for example, she may fake all of the swaps, or even not fake anything at all.

For the trick to work perfectly, the special ball should end up on a specific position — Masha has not decided yet, which position is perfect. Since faking swaps is difficult, for each position she wants to know the minimum number of swaps she has to fake so that the special ball ends up there.

Unfortunately, Masha is a magician, neither a mathematician nor a programmer. So she needs your help in calculating what she wants!

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — the number of balls, the number of swaps and the initial position of the special ball, respectively.

Then $$$m$$$ lines follow, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) denoting the $$$i$$$-th swap.

## Output Format
Print $$$n$$$ integers. The $$$i$$$-th integer should be the minimum number of swaps Masha has to fake so the special ball ends up on position $$$i$$$ (or $$$-1$$$, if Masha cannot put the special ball there).

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

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

# Problem
You have two IP cameras of the same model. Each camera can take photos starting from some moment of time with a fixed period. You can freely choose the starting moment but you can choose the period only as one of $$$k$$$ values $$$p_1, p_2, \dots, p_k$$$ which are chosen by the camera's manufacturer.

You have $$$n$$$ moments of interest $$$x_1, x_2, \dots, x_n$$$. You'd like to configure both cameras in such a way that at least one camera will take a photo in each of these moments. Configuring the camera means setting the moment when it takes the first photo and the gap between two consecutive photos (which should be one of the values $$$p_1, p_2, \dots, p_k$$$). It's not a problem for you that cameras can take photos at other moments of time — you only care about moments of interest.

## Input Format
The first line contains two integers $$$k$$$ and $$$n$$$ ($$$1 \le k \le 10^5$$$; $$$2 \le n \le 10^5$$$) — the number of periods to choose and the number of moments of interest.

The second line contains $$$k$$$ integers $$$p_1, p_2, \dots, p_k$$$ ($$$1 \le p_1 < p_2 < \dots < p_k \le 10^6$$$) — the periods to choose in the ascending order.

The third line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_1 < x_2 < \dots < x_n \le 10^6$$$) — the moments of interest in the ascending order.

## Output Format
Print YES (case insensitive) in the first line if there is a way to configure cameras.

In the second line, print two integers $$$s_1$$$ and $$$cp_1$$$ ($$$1 \le s_1 \le 10^6$$$; $$$1 \le cp_1 \le 10^6$$$; $$$cp_1 \in \{p_1, \dots, p_k\}$$$) — the starting moment and the period for the first camera. The period should be one of the given periods.

In the third line, print two integers $$$s_2$$$ and $$$cp_2$$$ ($$$1 \le s_2 \le 10^6$$$; $$$1 \le cp_2 \le 10^6$$$; $$$cp_2 \in \{p_1, \dots, p_k\}$$$) — the starting moment and the period for the second camera. The period should be one of the given periods.

If there is no way to configure cameras, print NO (case insensitive). If there are multiple ways, you may print any of them.

## Examples
```input
3 5
3 5 7
1 4 5 7 12
```
```output
YES
1 3
5 7
```
-----
```input
3 2
1 2 3
1 10
```
```output
YES
1 1
10 1
```
-----
```input
3 4
1 2 3
5 7 9 11
```
```output
YES
5 1
5 1
```
-----
```input
3 4
10 20 100
2 3 4 7
```
```output
NO
```

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 two positive integers $$$n$$$ ($$$1 \le n \le 10^9$$$) and $$$k$$$ ($$$1 \le k \le 100$$$). Represent the number $$$n$$$ as the sum of $$$k$$$ positive integers of the same parity (have the same remainder when divided by $$$2$$$).

In other words, find $$$a_1, a_2, \ldots, a_k$$$ such that all $$$a_i>0$$$, $$$n = a_1 + a_2 + \ldots + a_k$$$ and either all $$$a_i$$$ are even or all $$$a_i$$$ are odd at the same time.

If such a representation does not exist, then report it.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. Next, $$$t$$$ test cases are given, one per line.

Each test case is two positive integers $$$n$$$ ($$$1 \le n \le 10^9$$$) and $$$k$$$ ($$$1 \le k \le 100$$$).

## Output Format
For each test case print:

- YES and the required values $$$a_i$$$, if the answer exists (if there are several answers, print any of them);
- NO if the answer does not exist.

The letters in the words YES and NO can be printed in any case.

## Examples
```input
8
10 3
100 4
8 7
97 2
8 8
3 10
5 3
1000000000 9
```
```output
YES
4 2 4
YES
55 5 5 35
NO
NO
YES
1 1 1 1 1 1 1 1
NO
YES
3 1 1
YES
111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120
```

Now solve the problem and return the code.