apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of size $$$n$$$.

There is an $$$n \times n$$$ grid. In the $$$i$$$-th row, the first $$$a_i$$$ cells are black and the other cells are white. In other words, note $$$(i,j)$$$ as the cell in the $$$i$$$-th row and $$$j$$$-th column, cells $$$(i,1), (i,2), \ldots, (i,a_i)$$$ are black, and cells $$$(i,a_i+1), \ldots, (i,n)$$$ are white.

You can do the following operations any number of times in any order:

- Dye a $$$2 \times 2$$$ subgrid white;
- Dye a whole row white. Note you can not dye a whole column white.

Find the minimum number of operations to dye all cells white.

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

For each test case:

- The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the size of the array $$$a$$$.
- The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$).

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

## Output Format
For each test case, output a single integer — the minimum number of operations to dye all cells white.

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

## Note
In the first test case, you don't need to do any operation.

In the second test case, you can do:

- Dye $$$(1,1), (1,2), (2,1)$$$, and $$$(2,2)$$$ white;
- Dye $$$(2,3), (2,4), (3,3)$$$, and $$$(3,4)$$$ white;
- Dye $$$(3,1), (3,2), (4,1)$$$, and $$$(4,2)$$$ white.

It can be proven $$$3$$$ is the minimum number of operations.

In the third test case, you can do:

- Dye the first row white;
- Dye $$$(2,1), (2,2), (3,1)$$$, and $$$(3,2)$$$ white.

It can be proven $$$2$$$ is the minimum number of operations.

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: 8.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a$$$ of size $$$n$$$.

A segment $$$[l, r](1 \le l < r \le n)$$$ is called a polygonal segment only if the following conditions hold:

- $$$(r-l+1) \geq 3$$$;
- Considering $$$a_l, a_{l+1}, \ldots, a_r$$$ as side lengths, these sides can form a polygon with $$$(r-l+1)$$$ sides.

Process $$$q$$$ queries of two types:

- "1 l r": find the length of the longest segment among all polygonal segments $$$[l_0,r_0]$$$ satisfying $$$l \le l_0 \le r_0 \le r$$$. If there is no such polygonal segment, output $$$-1$$$ instead;
- "2 i x": assign $$$a_i := x$$$.

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

For each test case:

