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
Dima and Anya love playing different games. Now Dima has imagined a new game that he wants to play with Anya.

Dima writes n pairs of integers on a piece of paper (li, ri) (1 ≤ li < ri ≤ p). Then players take turns. On his turn the player can do the following actions:

1. choose the number of the pair i (1 ≤ i ≤ n), such that ri - li > 2;
2. replace pair number i by pair $$( l _ { i } + \left\lfloor \frac { r _ { i } - l _ { i } } { 3 } \right\rfloor, l _ { i } + 2 \cdot \left\lfloor \frac { r _ { i } - l _ { i } } { 3 } \right\rfloor )$$ or by pair $$( l _ { i }, r _ { i } - \left\lfloor \frac { r _ { i } - l _ { i } } { 3 } \right\rfloor )$$. Notation ⌊x⌋ means rounding down to the closest integer.

The player who can't make a move loses.

Of course, Dima wants Anya, who will move first, to win. That's why Dima should write out such n pairs of integers (li, ri) (1 ≤ li < ri ≤ p), that if both players play optimally well, the first one wins. Count the number of ways in which Dima can do it. Print the remainder after dividing the answer by number 1000000007 (109 + 7).

Two ways are considered distinct, if the ordered sequences of the written pairs are distinct.

## Input Format
The first line contains two integers n, p (1 ≤ n ≤ 1000, 1 ≤ p ≤ 109). The numbers are separated by a single space.

## Output Format
In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109 + 7).

## Examples
```input
2 2
```
```output
0
```
-----
```input
4 4
```
```output
520
```
-----
```input
100 1000
```
```output
269568947
```

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
A root tree is a directed acyclic graph that contains one node (root), from which there is exactly one path to any other node.

A root tree is binary if each node has at most two outgoing arcs.

When a binary tree is painted on the plane, all arcs should be directed from top to bottom. That is, each arc going from u to v must meet the condition yu > yv.

You've been given the coordinates of all tree nodes. Your task is to connect these nodes by arcs so as to get the binary root tree and make the total length of the arcs minimum. All arcs of the built tree must be directed from top to bottom.

## Input Format
The first line contains a single integer n (2 ≤ n ≤ 400) — the number of nodes in the tree. Then follow n lines, two integers per line: xi, yi (|xi|, |yi| ≤ 103) — coordinates of the nodes. It is guaranteed that all points are distinct.

## Output Format
If it is impossible to build a binary root tree on the given points, print "-1". Otherwise, print a single real number — the total length of the arcs in the minimum binary tree. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

## Examples
```input
3
0 0
1 0
2 1
```
```output
3.650281539872885
```
-----
```input
4
0 0
1 0
2 1
2 0
```
```output
-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
The classic programming language of Bitland is Bit++. This language is so peculiar and complicated.

The language is that peculiar as it has exactly one variable, called x. Also, there are two operations:

- Operation ++ increases the value of variable x by 1.
- Operation -- decreases the value of variable x by 1.

A statement in language Bit++ is a sequence, consisting of exactly one operation and one variable x. The statement is written without spaces, that is, it can only contain characters "+", "-", "X". Executing a statement means applying the operation it contains.

A programme in Bit++ is a sequence of statements, each of them needs to be executed. Executing a programme means executing all the statements it contains.

You're given a programme in language Bit++. The initial value of x is 0. Execute the programme and find its final value (the value of the variable when this programme is executed).

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 150) — the number of statements in the programme.

Next n lines contain a statement each. Each statement contains exactly one operation (++ or --) and exactly one variable x (denoted as letter «X»). Thus, there are no empty statements. The operation and the variable can be written in any order.

## Output Format
Print a single integer — the final value of x.

## Examples
```input
1
++X
```
```output
1
```
-----
```input
2
X++
--X
```
```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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
The Bitlandians are quite weird people. They have very peculiar customs.

As is customary, Uncle J. wants to have n eggs painted for Bitruz (an ancient Bitland festival). He has asked G. and A. to do the work.

The kids are excited because just as is customary, they're going to be paid for the job!

Overall uncle J. has got n eggs. G. named his price for painting each egg. Similarly, A. named his price for painting each egg. It turns out that for each egg the sum of the money both A. and G. want for the painting equals 1000.

Uncle J. wants to distribute the eggs between the children so as to give each egg to exactly one child. Also, Uncle J. wants the total money paid to A. to be different from the total money paid to G. by no more than 500.

Help Uncle J. Find the required distribution of eggs or otherwise say that distributing the eggs in the required manner is impossible.

## Input Format
The first line contains integer n (1 ≤ n ≤ 106) — the number of eggs.

Next n lines contain two integers ai and gi each (0 ≤ ai, gi ≤ 1000; ai + gi = 1000): ai is the price said by A. for the i-th egg and gi is the price said by G. for the i-th egg.

## Output Format
If it is impossible to assign the painting, print "-1" (without quotes).

