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

# Problem
You are given a binary matrix $$$A$$$ of size $$$n \times n$$$. Let's denote an $$$x$$$-compression of the given matrix as a matrix $$$B$$$ of size $$$\frac{n}{x} \times \frac{n}{x}$$$ such that for every $$$i \in [1, n], j \in [1, n]$$$ the condition $$$A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$$$ is met.

Obviously, $$$x$$$-compression is possible only if $$$x$$$ divides $$$n$$$, but this condition is not enough. For example, the following matrix of size $$$2 \times 2$$$ does not have any $$$2$$$-compression:

$$$01$$$

$$$10$$$

For the given matrix $$$A$$$, find maximum $$$x$$$ such that an $$$x$$$-compression of this matrix is possible.

Note that the input is given in compressed form. But even though it is compressed, you'd better use fast input.

## Input Format
The first line contains one number $$$n$$$ ($$$4 \le n \le 5200$$$) — the number of rows and columns in the matrix $$$A$$$. It is guaranteed that $$$n$$$ is divisible by $$$4$$$.

Then the representation of matrix follows. Each of $$$n$$$ next lines contains $$$\frac{n}{4}$$$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $$$0$$$ to $$$9$$$ or as uppercase Latin letters from $$$A$$$ to $$$F$$$). Binary representation of each of these numbers denotes next $$$4$$$ elements of the matrix in the corresponding row. For example, if the number $$$B$$$ is given, then the corresponding elements are 1011, and if the number is $$$5$$$, then the corresponding elements are 0101.

Elements are not separated by whitespaces.

## Output Format
Print one number: maximum $$$x$$$ such that an $$$x$$$-compression of the given matrix is possible.

## Examples
```input
8
E7
E7
E7
00
00
E7
E7
E7
```
```output
1
```
-----
```input
4
7
F
F
F
```
```output
1
```

## Note
The first example corresponds to the matrix:

$$$11100111$$$

$$$11100111$$$

$$$11100111$$$

$$$00000000$$$

$$$00000000$$$

$$$11100111$$$

$$$11100111$$$

$$$11100111$$$

It is easy to see that the answer on this example is $$$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
Vasya has a string $$$s$$$ of length $$$n$$$ consisting only of digits 0 and 1. Also he has an array $$$a$$$ of length $$$n$$$.

Vasya performs the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue together the remaining parts (any of them can be empty). For example, if he erases substring 111 from string 111110 he will get the string 110. Vasya gets $$$a_x$$$ points for erasing substring of length $$$x$$$.

Vasya wants to maximize his total points, so help him with this!

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of string $$$s$$$.

The second line contains string $$$s$$$, consisting only of digits 0 and 1.

The third line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of points for erasing the substring of length $$$i$$$.

## Output Format
Print one integer — the maximum total points Vasya can get.

## Examples
```input
7
1101001
3 4 9 100 1 2 3
```
```output
109
```
-----
```input
5
10101
3 10 15 15 15
```
```output
23
```

## Note
In the first example the optimal sequence of erasings is: 1101001 $$$\rightarrow$$$ 111001 $$$\rightarrow$$$ 11101 $$$\rightarrow$$$ 1111 $$$\rightarrow$$$ $$$\varnothing$$$.

In the second example the optimal sequence of erasings is: 10101 $$$\rightarrow$$$ 1001 $$$\rightarrow$$$ 11 $$$\rightarrow$$$ $$$\varnothing$$$.

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
Vasya wants to buy himself a nice new car. Unfortunately, he lacks some money. Currently he has exactly 0 burles.

However, the local bank has $$$n$$$ credit offers. Each offer can be described with three numbers $$$a_i$$$, $$$b_i$$$ and $$$k_i$$$. Offers are numbered from $$$1$$$ to $$$n$$$. If Vasya takes the $$$i$$$-th offer, then the bank gives him $$$a_i$$$ burles at the beginning of the month and then Vasya pays bank $$$b_i$$$ burles at the end of each month for the next $$$k_i$$$ months (including the month he activated the offer). Vasya can take the offers any order he wants.

Each month Vasya can take no more than one credit offer. Also each credit offer can not be used more than once. Several credits can be active at the same time. It implies that Vasya pays bank the sum of $$$b_i$$$ over all the $$$i$$$ of active credits at the end of each month.

