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
Let's imagine that you're playing the following simple computer game. The screen displays n lined-up cubes. Each cube is painted one of m colors. You are allowed to delete not more than k cubes (that do not necessarily go one after another). After that, the remaining cubes join together (so that the gaps are closed) and the system counts the score. The number of points you score equals to the length of the maximum sequence of cubes of the same color that follow consecutively. Write a program that determines the maximum possible number of points you can score.

Remember, you may delete no more than k any cubes. It is allowed not to delete cubes at all.

## Input Format
The first line contains three integers n, m and k (1 ≤ n ≤ 2·105, 1 ≤ m ≤ 105, 0 ≤ k < n). The second line contains n integers from 1 to m — the numbers of cube colors. The numbers of colors are separated by single spaces.

## Output Format
Print the maximum possible number of points you can score.

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

## Note
In the first sample you should delete the fifth and the sixth cubes.

In the second sample you should delete the fourth and the seventh cubes.

In the third sample you shouldn't delete any cubes.

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
Students of group 199 have written their lectures dismally. Now an exam on Mathematical Analysis is approaching and something has to be done asap (that is, quickly). Let's number the students of the group from 1 to n. Each student i (1 ≤ i ≤ n) has a best friend p[i] (1 ≤ p[i] ≤ n). In fact, each student is a best friend of exactly one student. In other words, all p[i] are different. It is possible that the group also has some really "special individuals" for who i = p[i].

Each student wrote exactly one notebook of lecture notes. We know that the students agreed to act by the following algorithm:

- on the first day of revising each student studies his own Mathematical Analysis notes,
- in the morning of each following day each student gives the notebook to his best friend and takes a notebook from the student who calls him the best friend.

Thus, on the second day the student p[i] (1 ≤ i ≤ n) studies the i-th student's notes, on the third day the notes go to student p[p[i]] and so on. Due to some characteristics of the boys' friendship (see paragraph 1), each day each student has exactly one notebook to study.

You are given two sequences that describe the situation on the third and fourth days of revising:

- a1, a2, ..., an, where ai means the student who gets the i-th student's notebook on the third day of revising;
- b1, b2, ..., bn, where bi means the student who gets the i-th student's notebook on the fourth day of revising.

You do not know array p, that is you do not know who is the best friend to who. Write a program that finds p by the given sequences a and b.

## Input Format
The first line contains integer n (1 ≤ n ≤ 105) — the number of students in the group. The second line contains sequence of different integers a1, a2, ..., an (1 ≤ ai ≤ n). The third line contains the sequence of different integers b1, b2, ..., bn (1 ≤ bi ≤ n).

## Output Format
Print sequence n of different integers p[1], p[2], ..., p[n] (1 ≤ p[i] ≤ n). It is guaranteed that the solution exists and that it is unique.

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

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Ian and Mary are frogs living on lattice points of the Cartesian coordinate plane, with Ian living on $$$(0,0)$$$ and Mary living on $$$(a,b)$$$.

Ian would like to visit Mary by jumping around the Cartesian coordinate plane. Every second, he jumps from his current position $$$(x_p, y_p)$$$ to another lattice point $$$(x_q, y_q)$$$, such that no lattice point other than $$$(x_p, y_p)$$$ and $$$(x_q, y_q)$$$ lies on the segment between point $$$(x_p, y_p)$$$ and point $$$(x_q, y_q)$$$.

As Ian wants to meet Mary as soon as possible, he wants to jump towards point $$$(a,b)$$$ using at most $$$2$$$ jumps. Unfortunately, Ian is not good at maths. Can you help him?

A lattice point is defined as a point with both the $$$x$$$-coordinate and $$$y$$$-coordinate being integers.

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

The first and only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1\le a,b\le 10^9$$$) — the coordinates of the lattice point where Mary lives.

## Output Format
For each test case, print an integer $$$n$$$ ($$$1 \le n \le 2$$$) on the first line, denoting the number of jumps Ian uses in order to meet Mary. Note that you do not need to minimize the number of jumps.

