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
The title is a reference to the very first Educational Round from our writers team, Educational Round 18.

There is a bag, containing colored balls. There are $$$n$$$ different colors of balls, numbered from $$$1$$$ to $$$n$$$. There are $$$\mathit{cnt}_i$$$ balls of color $$$i$$$ in the bag. The total amount of balls in the bag is odd (e. g. $$$\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$$$ is odd).

In one move, you can choose two balls with different colors and take them out of the bag.

At some point, all the remaining balls in the bag will have the same color. That's when you can't make moves anymore.

Find any possible color of the remaining balls.

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

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$) — the number of colors.

The second line contains $$$n$$$ integers $$$\mathit{cnt}_1, \mathit{cnt}_2, \dots, \mathit{cnt}_n$$$ ($$$1 \le \mathit{cnt}_i \le 100$$$) — the amount of balls of each color in the bag.

The total amount of balls in the bag is odd (e. g. $$$\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$$$ is odd).

## Output Format
For each testcase, print a single integer — any possible color of the remaining balls, after you made some moves and can't make moves anymore.

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

## Note
In the first testcase, your first and only move can be one of the following:

- take balls with colors $$$1$$$ and $$$2$$$;
- take balls with colors $$$1$$$ and $$$3$$$;
- take balls with colors $$$2$$$ and $$$3$$$.

After the move, exactly one ball will remain. Its color can be $$$3, 2$$$ or $$$1$$$ depending on the move.

In the second testcase, you can't make moves at all — there is only color of balls already. This color is $$$1$$$.

In the third testcase, you can keep removing one ball of color $$$1$$$ and one ball of color $$$2$$$ until there are no more balls of color $$$1$$$. At the end, three balls of color $$$2$$$ remain.

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
Let's define $$$f(x)$$$ for a positive integer $$$x$$$ as the length of the base-10 representation of $$$x$$$ without leading zeros. I like to call it a digital logarithm. Similar to a digital root, if you are familiar with that.

You are given two arrays $$$a$$$ and $$$b$$$, each containing $$$n$$$ positive integers. In one operation, you do the following:

1. pick some integer $$$i$$$ from $$$1$$$ to $$$n$$$;
2. assign either $$$f(a_i)$$$ to $$$a_i$$$ or $$$f(b_i)$$$ to $$$b_i$$$.

Two arrays are considered similar to each other if you can rearrange the elements in both of them, so that they are equal (e. g. $$$a_i = b_i$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$).

What's the smallest number of operations required to make $$$a$$$ and $$$b$$$ similar to each other?

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

The first line of the testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in each of the arrays.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < 10^9$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_j < 10^9$$$).

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print the smallest number of operations required to make $$$a$$$ and $$$b$$$ similar to each other.

## Examples
```input
4
1
1
1000
4
1 2 3 4
3 1 4 2
3
2 9 3
1 100 9
10
75019 709259 5 611271314 9024533 81871864 9 3 6 4865
9503 2 371245467 6 7 37376159 8 364036498 52295554 169
```
```output
2
0
2
18
```

## Note
In the first testcase, you can apply the digital logarithm to $$$b_1$$$ twice.

In the second testcase, the arrays are already similar to each other.

In the third testcase, you can first apply the digital logarithm to $$$a_1$$$, then to $$$b_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: 512.0 MB

# Problem
Alice and Bob are playing a game. Initially, they are given a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.

Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string $$$s$$$, removes it from $$$s$$$ and prepends (adds to the beginning) it to their own string.

The game ends when the string $$$s$$$ becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if there exists such position $$$i$$$ that $$$a_j = b_j$$$ for all $$$j < i$$$ and $$$a_i < b_i$$$.

What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

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

Each testcase consists of a single line — a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string $$$s$$$ is even.

The total length of the strings over all testcases doesn't exceed $$$2000$$$.

## Output Format
For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".

## Examples
```input
2
forces
abba
```
```output
Alice
Draw
```

## Note
One of the possible games Alice and Bob can play in the first testcase:

1. Alice picks the first letter in $$$s$$$: $$$s=$$$"orces", $$$a=$$$"f", $$$b=$$$"";
2. Bob picks the last letter in $$$s$$$: $$$s=$$$"orce", $$$a=$$$"f", $$$b=$$$"s";
3. Alice picks the last letter in $$$s$$$: $$$s=$$$"orc", $$$a=$$$"ef", $$$b=$$$"s";
4. Bob picks the first letter in $$$s$$$: $$$s=$$$"rc", $$$a=$$$"ef", $$$b=$$$"os";
5. Alice picks the last letter in $$$s$$$: $$$s=$$$"r", $$$a=$$$"cef", $$$b=$$$"os";
6. Bob picks the remaining letter in $$$s$$$: $$$s=$$$"", $$$a=$$$"cef", $$$b=$$$"ros".

Alice wins because "cef" < "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.

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
There are $$$n$$$ fishermen who have just returned from a fishing trip. The $$$i$$$-th fisherman has caught a fish of size $$$a_i$$$.