Vasya wants to buy a car in the middle of some month. He just takes all the money he currently has and buys the car of that exact price.

Vasya don't really care what he'll have to pay the bank back after he buys a car. He just goes out of the country on his car so that the bank can't find him anymore.

What is the maximum price that car can have?

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

Each of the next $$$n$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$k_i$$$ ($$$1 \le a_i, b_i, k_i \le 10^9$$$).

## Output Format
Print one integer — the maximum price of the car.

## Examples
```input
4
10 9 2
20 33 1
30 115 1
5 3 2
```
```output
32
```
-----
```input
3
40 1 2
1000 1100 5
300 2 1
```
```output
1337
```

## Note
In the first example, the following sequence of offers taken is optimal: 4 $$$\rightarrow$$$ 3.

The amount of burles Vasya has changes the following way: 5 $$$\rightarrow$$$ 32 $$$\rightarrow$$$ -86 $$$\rightarrow$$$ .... He takes the money he has in the middle of the second month (32 burles) and buys the car.

The negative amount of money means that Vasya has to pay the bank that amount of burles.

In the second example, the following sequence of offers taken is optimal: 3 $$$\rightarrow$$$ 1 $$$\rightarrow$$$ 2.

The amount of burles Vasya has changes the following way: 0 $$$\rightarrow$$$ 300 $$$\rightarrow$$$ 338 $$$\rightarrow$$$ 1337 $$$\rightarrow$$$ 236 $$$\rightarrow$$$ -866 $$$\rightarrow$$$ ....

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

# Problem
Vasya got really tired of these credits (from problem F) and now wants to earn the money himself! He decided to make a contest to gain a profit.

Vasya has $$$n$$$ problems to choose from. They are numbered from $$$1$$$ to $$$n$$$. The difficulty of the $$$i$$$-th problem is $$$d_i$$$. Moreover, the problems are given in the increasing order by their difficulties. The difficulties of all tasks are pairwise distinct. In order to add the $$$i$$$-th problem to the contest you need to pay $$$c_i$$$ burles to its author. For each problem in the contest Vasya gets $$$a$$$ burles.

In order to create a contest he needs to choose a consecutive subsegment of tasks.

So the total earnings for the contest are calculated as follows:

- if Vasya takes problem $$$i$$$ to the contest, he needs to pay $$$c_i$$$ to its author;
- for each problem in the contest Vasya gets $$$a$$$ burles;
- let $$$gap(l, r) = \max\limits_{l \le i < r} (d_{i + 1} - d_i)^2$$$. If Vasya takes all the tasks with indices from $$$l$$$ to $$$r$$$ to the contest, he also needs to pay $$$gap(l, r)$$$. If $$$l = r$$$ then $$$gap(l, r) = 0$$$.

Calculate the maximum profit that Vasya can earn by taking a consecutive segment of tasks.

## Input Format
The first line contains two integers $$$n$$$ and $$$a$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le a \le 10^9$$$) — the number of proposed tasks and the profit for a single problem, respectively.

Each of the next $$$n$$$ lines contains two integers $$$d_i$$$ and $$$c_i$$$ ($$$1 \le d_i, c_i \le 10^9, d_i < d_{i+1}$$$).

## Output Format
Print one integer — maximum amount of burles Vasya can earn.