On the $$$i$$$-th line of the next $$$n$$$ lines, print two integers $$$0 \le x_i,y_i \le 10^9$$$ separated by a space, denoting Ian's location $$$(x_i,y_i)$$$ after the $$$i$$$-th jump. $$$x_n = a$$$, $$$y_n = b$$$ must hold.

Ian's initial location and his locations after each of the $$$n$$$ jumps need not be distinct.

If there are multiple solutions, output any.

## Examples
```input
8
3 4
4 4
3 6
2 2
1 1
7 3
2022 2023
1000000000 1000000000
```
```output
1
3 4
2
3 2
4 4
2
5 3
3 6
2
1 0
2 2
1
1 1
1
7 3
1
2022 2023
2
69420420 469696969
1000000000 1000000000
```

## Note
In the first test case:

$$$(0,0) \to (3,4)$$$

In the second test case:

$$$(0,0) \to (3,2) \to (4,4)$$$

In the third test case:

$$$(0,0) \to (5,3) \to (3,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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Consider a $$$2 \times n$$$ grid, where $$$n$$$ is an even integer. You may place the integers $$$1, 2, \ldots, 2n$$$ on the grid, using each integer exactly once.

A path is a sequence of cells achieved by starting at $$$(1, 1)$$$, then repeatedly walking either downwards or to the right, and stopping when $$$(2, n)$$$ is reached. The path should not extend beyond the grid.

The cost of a path is the alternating sum of the numbers written on the cells in a path. That is, let the numbers written on the cells be $$$a_1, a_2, \ldots, a_k$$$ (in the order that it is visited), the cost of the path is $$$a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}$$$.

Construct a way to place the integers $$$1, 2, \ldots, 2n$$$ on the grid, such that the minimum cost over all paths from $$$(1, 1)$$$ to $$$(2, n)$$$ is maximized. If there are multiple such grids that result in the maximum value, output any of them.

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

The first and the only line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$, $$$n$$$ is even) — the number of the columns in the grid.

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

## Output Format
For each test case, output $$$2$$$ lines, each containing $$$n$$$ integers — the desired grid. If there are multiple solutions, output any of them.

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

## Note
In the first test case, there are only two paths from cell $$$(1, 1)$$$ to cell $$$(2, 2)$$$. Their costs are $$$3-1+4=6$$$ and $$$3-2+4=5$$$. Then the minimum cost is $$$5$$$, which is the maximum possible value.

In the second test case, there are four paths from cell $$$(1, 1)$$$ to cell $$$(2, 4)$$$. Their costs are $$$8-1+5-3+7=16$$$, $$$8-2+5-3+7=15$$$, $$$8-2+6-3+7=16$$$, and $$$8-2+6-4+7=15$$$. Then the minimum value is $$$15$$$, which is the maximum possible value.

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
Consider an array $$$a_1, a_2, \dots, a_n$$$ consisting of numbers $$$1$$$ and $$$-1$$$. Define $$$A$$$-characteristic of this array as a number of pairs of indices $$$1 \le i < j \le n$$$, such that $$$a_i \cdot a_j = 1$$$.

Find any array $$$a$$$ with given length $$$n$$$ with $$$A$$$-characteristic equal to the given value $$$k$$$.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100$$$; $$$0 \le k \le \frac{(n-1) n}{2}$$$) — the length of required array and required $$$A$$$-characteristic.

## Output Format
For each test case, if there is no array $$$a$$$ with given $$$A$$$-characteristic $$$k$$$, print NO.

Otherwise, print YES and $$$n$$$ numbers $$$1$$$ and $$$-1$$$, which form the required array $$$a$$$. If there are multiple answers, print any of them.

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

## Note
In the first test case, there is only one pair of different elements in the array, and their product is $$$a_1 \cdot a_2 = -1 \neq 1$$$, hence its $$$A$$$-characteristic is $$$0$$$.