The fishermen will choose some order in which they are going to tell the size of the fish they caught (the order is just a permutation of size $$$n$$$). However, they are not entirely honest, and they may "increase" the size of the fish they have caught.

Formally, suppose the chosen order of the fishermen is $$$[p_1, p_2, p_3, \dots, p_n]$$$. Let $$$b_i$$$ be the value which the $$$i$$$-th fisherman in the order will tell to the other fishermen. The values $$$b_i$$$ are chosen as follows:

- the first fisherman in the order just honestly tells the actual size of the fish he has caught, so $$$b_1 = a_{p_1}$$$;
- every other fisherman wants to tell a value that is strictly greater than the value told by the previous fisherman, and is divisible by the size of the fish that the fisherman has caught. So, for $$$i > 1$$$, $$$b_i$$$ is the smallest integer that is both strictly greater than $$$b_{i-1}$$$ and divisible by $$$a_{p_i}$$$.

For example, let $$$n = 7$$$, $$$a = [1, 8, 2, 3, 2, 2, 3]$$$. If the chosen order is $$$p = [1, 6, 7, 5, 3, 2, 4]$$$, then:

- $$$b_1 = a_{p_1} = 1$$$;
- $$$b_2$$$ is the smallest integer divisible by $$$2$$$ and greater than $$$1$$$, which is $$$2$$$;
- $$$b_3$$$ is the smallest integer divisible by $$$3$$$ and greater than $$$2$$$, which is $$$3$$$;
- $$$b_4$$$ is the smallest integer divisible by $$$2$$$ and greater than $$$3$$$, which is $$$4$$$;
- $$$b_5$$$ is the smallest integer divisible by $$$2$$$ and greater than $$$4$$$, which is $$$6$$$;
- $$$b_6$$$ is the smallest integer divisible by $$$8$$$ and greater than $$$6$$$, which is $$$8$$$;
- $$$b_7$$$ is the smallest integer divisible by $$$3$$$ and greater than $$$8$$$, which is $$$9$$$.

You have to choose the order of fishermen in a way that yields the minimum possible $$$\sum\limits_{i=1}^{n} b_i$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of fishermen.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

## Output Format
Print one integer — the minimum possible value of $$$\sum\limits_{i=1}^{n} b_i$$$ you can obtain by choosing the order of fishermen optimally.

## Examples
```input
7
1 8 2 3 2 2 3
```
```output
33
```
-----
```input
10
5 6 5 6 5 6 5 6 5 6
```
```output
165
```

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 an array $$$a$$$ of size $$$n$$$ consisting only of zeroes and ones and an integer $$$k$$$. In one operation you can do one of the following:

- Select $$$2$$$ consecutive elements of $$$a$$$ and replace them with their minimum (that is, let $$$a := [a_{1}, a_{2}, \ldots, a_{i-1}, \min(a_{i}, a_{i+1}), a_{i+2}, \ldots, a_{n}]$$$ for some $$$1 \le i \le n-1$$$). This operation decreases the size of $$$a$$$ by $$$1$$$.
- Select $$$k$$$ consecutive elements of $$$a$$$ and replace them with their maximum (that is, let $$$a := [a_{1}, a_{2}, \ldots, a_{i-1}, \max(a_{i}, a_{i+1}, \ldots, a_{i+k-1}), a_{i+k}, \ldots, a_{n}]$$$ for some $$$1 \le i \le n-k+1$$$). This operation decreases the size of $$$a$$$ by $$$k-1$$$.

Determine if it's possible to turn $$$a$$$ into $$$[1]$$$ after several (possibly zero) operations.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 50$$$), the size of array $$$a$$$ and the length of segments that you can perform second type operation on.

The second line contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$a_i$$$ is $$$0$$$ or $$$1$$$), elements of array $$$a$$$.

## Output Format
For each test case, if it is possible to turn $$$a$$$ into $$$[1]$$$, print "YES", otherwise print "NO".

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

## Note
In the first test case, you can perform the second type operation on second and third elements so $$$a$$$ becomes $$$[0, 1]$$$, then you can perform the second type operation on first and second elements, so $$$a$$$ turns to $$$[1]$$$.

In the fourth test case, it's obvious to see that you can't make any $$$1$$$, no matter what you do.

In the fifth test case, you can first perform a type 2 operation on the first three elements so that $$$a$$$ becomes $$$[1, 0, 0, 1]$$$, then perform a type 2 operation on the elements in positions two through four, so that $$$a$$$ becomes $$$[1, 1]$$$, and finally perform the first type operation on the remaining elements, so that $$$a$$$ becomes $$$[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
You have an array $$$a$$$ of size $$$n$$$ consisting only of zeroes and ones. You can do the following operation:

- choose two indices $$$1 \le i , j \le n$$$, $$$i \ne j$$$,
- add $$$a_{i}$$$ to $$$a_{j}$$$,
- remove $$$a_{i}$$$ from $$$a$$$.

Note that elements of $$$a$$$ can become bigger than $$$1$$$ after performing some operations. Also note that $$$n$$$ becomes $$$1$$$ less after the operation.

What is the minimum number of operations needed to make $$$a$$$ non-decreasing, i. e. that each element is not less than the previous element?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). 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 size of array $$$a$$$.