- The first line of each testcase contains two integers $$$n$$$, $$$q$$$ ($$$4 \le n \le 2\cdot 10^5$$$, $$$1 \le q \le 10^5$$$);
- The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$);
- The following $$$q$$$ lines contain the description of queries. Each line is of one of two types:  "1 l r" ($$$1 \le l < r \le n$$$, $$$r-l+1\ge 3$$$);  "2 i x" ($$$1 \le i \le n$$$, $$$1 \le x \le 10^{12}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$, and the sum of $$$q$$$ over all test cases will not exceed $$$10^5$$$.

## Output Format
For each query, if there is no suitable segment, output $$$-1$$$ in a new line. Otherwise, output the length of the longest segment satisfying the condition above in a new line.

## Examples
```input
2
5 6
3 1 2 2 8
1 1 3
1 1 4
1 1 5
2 1 5
1 1 4
1 1 5
4 10
500000000000 500000000000 1000000000000 500000000000
1 1 3
1 2 4
1 1 4
2 1 499999999999
2 3 999999999999
1 1 3
1 2 4
1 1 4
2 3 1000000000000
1 1 3
```
```output
-1
4
4
3
5
-1
-1
4
-1
3
4
-1
```

## Note
In the first query of the first test case, there is no polygonal segment under the given condition. For example, considering segment $$$[1,3]$$$, you can not form a triangle with side lengths of $$$a_1=3$$$, $$$a_2=1$$$, and $$$a_3=2$$$.

In the second query of the first test case, the longest polygonal segment is $$$[1,4]$$$. You can form a quadrilateral with side lengths of $$$a_1=3$$$, $$$a_2=1$$$, $$$a_3=2$$$, and $$$a_4=2$$$.

An example of a quadrilateral with side lengths of $$$3$$$, $$$1$$$, $$$2$$$, and $$$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
Several ages ago Berland was a kingdom. The King of Berland adored math. That's why, when he first visited one of his many palaces, he first of all paid attention to the floor in one hall. The floor was tiled with hexagonal tiles.

The hall also turned out hexagonal in its shape. The King walked along the perimeter of the hall and concluded that each of the six sides has a, b, c, a, b and c adjacent tiles, correspondingly.

To better visualize the situation, look at the picture showing a similar hexagon for a = 2, b = 3 and c = 4.

According to the legend, as the King of Berland obtained the values a, b and c, he almost immediately calculated the total number of tiles on the hall floor. Can you do the same?

## Input Format
The first line contains three integers: a, b and c (2 ≤ a, b, c ≤ 1000).

## Output Format
Print a single number — the total number of tiles on the hall floor.

## Examples
```input
2 3 4
```
```output
18
```

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
One day n students come to the stadium. They want to play football, and for that they need to split into teams, the teams must have an equal number of people.

We know that this group of people has archenemies. Each student has at most two archenemies. Besides, if student A is an archenemy to student B, then student B is an archenemy to student A.

The students want to split so as no two archenemies were in one team. If splitting in the required manner is impossible, some students will have to sit on the bench.

Determine the minimum number of students you will have to send to the bench in order to form the two teams in the described manner and begin the game at last.

## Input Format
The first line contains two integers n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of students and the number of pairs of archenemies correspondingly.

Next m lines describe enmity between students. Each enmity is described as two numbers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the indexes of the students who are enemies to each other. Each enmity occurs in the list exactly once. It is guaranteed that each student has no more than two archenemies.

You can consider the students indexed in some manner with distinct integers from 1 to n.

## Output Format
Print a single integer — the minimum number of students you will have to send to the bench in order to start the game.

## Examples
```input
5 4
1 2
2 4
5 3
1 4
```
```output
1
```
-----
```input
6 2
1 4
3 4
```
```output
0
```
-----
```input
6 6
1 2
2 3
3 1
4 5
5 6
6 4
```
```output
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
A new Berland businessman Vitaly is going to open a household appliances' store. All he's got to do now is to hire the staff.

The store will work seven days a week, but not around the clock. Every day at least k people must work in the store.

Berland has a law that determines the order of working days and non-working days. Namely, each employee must work for exactly n consecutive days, then rest for exactly m days, then work for n more days and rest for m more, and so on. Vitaly doesn't want to break the law. Fortunately, there is a loophole: the law comes into force on the day when the employee is hired. For example, if an employee is hired on day x, then he should work on days [x, x + 1, ..., x + n - 1], [x + m + n, x + m + n + 1, ..., x + m + 2n - 1], and so on. Day x can be chosen arbitrarily by Vitaly.

There is one more thing: the key to the store. Berland law prohibits making copies of keys, so there is only one key. Vitaly is planning to entrust the key to the store employees. At the same time on each day the key must be with an employee who works that day — otherwise on this day no one can get inside the store. During the day the key holder can give the key to another employee, if he also works that day. The key will handed to the first hired employee at his first working day.

Each employee has to be paid salary. Therefore, Vitaly wants to hire as few employees as possible provided that the store can operate normally on each day from 1 to infinity. In other words, on each day with index from 1 to infinity, the store must have at least k working employees, and one of the working employees should have the key to the store.

Help Vitaly and determine the minimum required number of employees, as well as days on which they should be hired.

## Input Format
The first line contains three integers n, m and k (1 ≤ m ≤ n ≤ 1000, n ≠ 1, 1 ≤ k ≤ 1000).

## Output Format
In the first line print a single integer z — the minimum required number of employees.

In the second line print z positive integers, separated by spaces: the i-th integer ai (1 ≤ ai ≤ 104) should represent the number of the day, on which Vitaly should hire the i-th employee.

If there are multiple answers, print any of them.

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

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
You know that the Martians use a number system with base k. Digit b (0 ≤ b < k) is considered lucky, as the first contact between the Martians and the Earthlings occurred in year b (by Martian chronology).

A digital root d(x) of number x is a number that consists of a single digit, resulting after cascading summing of all digits of number x. Word "cascading" means that if the first summing gives us a number that consists of several digits, then we sum up all digits again, and again, until we get a one digit number.

For example, d(35047) = d((3 + 5 + 0 + 4)7) = d(157) = d((1 + 5)7) = d(67) = 67. In this sample the calculations are performed in the 7-base notation.

If a number's digital root equals b, the Martians also call this number lucky.

You have string s, which consists of n digits in the k-base notation system. Your task is to find, how many distinct substrings of the given string are lucky numbers. Leading zeroes are permitted in the numbers.

Note that substring s[i... j] of the string s = a1a2... an (1 ≤ i ≤ j ≤ n) is the string aiai + 1... aj. Two substrings s[i1... j1] and s[i2... j2] of the string s are different if either i1 ≠ i2 or j1 ≠ j2.

## Input Format
The first line contains three integers k, b and n (2 ≤ k ≤ 109, 0 ≤ b < k, 1 ≤ n ≤ 105).

The second line contains string s as a sequence of n integers, representing digits in the k-base notation: the i-th integer equals ai (0 ≤ ai < k) — the i-th digit of string s. The numbers in the lines are space-separated.

## Output Format
Print a single integer — the number of substrings that are lucky numbers.

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 5 6
3 2 0 5 6 1
```
```output
5
```
-----
```input
7 6 4
3 5 0 4
```
```output
1
```
-----
```input
257 0 3
0 0 256
```
```output
3
```

## Note
In the first sample the following substrings have the sought digital root: s[1... 2] = "3 2", s[1... 3] = "3 2 0", s[3... 4] = "0 5", s[4... 4] = "5" and s[2... 6] = "2 0 5 6 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 is an active Internet user. One day he came across an Internet resource he liked, so he wrote its address in the notebook. We know that the address of the written resource has format:

<protocol>://<domain>.ru[/<context>]

where:

- <protocol> can equal either "http" (without the quotes) or "ftp" (without the quotes),
- <domain> is a non-empty string, consisting of lowercase English letters,
- the /<context> part may not be present. If it is present, then <context> is a non-empty string, consisting of lowercase English letters.

If string <context> isn't present in the address, then the additional character "/" isn't written. Thus, the address has either two characters "/" (the ones that go before the domain), or three (an extra one in front of the context).

When the boy came home, he found out that the address he wrote in his notebook had no punctuation marks. Vasya must have been in a lot of hurry and didn't write characters ":", "/", ".".

Help Vasya to restore the possible address of the recorded Internet resource.

## Input Format
The first line contains a non-empty string that Vasya wrote out in his notebook. This line consists of lowercase English letters only.

It is guaranteed that the given string contains at most 50 letters. It is guaranteed that the given string can be obtained from some correct Internet resource address, described above.

## Output Format
Print a single line — the address of the Internet resource that Vasya liked. If there are several addresses that meet the problem limitations, you are allowed to print any of them.

## Examples
```input
httpsunrux
```
```output
http://sun.ru/x
```
-----
```input
ftphttprururu
```
```output
ftp://http.ru/ruru
```

## Note
In the second sample there are two more possible answers: "ftp://httpruru.ru" and "ftp://httpru.ru/ru".

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
Two pirates Polycarpus and Vasily play a very interesting game. They have n chests with coins, the chests are numbered with integers from 1 to n. Chest number i has ai coins.

Polycarpus and Vasily move in turns. Polycarpus moves first. During a move a player is allowed to choose a positive integer x (2·x + 1 ≤ n) and take a coin from each chest with numbers x, 2·x, 2·x + 1. It may turn out that some chest has no coins, in this case the player doesn't take a coin from this chest. The game finishes when all chests get emptied.

Polycarpus isn't a greedy scrooge. Polycarpys is a lazy slob. So he wonders in what minimum number of moves the game can finish. Help Polycarpus, determine the minimum number of moves in which the game can finish. Note that Polycarpus counts not only his moves, he also counts Vasily's moves.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 100) — the number of chests with coins. The second line contains a sequence of space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai is the number of coins in the chest number i at the beginning of the game.