## Examples
```input
5 10
1 15
5 3
6 11
7 2
11 22
```
```output
13
```
-----
```input
3 5
1 8
2 19
3 11
```
```output
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
After lessons Nastya decided to read a book. The book contains $$$n$$$ chapters, going one after another, so that one page of the book belongs to exactly one chapter and each chapter contains at least one page.

Yesterday evening Nastya did not manage to finish reading the book, so she marked the page with number $$$k$$$ as the first page which was not read (i.e. she read all pages from the $$$1$$$-st to the $$$(k-1)$$$-th).

The next day Nastya's friend Igor came and asked her, how many chapters remain to be read by Nastya? Nastya is too busy now, so she asks you to compute the number of chapters she has not completely read yet (i.e. the number of chapters she has not started to read or has finished reading somewhere in the middle).

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of chapters in the book.

There are $$$n$$$ lines then. The $$$i$$$-th of these lines contains two integers $$$l_i$$$, $$$r_i$$$ separated by space ($$$l_1 = 1$$$, $$$l_i \leq r_i$$$) — numbers of the first and the last pages of the $$$i$$$-th chapter. It's guaranteed that $$$l_{i+1} = r_i + 1$$$ for all $$$1 \leq i \leq n-1$$$, and also that every chapter contains at most $$$100$$$ pages.

The $$$(n+2)$$$-th line contains a single integer $$$k$$$ ($$$1 \leq k \leq r_n$$$) — the index of the marked page.

## Output Format
Print a single integer — the number of chapters which has not been completely read so far.

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

## Note
In the first example the book contains $$$11$$$ pages and $$$3$$$ chapters — $$$[1;3]$$$, $$$[4;7]$$$ and $$$[8;11]$$$. Nastya marked the $$$2$$$-nd page, so she finished in the middle of the $$$1$$$-st chapter. So, all chapters has not been read so far, so the answer is $$$3$$$.

The book in the second example contains $$$12$$$ pages and $$$3$$$ chapters too, but Nastya finished reading in the middle of the $$$2$$$-nd chapter, so that the answer 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Finished her homework, Nastya decided to play computer games. Passing levels one by one, Nastya eventually faced a problem. Her mission is to leave a room, where a lot of monsters live, as quickly as possible.

There are $$$n$$$ manholes in the room which are situated on one line, but, unfortunately, all the manholes are closed, and there is one stone on every manhole. There is exactly one coin under every manhole, and to win the game Nastya should pick all the coins. Initially Nastya stands near the $$$k$$$-th manhole from the left. She is thinking what to do.

In one turn, Nastya can do one of the following:

- if there is at least one stone on the manhole Nastya stands near, throw exactly one stone from it onto any other manhole (yes, Nastya is strong).
- go to a neighboring manhole;
- if there are no stones on the manhole Nastya stays near, she can open it and pick the coin from it. After it she must close the manhole immediately (it doesn't require additional moves).

The figure shows the intermediate state of the game. At the current position Nastya can throw the stone to any other manhole or move left or right to the neighboring manholes. If she were near the leftmost manhole, she could open it (since there are no stones on it).

Nastya can leave the room when she picks all the coins. Monsters are everywhere, so you need to compute the minimum number of moves Nastya has to make to pick all the coins.

Note one time more that Nastya can open a manhole only when there are no stones onto it.

## Input Format
The first and only line contains two integers $$$n$$$ and $$$k$$$, separated by space ($$$2 \leq n \leq 5000$$$, $$$1 \leq k \leq n$$$) — the number of manholes and the index of manhole from the left, near which Nastya stays initially. Initially there is exactly one stone near each of the $$$n$$$ manholes.

## Output Format
Print a single integer — minimum number of moves which lead Nastya to pick all the coins.

## Examples
```input
2 2
```
```output
6
```
-----
```input
4 2
```
```output
13
```
-----
```input
5 1
```
```output
15
```

## Note
Let's consider the example where $$$n = 2$$$, $$$k = 2$$$. Nastya should play as follows:

- At first she throws the stone from the second manhole to the first. Now there are two stones on the first manhole.
- Then she opens the second manhole and pick the coin from it.
- Then she goes to the first manhole, throws two stones by two moves to the second manhole and then opens the manhole and picks the coin from it.

So, $$$6$$$ moves are required to win.

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
In this task, Nastya asked us to write a formal statement.

An array $$$a$$$ of length $$$n$$$ and an array $$$k$$$ of length $$$n-1$$$ are given. Two types of queries should be processed:

- increase $$$a_i$$$ by $$$x$$$. Then if $$$a_{i+1} < a_i + k_i$$$, $$$a_{i+1}$$$ becomes exactly $$$a_i + k_i$$$; again, if $$$a_{i+2} < a_{i+1} + k_{i+1}$$$, $$$a_{i+2}$$$ becomes exactly $$$a_{i+1} + k_{i+1}$$$, and so far for $$$a_{i+3}$$$, ..., $$$a_n$$$;
- print the sum of the contiguous subarray from the $$$l$$$-th element to the $$$r$$$-th element of the array $$$a$$$.

It's guaranteed that initially $$$a_i + k_i \leq a_{i+1}$$$ for all $$$1 \leq i \leq n-1$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^{5}$$$) — the number of elements in the array $$$a$$$.

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

The third line contains $$$n-1$$$ integers $$$k_1, k_2, \ldots, k_{n-1}$$$ ($$$-10^{6} \leq k_i \leq 10^{6}$$$) — the elements of the array $$$k$$$.

The fourth line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^{5}$$$) — the number of queries.

Each of the following $$$q$$$ lines contains a query of one of two types:

- if the query has the first type, the corresponding line contains the character '+' (without quotes), and then there are two integers $$$i$$$ and $$$x$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq x \leq 10^{6}$$$), it means that integer $$$x$$$ is added to the $$$i$$$-th element of the array $$$a$$$ as described in the statement.
- if the query has the second type, the corresponding line contains the character 's' (without quotes) and then there are two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$).

## Output Format
For each query of the second type print a single integer in a new line — the sum of the corresponding subarray.

## Examples
```input
3
1 2 3
1 -1
5
s 2 3
+ 1 2
s 1 2
+ 3 1
s 2 3
```
```output
5
7
8
```
-----
```input
3
3 6 7
3 1
3
+ 1 3
+ 2 4
s 1 3
```
```output
33
```

## Note
In the first example:

- after the first change $$$a = [3, 4, 3]$$$;
- after the second change $$$a = [3, 4, 4]$$$.

In the second example:

- after the first change $$$a = [6, 9, 10]$$$;
- after the second change $$$a = [6, 13, 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$, where $$$n$$$ is an even number.

Your goal is to sort the permutation. To do so, you can perform zero or more operations of the following type:

- take two indices $$$i$$$ and $$$j$$$ such that $$$2 \cdot |i - j| \geq n$$$ and swap $$$p_i$$$ and $$$p_j$$$.

There is no need to minimize the number of operations, however you should use no more than $$$5 \cdot n$$$ operations. One can show that it is always possible to do that.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$n$$$ is even) — the length of the permutation.

The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the given permutation.

## Output Format
On the first line print $$$m$$$ ($$$0 \le m \le 5 \cdot n$$$) — the number of swaps to perform.

Each of the following $$$m$$$ lines should contain integers $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$|a_i - b_i| \ge \frac{n}{2}$$$) — the indices that should be swapped in the corresponding swap.

Note that there is no need to minimize the number of operations. We can show that an answer always exists.

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

## Note
In the first example, when one swap elements on positions $$$1$$$ and $$$2$$$, the array becomes sorted.

In the second example, pay attention that there is no need to minimize number of swaps.

In the third example, after swapping elements on positions $$$1$$$ and $$$5$$$ the array becomes: $$$[4, 5, 3, 1, 2, 6]$$$. After swapping elements on positions $$$2$$$ and $$$5$$$ the array becomes $$$[4, 2, 3, 1, 5, 6]$$$ and finally after swapping elements on positions $$$1$$$ and $$$4$$$ the array becomes sorted: $$$[1, 2, 3, 4, 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ pairs of integers $$$(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$$$. All of the integers in the pairs are distinct and are in the range from $$$1$$$ to $$$2 \cdot n$$$ inclusive.

Let's call a sequence of integers $$$x_1, x_2, \ldots, x_{2k}$$$ good if either

- $$$x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k}$$$, or
- $$$x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k}$$$.

You need to choose a subset of distinct indices $$$i_1, i_2, \ldots, i_t$$$ and their order in a way that if you write down all numbers from the pairs in a single sequence (the sequence would be $$$a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t}$$$), this sequence is good.

What is the largest subset of indices you can choose? You also need to construct the corresponding index sequence $$$i_1, i_2, \ldots, i_t$$$.

## Input Format
The first line contains single integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — the number of pairs.

Each of the next $$$n$$$ lines contain two numbers — $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 2 \cdot n$$$) — the elements of the pairs.

It is guaranteed that all integers in the pairs are distinct, that is, every integer from $$$1$$$ to $$$2 \cdot n$$$ is mentioned exactly once.

## Output Format
In the first line print a single integer $$$t$$$ — the number of pairs in the answer.

Then print $$$t$$$ distinct integers $$$i_1, i_2, \ldots, i_t$$$ — the indexes of pairs in the corresponding order.

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

## Note
The final sequence in the first example is $$$1 < 7 > 3 < 5 > 2 < 10$$$.

The final sequence in the second example is $$$6 > 1 < 3 > 2 < 5 > 4$$$.

Now solve the problem and return the code.