Next line contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots a_{n}$$$ ($$$a_i$$$ is $$$0$$$ or $$$1$$$), elements of array $$$a$$$.

It's guaranteed that sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case print a single integer, minimum number of operations needed to make $$$a$$$ non-decreasing.

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

## Note
In the first test case, $$$a$$$ is already non-decreasing, so you don't need to do any operations and the answer is $$$0$$$.

In the second test case, you can perform an operation for $$$i = 1$$$ and $$$j = 5$$$, so $$$a$$$ will be equal to $$$[0, 0, 1, 2]$$$ and it becomes non-decreasing.

In the third test case, you can perform an operation for $$$i = 2$$$ and $$$j = 1$$$, so $$$a$$$ will be equal to $$$[1]$$$ and it becomes non-decreasing.

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 are given a rooted tree consisting of $$$n$$$ vertices. The vertices are numbered from $$$1$$$ to $$$n$$$, and the root is the vertex $$$1$$$. You are also given a score array $$$s_1, s_2, \ldots, s_n$$$.

A multiset of $$$k$$$ simple paths is called valid if the following two conditions are both true.

- Each path starts from $$$1$$$.
- Let $$$c_i$$$ be the number of paths covering vertex $$$i$$$. For each pair of vertices $$$(u,v)$$$ ($$$2\le u,v\le n$$$) that have the same parent, $$$|c_u-c_v|\le 1$$$ holds.

It can be shown that it is always possible to find at least one valid multiset. Find the maximum value among all valid multisets.

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

The first line of each test case contains two space-separated integers $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) and $$$k$$$ ($$$1 \le k \le 10^9$$$) — the size of the tree and the required number of paths.

The second line contains $$$n - 1$$$ space-separated integers $$$p_2,p_3,\ldots,p_n$$$ ($$$1\le p_i\le n$$$), where $$$p_i$$$ is the parent of the $$$i$$$-th vertex. It is guaranteed that this value describe a valid tree with root $$$1$$$.

The third line contains $$$n$$$ space-separated integers $$$s_1,s_2,\ldots,s_n$$$ ($$$0 \le s_i \le 10^4$$$) — the scores of the vertices.

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, print a single integer — the maximum value of a path multiset.

## Examples
```input
2
5 4
1 2 1 3
6 2 1 5 7
5 3
1 2 1 3
6 6 1 4 10
```
```output
54
56
```

## Note
In the first test case, one of optimal solutions is four paths $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 4$$$, $$$1 \to 4$$$, here $$$c=[4,2,2,2,2]$$$. The value equals to $$$4\cdot 6+ 2\cdot 2+2\cdot 1+2\cdot 5+2\cdot 7=54$$$.

In the second test case, one of optimal solution is three paths $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 4$$$, here $$$c=[3,2,2,1,2]$$$. The value equals to $$$3\cdot 6+ 2\cdot 6+2\cdot 1+1\cdot 4+2\cdot 10=56$$$.

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
Anton decided to get ready for an Olympiad in Informatics. Ilya prepared $$$n$$$ tasks for him to solve. It is possible to submit the solution for the $$$i$$$-th task in the first $$$d_{i}$$$ days only. Anton cannot solve more than one task a day. Ilya estimated the usefulness of the $$$i$$$-th tasks as $$$r_{i}$$$ and divided the tasks into three topics, the topic of the $$$i$$$-th task is $$$type_{i}$$$.

Anton wants to solve exactly $$$a$$$ tasks on the first topic, $$$b$$$ tasks on the second topic and $$$c$$$ tasks on the third topic. Tell Anton if it is possible to do so, and if it is, calculate the maximum total usefulness of the tasks he may solve.

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

The first line of each test case contains four integers $$$n, a, b, c$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le a, b, c \le n$$$).

The following $$$n$$$ lines contain three integers each — $$$r_i, type_i, d_i$$$ ($$$0 \le r_i \le 10^{9}$$$, $$$1 \le type_i \le 3$$$, $$$1 \le d_i \le n$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case print $$$-1$$$ if Anton cannot reach his goal; otherwise, print the maximum usefulness of the tasks he will solve.

## Examples
```input
4
4 1 1 0
1 2 1
1 1 1
0 1 2
1 2 2
3 1 1 1
1 1 2
7 2 1
9 3 2
4 2 1 0
100 2 1
5 2 3
7 1 2
5 1 2
5 1 1 1
10 3 1
9 2 3
20 1 1
16 1 4
1 3 4
```
```output
2
-1
17
35
```

## Note
In the first test case from the sample test Anton can solve tasks $$$2$$$ and $$$4$$$.

In the second test case from the sample test it is impossible to fulfill Anton's wish.

In the third test case from the sample test it is optimal to solve tasks $$$2$$$, $$$3$$$ and $$$4$$$.

In the last test case from the sample test it is optimal to solve tasks $$$1$$$, $$$2$$$ and $$$4$$$.

Now solve the problem and return the code.