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
Sereja and his friends went to a picnic. The guys had n soda bottles just for it. Sereja forgot the bottle opener as usual, so the guys had to come up with another way to open bottles.

Sereja knows that the i-th bottle is from brand ai, besides, you can use it to open other bottles of brand bi. You can use one bottle to open multiple other bottles. Sereja can open bottle with opened bottle or closed bottle.

Knowing this, Sereja wants to find out the number of bottles they've got that they won't be able to open in any way. Help him and find this number.

## Input Format
The first line contains integer n (1 ≤ n ≤ 100) — the number of bottles. The next n lines contain the bottles' description. The i-th line contains two integers ai, bi (1 ≤ ai, bi ≤ 1000) — the description of the i-th bottle.

## Output Format
In a single line print a single integer — the answer to the problem.

## Examples
```input
4
1 1
2 2
3 3
4 4
```
```output
4
```
-----
```input
4
1 2
2 3
3 4
4 1
```
```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: 6.0 seconds
Memory limit: 256.0 MB

# Problem
A substring of a string is a contiguous subsequence of that string. So, string bca is substring of string abcabc, but string cc is not.

A repeating block is a string formed by concatenating some string with itself. So, string abcabc is a repeating block, but strings abcabd, ababab are not.

You've got a sequence of Latin characters (string). At each step you find the shortest substring that is a repeating block, if there exists more than one you must choose the leftmost. As the substring is of form XX (X — some string) you replace this substring with X, in other words you delete one of the X substrings in the substring. You repeat this process until there remains no repeating block in the string.

How would the final string looks like? Look at the sample explanation to understand the statement more precise.

## Input Format
In the first line of input you're given a string of small Latin characters with length between 1 to 50000, inclusive.

## Output Format
Print the final string after applying changes.

## Examples
```input
abccabc
```
```output
abc
```
-----
```input
aaaabaaab
```
```output
ab
```
-----
```input
birdbirdbirdistheword
```
```output
birdistheword
```

## Note
At the first sample the string transforms as follows: abccabc  →  abcabc  →  abc.

At the second sample the string transforms as follows: aaaabaaab  →  aaabaaab  →  aabaaab  →  abaaab  →  abaab  →  abab  →  ab.

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
Petya is preparing for IQ test and he has noticed that there many problems like: you are given a sequence, find the next number. Now Petya can solve only problems with arithmetic or geometric progressions.

Arithmetic progression is a sequence a1, a1 + d, a1 + 2d, ..., a1 + (n - 1)d, where a1 and d are any numbers.

Geometric progression is a sequence b1, b2 = b1q, ..., bn = bn - 1q, where b1 ≠ 0, q ≠ 0, q ≠ 1.

Help Petya and write a program to determine if the given sequence is arithmetic or geometric. Also it should found the next number. If the sequence is neither arithmetic nor geometric, print 42 (he thinks it is impossible to find better answer). You should also print 42 if the next element of progression is not integer. So answer is always integer.

## Input Format
The first line contains exactly four integer numbers between 1 and 1000, inclusively.

## Output Format
Print the required number. If the given sequence is arithmetic progression, print the next progression element. Similarly, if the given sequence is geometric progression, print the next progression element.

Print 42 if the given sequence is not an arithmetic or geometric progression.

## Examples
```input
836 624 412 200
```
```output
-12
```
-----
```input
1 334 667 1000
```
```output
1333
```

## Note
This problem contains very weak pretests!

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
Do you remember how Kai constructed the word "eternity" using pieces of ice as components?

Little Sheldon plays with pieces of ice, each piece has exactly one digit between 0 and 9. He wants to construct his favourite number t. He realized that digits 6 and 9 are very similar, so he can rotate piece of ice with 6 to use as 9 (and vice versa). Similary, 2 and 5 work the same. There is no other pair of digits with similar effect. He called this effect "Digital Mimicry".

Sheldon favourite number is t. He wants to have as many instances of t as possible. How many instances he can construct using the given sequence of ice pieces. He can use any piece at most once.

## Input Format
The first line contains integer t (1 ≤ t ≤ 10000). The second line contains the sequence of digits on the pieces. The length of line is equal to the number of pieces and between 1 and 200, inclusive. It contains digits between 0 and 9.

## Output Format
Print the required number of instances.

## Examples
```input
42
23454
```
```output
2
```
-----
```input
169
12118999
```
```output
1
```

## Note
This problem contains very weak pretests.

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
Jeff's got n cards, each card contains either digit 0, or digit 5. Jeff can choose several cards and put them in a line so that he gets some number. What is the largest possible number divisible by 90 Jeff can make from the cards he's got?

Jeff must make the number without leading zero. At that, we assume that number 0 doesn't contain any leading zeroes. Jeff doesn't have to use all the cards.

## Input Format
The first line contains integer n (1 ≤ n ≤ 103). The next line contains n integers a1, a2, ..., an (ai = 0 or ai = 5). Number ai represents the digit that is written on the i-th card.

## Output Format
In a single line print the answer to the problem — the maximum number, divisible by 90. If you can't make any divisible by 90 number from the cards, print -1.

## Examples
```input
4
5 0 5 0
```
```output
0
```
-----
```input
11
5 5 5 5 5 5 5 5 0 5 5
```
```output
5555555550
```

## Note
In the first test you can make only one number that is a multiple of 90 — 0.

In the second test you can make number 5555555550, it is a multiple of 90.

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
One day Jeff got hold of an integer sequence a1, a2, ..., an of length n. The boy immediately decided to analyze the sequence. For that, he needs to find all values of x, for which these conditions hold:

- x occurs in sequence a.
- Consider all positions of numbers x in the sequence a (such i, that ai = x). These numbers, sorted in the increasing order, must form an arithmetic progression.

Help Jeff, find all x that meet the problem conditions.

## Input Format
The first line contains integer n (1 ≤ n ≤ 105). The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 105). The numbers are separated by spaces.

## Output Format
In the first line print integer t — the number of valid x. On each of the next t lines print two integers x and px, where x is current suitable value, px is the common difference between numbers in the progression (if x occurs exactly once in the sequence, px must equal 0). Print the pairs in the order of increasing x.

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

## Note
In the first test 2 occurs exactly once in the sequence, ergo p2 = 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
You know that Japan is the country with almost the largest 'electronic devices per person' ratio. So you might be quite surprised to find out that the primary school in Japan teaches to count using a Soroban — an abacus developed in Japan. This phenomenon has its reasons, of course, but we are not going to speak about them. Let's have a look at the Soroban's construction.

Soroban consists of some number of rods, each rod contains five beads. We will assume that the rods are horizontal lines. One bead on each rod (the leftmost one) is divided from the others by a bar (the reckoning bar). This single bead is called go-dama and four others are ichi-damas. Each rod is responsible for representing a single digit from 0 to 9. We can obtain the value of a digit by following simple algorithm:

- Set the value of a digit equal to 0.
- If the go-dama is shifted to the right, add 5.
- Add the number of ichi-damas shifted to the left.

Thus, the upper rod on the picture shows digit 0, the middle one shows digit 2 and the lower one shows 7. We will consider the top rod to represent the last decimal digit of a number, so the picture shows number 720.

Write the program that prints the way Soroban shows the given number n.

## Input Format
The first line contains a single integer n (0 ≤ n < 109).

## Output Format
Print the description of the decimal digits of number n from the last one to the first one (as mentioned on the picture in the statement), one per line. Print the beads as large English letters 'O', rod pieces as character '-' and the reckoning bar as '|'. Print as many rods, as many digits are in the decimal representation of number n without leading zeroes. We can assume that number 0 has no leading zeroes.

## Examples
```input
2
```
```output
O-|OO-OO
```
-----
```input
13
```
```output
O-|OOO-O
O-|O-OOO
```
-----
```input
720
```
```output
O-|-OOOO
O-|OO-OO
-O|OO-OO
```

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
Many modern text editors automatically check the spelling of the user's text. Some editors even suggest how to correct typos.

In this problem your task to implement a small functionality to correct two types of typos in a word. We will assume that three identical letters together is a typo (for example, word "helllo" contains a typo). Besides, a couple of identical letters immediately followed by another couple of identical letters is a typo too (for example, words "helloo" and "wwaatt" contain typos).

Write a code that deletes the minimum number of letters from a word, correcting described typos in the word. You are allowed to delete letters from both ends and from the middle of the word.

## Input Format
The single line of the input contains word s, its length is from 1 to 200000 characters. The given word s consists of lowercase English letters.

## Output Format
Print such word t that it doesn't contain any typos described in the problem statement and is obtained from s by deleting the least number of letters.

If there are multiple solutions, print any of them.

## Examples
```input
helloo
```
```output
hello
```
-----
```input
woooooow
```
```output
woow
```

## Note
The second valid answer to the test from the statement is "heloo".

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
A group of n schoolboys decided to ride bikes. As nobody of them has a bike, the boys need to rent them.

The renting site offered them m bikes. The renting price is different for different bikes, renting the j-th bike costs pj rubles.

In total, the boys' shared budget is a rubles. Besides, each of them has his own personal money, the i-th boy has bi personal rubles. The shared budget can be spent on any schoolchildren arbitrarily, but each boy's personal money can be spent on renting only this boy's bike.

Each boy can rent at most one bike, one cannot give his bike to somebody else.

What maximum number of schoolboys will be able to ride bikes? What minimum sum of personal money will they have to spend in total to let as many schoolchildren ride bikes as possible?

## Input Format
The first line of the input contains three integers n, m and a (1 ≤ n, m ≤ 105; 0 ≤ a ≤ 109). The second line contains the sequence of integers b1, b2, ..., bn (1 ≤ bi ≤ 104), where bi is the amount of the i-th boy's personal money. The third line contains the sequence of integers p1, p2, ..., pm (1 ≤ pj ≤ 109), where pj is the price for renting the j-th bike.

## Output Format
Print two integers r and s, where r is the maximum number of schoolboys that can rent a bike and s is the minimum total personal money needed to rent r bikes. If the schoolchildren cannot rent any bikes, then r = s = 0.

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

## Note
In the first sample both schoolchildren can rent a bike. For instance, they can split the shared budget in half (5 rubles each). In this case one of them will have to pay 1 ruble from the personal money and the other one will have to pay 2 rubles from the personal money. In total, they spend 3 rubles of their personal money. This way of distribution of money minimizes the amount of spent personal money.

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

# Problem
Let's assume that we are given an n × m table filled by integers. We'll mark a cell in the i-th row and j-th column as (i, j). Thus, (1, 1) is the upper left cell of the table and (n, m) is the lower right cell. We'll assume that a circle of radius r with the center in cell (i0, j0) is a set of such cells (i, j) that $$\sqrt{(i-i_{0})^{2}+(j-j_{0})^{2}} \leq r$$. We'll consider only the circles that do not go beyond the limits of the table, that is, for which r + 1 ≤ i0 ≤ n - r and r + 1 ≤ j0 ≤ m - r.

A circle of radius 3 with the center at (4, 5).

Find two such non-intersecting circles of the given radius r that the sum of numbers in the cells that belong to these circles is maximum. Two circles intersect if there is a cell that belongs to both circles. As there can be more than one way to choose a pair of circles with the maximum sum, we will also be interested in the number of such pairs. Calculate the number of unordered pairs of circles, for instance, a pair of circles of radius 2 with centers at (3, 4) and (7, 7) is the same pair as the pair of circles of radius 2 with centers at (7, 7) and (3, 4).

## Input Format
The first line contains three integers n, m and r (2 ≤ n, m ≤ 500, r ≥ 0). Each of the following n lines contains m integers from 1 to 1000 each — the elements of the table. The rows of the table are listed from top to bottom at the elements in the rows are listed from left to right. It is guaranteed that there is at least one circle of radius r, not going beyond the table limits.

## Output Format
Print two integers — the maximum sum of numbers in the cells that are located into two non-intersecting circles and the number of pairs of non-intersecting circles with the maximum sum. If there isn't a single pair of non-intersecting circles, print 0 0.

## Examples
```input
2 2 0
1 2
2 4
```
```output
6 2
```
-----
```input
5 6 1
4 2 1 3 2 6
2 3 2 4 7 2
5 2 2 1 1 3
1 4 3 3 6 4
5 1 4 2 3 2
```
```output
34 3
```
-----
```input
3 3 1
1 2 3
4 5 6
7 8 9
```
```output
0 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
Pavel is going to make a game of his dream. However, he knows that he can't make it on his own so he founded a development company and hired n workers of staff. Now he wants to pick n workers from the staff who will be directly responsible for developing a game.

Each worker has a certain skill level vi. Besides, each worker doesn't want to work with the one whose skill is very different. In other words, the i-th worker won't work with those whose skill is less than li, and with those whose skill is more than ri.

Pavel understands that the game of his dream isn't too hard to develop, so the worker with any skill will be equally useful. That's why he wants to pick a team of the maximum possible size. Help him pick such team.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 105) — the number of workers Pavel hired.

Each of the following n lines contains three space-separated integers li, vi, ri (1 ≤ li ≤ vi ≤ ri ≤ 3·105) — the minimum skill value of the workers that the i-th worker can work with, the i-th worker's skill and the maximum skill value of the workers that the i-th worker can work with.

## Output Format
In the first line print a single integer m — the number of workers Pavel must pick for developing the game.

In the next line print m space-separated integers — the numbers of the workers in any order.

If there are multiple optimal solutions, print any of them.

## Examples
```input
4
2 8 9
1 4 7
3 6 8
5 8 10
```
```output
3
1 3 4
```
-----
```input
6
3 5 16
1 6 11
4 8 12
7 9 16
2 10 14
8 13 15
```
```output
4
1 2 3 5
```

Now solve the problem and return the code.