Otherwise print a string, consisting of n letters "G" and "A". The i-th letter of this string should represent the child who will get the i-th egg in the required distribution. Letter "A" represents A. and letter "G" represents G. If we denote the money Uncle J. must pay A. for the painting as Sa, and the money Uncle J. must pay G. for the painting as Sg, then this inequality must hold: |Sa  -  Sg|  ≤  500.

If there are several solutions, you are allowed to print any of them.

## Examples
```input
2
1 999
999 1
```
```output
AG
```
-----
```input
3
400 600
400 600
400 600
```
```output
AGA
```

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
Since most contestants do not read this part, I have to repeat that Bitlandians are quite weird. They have their own jobs, their own working method, their own lives, their own sausages and their own games!

Since you are so curious about Bitland, I'll give you the chance of peeking at one of these games.

BitLGM and BitAryo are playing yet another of their crazy-looking genius-needed Bitlandish games. They've got a sequence of n non-negative integers a1, a2, ..., an. The players make moves in turns. BitLGM moves first. Each player can and must do one of the two following actions in his turn:

- Take one of the integers (we'll denote it as ai). Choose integer x (1 ≤ x ≤ ai). And then decrease ai by x, that is, apply assignment: ai = ai - x.
- Choose integer x $$(1 \leq x \leq \min_{i=1}^{n} a_i)$$. And then decrease all ai by x, that is, apply assignment: ai = ai - x, for all i.

The player who cannot make a move loses.

You're given the initial sequence a1, a2, ..., an. Determine who wins, if both players plays optimally well and if BitLGM and BitAryo start playing the described game in this sequence.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 3).

The next line contains n integers a1, a2, ..., an (0 ≤ ai < 300).

## Output Format
Write the name of the winner (provided that both players play optimally well). Either "BitLGM" or "BitAryo" (without the quotes).

## Examples
```input
2
1 1
```
```output
BitLGM
```
-----
```input
2
1 2
```
```output
BitAryo
```
-----
```input
3
1 2 1
```
```output
BitLGM
```

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 Bitlandians are quite weird people. They have their own problems and their own solutions. They have their own thoughts and their own beliefs, they have their own values and their own merits. They have their own dishes and their own sausages!

In Bitland a sausage is an array of integers! A sausage's deliciousness is equal to the bitwise excluding OR (the xor operation) of all integers in that sausage.

One day, when Mr. Bitkoch (the local cook) was going to close his BitRestaurant, BitHaval and BitAryo, the most famous citizens of Bitland, entered the restaurant and each ordered a sausage.

But Mr. Bitkoch had only one sausage left. So he decided to cut a prefix (several, may be zero, first array elements) of the sausage and give it to BitHaval and a postfix (several, may be zero, last array elements) of the sausage and give it to BitAryo. Note that one or both pieces of the sausage can be empty. Of course, the cut pieces mustn't intersect (no array element can occur in both pieces).

The pleasure of BitHaval and BitAryo is equal to the bitwise XOR of their sausages' deliciousness. An empty sausage's deliciousness equals zero.

Find a way to cut a piece of sausage for BitHaval and BitAryo that maximizes the pleasure of these worthy citizens.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 105).

The next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 1012) — Mr. Bitkoch's sausage.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

## Output Format
Print a single integer — the maximum pleasure BitHaval and BitAryo can get from the dinner.

## Examples
```input
2
1 2
```
```output
3
```
-----
```input
3
1 2 3
```
```output
3
```
-----
```input
2
1000 1000
```
```output
1000
```

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
Ilya is a very clever lion, he lives in an unusual city ZooVille. In this city all the animals have their rights and obligations. Moreover, they even have their own bank accounts. The state of a bank account is an integer. The state of a bank account can be a negative number. This means that the owner of the account owes the bank money.

Ilya the Lion has recently had a birthday, so he got a lot of gifts. One of them (the gift of the main ZooVille bank) is the opportunity to delete the last digit or the digit before last from the state of his bank account no more than once. For example, if the state of Ilya's bank account is -123, then Ilya can delete the last digit and get his account balance equal to -12, also he can remove its digit before last and get the account balance equal to -13. Of course, Ilya is permitted not to use the opportunity to delete a digit from the balance.

Ilya is not very good at math, and that's why he asks you to help him maximize his bank account. Find the maximum state of the bank account that can be obtained using the bank's gift.

## Input Format
The single line contains integer n (10 ≤ |n| ≤ 109) — the state of Ilya's bank account.

## Output Format
In a single line print an integer — the maximum state of the bank account that Ilya can get.

## Examples
```input
2230
```
```output
2230
```
-----
```input
-10
```
```output
0
```
-----
```input
-100003
```
```output
-10000
```

## Note
In the first test sample Ilya doesn't profit from using the present.