In the second test case, there is only one pair of different elements in the array, and their product is $$$a_1 \cdot a_2 = 1$$$, hence its $$$A$$$-characteristic is $$$1$$$.

In the third test case, there are three pairs of different elements in the array, and their product are: $$$a_1 \cdot a_2 = -1$$$, $$$a_1 \cdot a_3 = 1$$$, $$$a_2 \cdot a_3 = -1$$$, hence its $$$A$$$-characteristic is $$$1$$$.

In the fourth test case, we can show, that there is no array with length $$$3$$$, which $$$A$$$-characteristic is $$$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
Alice and Bob are playing a game on a graph. They have an undirected graph without self-loops and multiple edges. All vertices of the graph have degree equal to $$$2$$$. The graph may consist of several components. Note that if such graph has $$$n$$$ vertices, it will have exactly $$$n$$$ edges.

Alice and Bob take turn. Alice goes first. In each turn, the player can choose $$$k$$$ ($$$l \le k \le r$$$; $$$l < r$$$) vertices that form a connected subgraph and erase these vertices from the graph, including all incident edges.

The player who can't make a step loses.

For example, suppose they are playing on the given graph with given $$$l = 2$$$ and $$$r = 3$$$:

A valid vertex set for Alice to choose at the first move is one of the following:

- $$$\{1, 2\}$$$
- $$$\{1, 3\}$$$
- $$$\{2, 3\}$$$
- $$$\{4, 5\}$$$
- $$$\{4, 6\}$$$
- $$$\{5, 6\}$$$
- $$$\{1, 2, 3\}$$$
- $$$\{4, 5, 6\}$$$

Then a valid vertex set for Bob to choose at the first move is one of the following:

- $$$\{1, 2\}$$$
- $$$\{1, 3\}$$$
- $$$\{2, 3\}$$$
- $$$\{1, 2, 3\}$$$

Alice can't make a move, so she loses.

You are given a graph of size $$$n$$$ and integers $$$l$$$ and $$$r$$$. Who will win if both Alice and Bob play optimally.

## Input Format
The first line contains three integers $$$n$$$, $$$l$$$ and $$$r$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le l < r \le n$$$) — the number of vertices in the graph, and the constraints on the number of vertices Alice or Bob can choose in one move.

Next $$$n$$$ lines contains edges of the graph: one edge per line. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — description of the $$$i$$$-th edge.

It's guaranteed that the degree of each vertex of the given graph is equal to $$$2$$$.

## Output Format
Print Alice (case-insensitive) if Alice wins, or Bob otherwise.

## Examples
```input
6 2 3
1 2
2 3
3 1
4 5
5 6
6 4
```
```output
Bob
```
-----
```input
6 1 2
1 2
2 3
3 1
4 5
5 6
6 4
```
```output
Bob
```
-----
```input
12 1 3
1 2
2 3
3 1
4 5
5 6
6 7
7 4
8 9
9 10
10 11
11 12
12 8
```
```output
Alice
```

## Note
In the first test the same input as in legend is shown.

In the second test the same graph as in legend is shown, but with $$$l = 1$$$ and $$$r = 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
No, not "random" numbers.

Ranom digits are denoted by uppercase Latin letters from A to E. Moreover, the value of the letter A is $$$1$$$, B is $$$10$$$, C is $$$100$$$, D is $$$1000$$$, E is $$$10000$$$.

A Ranom number is a sequence of Ranom digits. The value of the Ranom number is calculated as follows: the values of all digits are summed up, but some digits are taken with negative signs: a digit is taken with negative sign if there is a digit with a strictly greater value to the right of it (not necessarily immediately after it); otherwise, that digit is taken with a positive sign.

For example, the value of the Ranom number DAAABDCA is $$$1000 - 1 - 1 - 1 - 10 + 1000 + 100 + 1 = 2088$$$.