## Output Format
Print a single integer — the minimum number of moves needed to finish the game. If no sequence of turns leads to finishing the game, print -1.

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

## Note
In the first test case there isn't a single move that can be made. That's why the players won't be able to empty the chests.

In the second sample there is only one possible move x = 1. This move should be repeated at least 3 times to empty the third chest.

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
Polycarpus just has been out of luck lately! As soon as he found a job in the "Binary Cat" cafe, the club got burgled. All ice-cream was stolen.

On the burglary night Polycarpus kept a careful record of all club visitors. Each time a visitor entered the club, Polycarpus put down character "+" in his notes. Similarly, each time a visitor left the club, Polycarpus put character "-" in his notes. We know that all cases of going in and out happened consecutively, that is, no two events happened at the same time. Polycarpus doesn't remember whether there was somebody in the club at the moment when his shift begun and at the moment when it ended.

Right now the police wonders what minimum number of distinct people Polycarpus could have seen. Assume that he sees anybody coming in or out of the club. Each person could have come in or out an arbitrary number of times.

## Input Format
The only line of the input contains a sequence of characters "+" and "-", the characters are written one after another without any separators. The characters are written in the order, in which the corresponding events occurred. The given sequence has length from 1 to 300 characters, inclusive.

## Output Format
Print the sought minimum number of people

## Examples
```input
+-+-+
```
```output
1
```
-----
```input
---
```
```output
3
```

Now solve the problem and return the code.