In the second test sample you can delete digit 1 and get the state of the account equal to 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string s = s1s2... sn (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers li, ri (1 ≤ li < ri ≤ n). The answer to the query li, ri is the number of such integers i (li ≤ i < ri), that si = si + 1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.

## Input Format
The first line contains string s of length n (2 ≤ n ≤ 105). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers li, ri (1 ≤ li < ri ≤ n).

## Output Format
Print m integers — the answers to the queries in the order in which they are given in the input.

## Examples
```input
......
4
3 4
2 3
1 6
2 6
```
```output
1
1
5
4
```
-----
```input
#..###
5
1 3
5 6
1 5
3 6
3 4
```
```output
1
1
2
2
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
Ilya is a very good-natured lion. He likes maths. Of all mathematical objects, his favourite one is matrices. Now he's faced a complicated matrix problem he needs to solve.

He's got a square 2n × 2n-sized matrix and 4n integers. You need to arrange all these numbers in the matrix (put each number in a single individual cell) so that the beauty of the resulting matrix with numbers is maximum.

The beauty of a 2n × 2n-sized matrix is an integer, obtained by the following algorithm:

1. Find the maximum element in the matrix. Let's denote it as m.
2. If n = 0, then the beauty of the matrix equals m. Otherwise, a matrix can be split into 4 non-intersecting 2n - 1 × 2n - 1-sized submatrices, then the beauty of the matrix equals the sum of number m and other four beauties of the described submatrices.

As you can see, the algorithm is recursive.

Help Ilya, solve the problem and print the resulting maximum beauty of the matrix.

## Input Format
The first line contains integer 4n (1 ≤ 4n ≤ 2·106). The next line contains 4n integers ai (1 ≤ ai ≤ 109) — the numbers you need to arrange in the 2n × 2n-sized matrix.

## Output Format
On a single line print the maximum value of the beauty of the described matrix.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

## Examples
```input
1
13
```
```output
13
```
-----
```input
4
1 2 3 4
```
```output
14
```

## Note
Consider the second sample. You need to arrange the numbers in the matrix as follows:

Then the beauty of the matrix will equal: 4 + 1 + 2 + 3 + 4 = 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
Everything is great about Ilya's city, except the roads. The thing is, the only ZooVille road is represented as n holes in a row. We will consider the holes numbered from 1 to n, from left to right.

Ilya is really keep on helping his city. So, he wants to fix at least k holes (perharps he can fix more) on a single ZooVille road.

The city has m building companies, the i-th company needs ci money units to fix a road segment containing holes with numbers of at least li and at most ri. The companies in ZooVille are very greedy, so, if they fix a segment containing some already fixed holes, they do not decrease the price for fixing the segment.

Determine the minimum money Ilya will need to fix at least k holes.

## Input Format
The first line contains three integers n, m, k (1 ≤ n ≤ 300, 1 ≤ m ≤ 105, 1 ≤ k ≤ n). The next m lines contain the companies' description. The i-th line contains three integers li, ri, ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ci ≤ 109).

## Output Format
Print a single integer — the minimum money Ilya needs to fix at least k holes.

If it is impossible to fix at least k holes, print -1.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

## Examples
```input
10 4 6
7 9 11
6 9 13
7 7 7
3 5 6
```
```output
17
```
-----
```input
10 7 1
3 4 15
8 9 8
5 6 8
9 10 6
1 4 2
1 4 10
8 10 13
```
```output
2
```
-----
```input
10 1 9
5 10 14
```
```output
-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
Ilya has recently taken up archaeology. He's recently found two numbers, written in the m-based notation. Each of the found numbers consisted of exactly n digits. Ilya immediately started looking for information about those numbers. He learned that the numbers are part of a cyphered code and the one who can decypher it can get the greatest treasure.

After considerable research Ilya understood that to decypher the code, he should do the following:

- Rearrange digits in the first number in some manner. Similarly, rearrange digits in the second number in some manner. As a result of this operation, the numbers can get leading zeroes.
- Add numbers, digit by digit, modulo m. In other words, we need to get the third number of length n, each digit of the number is the sum of the respective numbers of the found numbers. For example, suppose there are two numbers recorded in the ternary notation, 001210 and 012111, then if you add them to each other digit by digit modulo 3, you will get number 010021.
- The key to the code is the maximum possible number that can be obtained in the previous step.

Help Ilya, find the key to the code.

## Input Format
The first line contains two integers n, m (1 ≤ n, m ≤ 105, m > 1). The second line contains the first found number, the third line contains the second found number.

The numbers are recorded as a sequence of digits in the m-based notation. Each digit is an integer from 0 to m - 1. The digits in the line are written in the order from the most significant digits to the least significant ones.

The given numbers can contain leading zeroes.

## Output Format
Print n m-base digits. The resulting third number written in the m-based notation. Print the digits in the order from the most significant digits to the least significant ones.

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

Now solve the problem and return the code.