You are given a Ranom number. You can change no more than one digit in it. Calculate the maximum possible value of the resulting number.

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

The only line of each test case contains a string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) consisting of uppercase Latin letters from A to E — the Ranom number you are given.

The sum of the string lengths over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the maximum possible value of the number, if you can change no more than one digit in it.

## Examples
```input
4
DAAABDCA
AB
ABCDEEDCBA
DDDDAAADDABECD
```
```output
11088
10010
31000
15886
```

## Note
In the first example, you can get EAAABDCA with the value $$$10000-1-1-1-10+1000+100+1=11088$$$.

In the second example, you can get EB with the value $$$10000+10=10010$$$.

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 is a square matrix, consisting of $$$n$$$ rows and $$$n$$$ columns of cells, both numbered from $$$1$$$ to $$$n$$$. The cells are colored white or black. Cells from $$$1$$$ to $$$a_i$$$ are black, and cells from $$$a_i+1$$$ to $$$n$$$ are white, in the $$$i$$$-th column.

You want to place $$$m$$$ integers in the matrix, from $$$1$$$ to $$$m$$$. There are two rules:

- each cell should contain at most one integer;
- black cells should not contain integers.

The beauty of the matrix is the number of such $$$j$$$ that $$$j+1$$$ is written in the same row, in the next column as $$$j$$$ (in the neighbouring cell to the right).

What's the maximum possible beauty of the matrix?

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — the number of black cells in each column.

The third line contains a single integer $$$m$$$ ($$$0 \le m \le \sum \limits_{i=1}^n n - a_i$$$) — the number of integers you have to write in the matrix. Note that this number might not fit into a 32-bit integer data type.

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

## Output Format
For each testcase, print a single integer — the maximum beauty of the matrix after you write all $$$m$$$ integers in it. Note that there are no more integers than the white cells, so the answer always exists.

## Examples
```input
6
3
0 0 0
9
4
2 0 3 1
5
4
2 0 3 1
6
4
2 0 3 1
10
10
0 2 2 1 5 10 3 4 1 1
20
1
1
0
```
```output
6
3
4
4
16
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: 5.0 seconds
Memory limit: 1024.0 MB

# Problem
Entering senior high school life, Tom is attracted by LIS problems, not only the Longest Increasing Subsequence problem, but also the Largest Interval Sum problem. Now he gets a really interesting problem from his friend Daniel. However, it seems too hard for him to solve it, so he asks you for help.

Given an array $$$a$$$ consisting of $$$n$$$ integers.

In one operation, you do the following:

- Select an interval $$$[l,r]$$$ ($$$1\le l\le r\le n$$$), such that the sum of the interval is the largest among all intervals in the array $$$a$$$. More formally, $$$\displaystyle\sum_{i=l}^r a_i=\max_{1\le l'\le r'\le n}\sum_{i=l'}^{r'} a_i$$$.
- Then subtract $$$1$$$ from all elements $$$a_l,a_{l+1},\ldots,a_r$$$.

Find the minimum number of operations you need to perform to make $$$a_i<0$$$ for every $$$1\le i\le n$$$.

## Input Format
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of the array $$$a$$$.

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

## Output Format
Print a single integer — the minimum number of operations.

## Examples
```input
5
1 2 3 4 5
```
```output
6
```
-----
```input
6
-1 -5 -4 -1 -4 -7
```
```output
0
```
-----
```input
11
0 1000000 1 -50000 2 998353 3 -100007 4 200943 0
```
```output
1936973
```

## Note
In the first example, you can do operations on intervals $$$[1,5],[1,5],[2,5],[3,5],[4,5],[5,5]$$$ in such order. You may also do operations on intervals $$$[1,5],[2,5],[3,5],[4,5],[5,5],[1,5]$$$ in such order.

In the second example, it's already satisfied that $$$a_i<0$$$ for every $$$1\le i\le n$$$. So you do not need to perform any operations.

Now solve the problem and return the code.