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 python3.

Your soluton must read input from the file 'input.txt' and write output to the file 'output.txt'.
Do not include any debug prints or additional output.

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
One day mum asked Petya to sort his toys and get rid of some of them. Petya found a whole box of toy spiders. They were quite dear to him and the boy didn't want to throw them away. Petya conjured a cunning plan: he will glue all the spiders together and attach them to the ceiling. Besides, Petya knows that the lower the spiders will hang, the more mum is going to like it and then she won't throw his favourite toys away. Help Petya carry out the plan.

A spider consists of k beads tied together by k - 1 threads. Each thread connects two different beads, at that any pair of beads that make up a spider is either directly connected by a thread, or is connected via some chain of threads and beads.

Petya may glue spiders together directly gluing their beads. The length of each thread equals 1. The sizes of the beads can be neglected. That's why we can consider that gluing spiders happens by identifying some of the beads (see the picture). Besides, the construction resulting from the gluing process should also represent a spider, that is, it should have the given features.

After Petya glues all spiders together, he measures the length of the resulting toy. The distance between a pair of beads is identified as the total length of the threads that connect these two beads. The length of the resulting construction is the largest distance between all pairs of beads. Petya wants to make the spider whose length is as much as possible.

The picture two shows two spiders from the second sample. We can glue to the bead number 2 of the first spider the bead number 1 of the second spider. The threads in the spiders that form the sequence of threads of maximum lengths are highlighted on the picture.

## Input Format
The first input file line contains one integer n (1 ≤ n ≤ 100) — the number of spiders. Next n lines contain the descriptions of each spider: integer ni (2 ≤ ni ≤ 100) — the number of beads, then ni - 1 pairs of numbers denoting the numbers of the beads connected by threads. The beads that make up each spider are numbered from 1 to ni.

## Output Format
Print a single number — the length of the required construction.

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

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 python3.

Your soluton must read input from the file 'input.txt' and write output to the file 'output.txt'.
Do not include any debug prints or additional output.

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
As we communicate, we learn much new information. However, the process of communication takes too much time. It becomes clear if we look at the words we use in our everyday speech.

We can list many simple words consisting of many letters: "information", "technologies", "university", "construction", "conservatoire", "refrigerator", "stopwatch", "windowsill", "electricity", "government" and so on. Of course, we can continue listing those words ad infinitum.

Fortunately, the solution for that problem has been found. To make our speech clear and brief, we should replace the initial words with those that resemble them but are much shorter. This idea hasn't been brought into life yet, that's why you are chosen to improve the situation.

Let's consider the following formal model of transforming words: we shall assume that one can use n words in a chat. For each words we shall introduce a notion of its shorter variant. We shall define shorter variant of an arbitrary word s as such word t, that meets the following conditions:

- it occurs in s as a subsequence,
- its length ranges from one to four characters.

In other words, the word t consists at least of one and at most of four characters that occur in the same order in the word s. Note that those characters do not necessarily follow in s immediately one after another. You are allowed not to shorten the initial word if its length does not exceed four characters.

You are given a list of n different words. Your task is to find a set of their shortened variants. The shortened variants of all words from the list should be different.

## Input Format
The first line of the input file contains the only integer n (1 ≤ n ≤ 200). Then n lines contain a set of different non-empty words that consist of lowercase Latin letters. The length of each word does not exceed 10 characters.

## Output Format
If the solution exists, print in the output file exactly n lines, where the i-th line represents the shortened variant of the i-th word from the initial set. If there are several variants to solve the problem, print any of them. If there is no solution, print -1.

## Examples
```input
6
privet
spasibo
codeforces
java
marmelad
normalno
```
```output
pret
sps
cdfs
java
mama
norm
```
-----
```input
5
aaa
aa
a
aaaa
aaaaa
```
```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 python3.

Your soluton must read input from the file 'input.txt' and write output to the file 'output.txt'.
Do not include any debug prints or additional output.

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya has been collecting transport tickets for quite a while now. His collection contains several thousands of tram, trolleybus and bus tickets. Vasya is already fed up with the traditional definition of what a lucky ticket is. Thus, he's looking for new perspectives on that. Besides, Vasya cannot understand why all tickets are only divided into lucky and unlucky ones. He thinks that all tickets are lucky but in different degrees. Having given the matter some thought, Vasya worked out the definition of a ticket's degree of luckiness. Let a ticket consist of 2n digits. Let's regard each digit as written as is shown on the picture:

You have seen such digits on electronic clocks: seven segments are used to show digits. Each segment can either be colored or not. The colored segments form a digit. Vasya regards the digits as written in this very way and takes the right half of the ticket and puts it one the left one, so that the first digit coincides with the n + 1-th one, the second digit coincides with the n + 2-th one, ..., the n-th digit coincides with the 2n-th one. For each pair of digits, put one on another, he counts the number of segments colored in both digits and summarizes the resulting numbers. The resulting value is called the degree of luckiness of a ticket. For example, the degree of luckiness of ticket 03 equals four and the degree of luckiness of ticket 2345 equals six.

You are given the number of a ticket containing 2n digits. Your task is to find among the tickets whose number exceeds the number of this ticket but also consists of 2n digits such ticket, whose degree of luckiness exceeds the degrees of luckiness of the given ticket. Moreover, if there are several such tickets, you should only choose the one with the smallest number.

## Input Format
The first line contains the number of the ticket that consists of k characters (k = 2n, 1 ≤ n ≤ 105).

## Output Format
Print the number of the sought ticket or "-1" (without the quotes) if no such ticket exists.

## Examples
```input
13
```
```output
20
```
-----
```input
2345
```
```output
2348
```
-----
```input
88
```
```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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp is reading a book consisting of $$$n$$$ pages numbered from $$$1$$$ to $$$n$$$. Every time he finishes the page with the number divisible by $$$m$$$, he writes down the last digit of this page number. For example, if $$$n=15$$$ and $$$m=5$$$, pages divisible by $$$m$$$ are $$$5, 10, 15$$$. Their last digits are $$$5, 0, 5$$$ correspondingly, their sum is $$$10$$$.

Your task is to calculate the sum of all digits Polycarp has written down.

You have to answer $$$q$$$ independent queries.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 1000$$$) — the number of queries.

The following $$$q$$$ lines contain queries, one per line. Each query is given as two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^{16}$$$) — the number of pages in the book and required divisor, respectively.

## Output Format
For each query print the answer for it — the sum of digits written down by Polycarp.

## Examples
```input
7
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13
```
```output
1
45
153
294
3359835
0
427262129093995
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between easy and hard versions is the number of elements in the array.

You are given an array $$$a$$$ consisting of $$$n$$$ integers. In one move you can choose any $$$a_i$$$ and divide it by $$$2$$$ rounding down (in other words, in one move you can set $$$a_i := \lfloor\frac{a_i}{2}\rfloor$$$).

You can perform such an operation any (possibly, zero) number of times with any $$$a_i$$$.

Your task is to calculate the minimum possible number of operations required to obtain at least $$$k$$$ equal numbers in the array.

Don't forget that it is possible to have $$$a_i = 0$$$ after some operations, thus the answer always exists.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 50$$$) — the number of elements in the array and the number of equal numbers required.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
Print one integer — the minimum possible number of operations required to obtain at least $$$k$$$ equal numbers in the array.

## Examples
```input
5 3
1 2 2 4 5
```
```output
1
```
-----
```input
5 3
1 2 3 4 5
```
```output
2
```
-----
```input
5 3
1 2 3 3 3
```
```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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between easy and hard versions is the number of elements in the array.

You are given an array $$$a$$$ consisting of $$$n$$$ integers. In one move you can choose any $$$a_i$$$ and divide it by $$$2$$$ rounding down (in other words, in one move you can set $$$a_i := \lfloor\frac{a_i}{2}\rfloor$$$).

You can perform such an operation any (possibly, zero) number of times with any $$$a_i$$$.

Your task is to calculate the minimum possible number of operations required to obtain at least $$$k$$$ equal numbers in the array.

Don't forget that it is possible to have $$$a_i = 0$$$ after some operations, thus the answer always exists.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of elements in the array and the number of equal numbers required.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
Print one integer — the minimum possible number of operations required to obtain at least $$$k$$$ equal numbers in the array.

## Examples
```input
5 3
1 2 2 4 5
```
```output
1
```
-----
```input
5 3
1 2 3 4 5
```
```output
2
```
-----
```input
5 3
1 2 3 3 3
```
```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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two strings $$$s$$$ and $$$t$$$ both of length $$$2$$$ and both consisting only of characters 'a', 'b' and 'c'.

Possible examples of strings $$$s$$$ and $$$t$$$: "ab", "ca", "bb".

You have to find a string $$$res$$$ consisting of $$$3n$$$ characters, $$$n$$$ characters should be 'a', $$$n$$$ characters should be 'b' and $$$n$$$ characters should be 'c' and $$$s$$$ and $$$t$$$ should not occur in $$$res$$$ as substrings.

A substring of a string is a contiguous subsequence of that string. So, the strings "ab", "ac" and "cc" are substrings of the string "abacc", but the strings "bc", "aa" and "cb" are not substrings of the string "abacc".

If there are multiple answers, you can print any of them.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of characters 'a', 'b' and 'c' in the resulting string.

The second line of the input contains one string $$$s$$$ of length $$$2$$$ consisting of characters 'a', 'b' and 'c'.

The third line of the input contains one string $$$t$$$ of length $$$2$$$ consisting of characters 'a', 'b' and 'c'.

## Output Format
If it is impossible to find the suitable string, print "NO" on the first line.

Otherwise print "YES" on the first line and string $$$res$$$ on the second line. $$$res$$$ should consist of $$$3n$$$ characters, $$$n$$$ characters should be 'a', $$$n$$$ characters should be 'b' and $$$n$$$ characters should be 'c' and $$$s$$$ and $$$t$$$ should not occur in $$$res$$$ as substrings.

If there are multiple answers, you can print any of them.

## Examples
```input
2
ab
bc
```
```output
YES
acbbac
```
-----
```input
3
aa
bc
```
```output
YES
cacbacbab
```
-----
```input
1
cb
ac
```
```output
YES
abc
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You play your favourite game yet another time. You chose the character you didn't play before. It has $$$str$$$ points of strength and $$$int$$$ points of intelligence. Also, at start, the character has $$$exp$$$ free experience points you can invest either in strength or in intelligence (by investing one point you can either raise strength by $$$1$$$ or raise intelligence by $$$1$$$).

Since you'd like to make some fun you want to create a jock character, so it has more strength than intelligence points (resulting strength is strictly greater than the resulting intelligence).

Calculate the number of different character builds you can create (for the purpose of replayability) if you must invest all free points. Two character builds are different if their strength and/or intellect are different.

## Input Format
The first line contains the single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of queries. Next $$$T$$$ lines contain descriptions of queries — one per line.

This line contains three integers $$$str$$$, $$$int$$$ and $$$exp$$$ ($$$1 \le str, int \le 10^8$$$, $$$0 \le exp \le 10^8$$$) — the initial strength and intelligence of the character and the number of free points, respectively.

## Output Format
Print $$$T$$$ integers — one per query. For each query print the number of different character builds you can create.

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

## Note
In the first query there are only three appropriate character builds: $$$(str = 7, int = 5)$$$, $$$(8, 4)$$$ and $$$(9, 3)$$$. All other builds are either too smart or don't use all free points.

In the second query there is only one possible build: $$$(2, 1)$$$.

In the third query there are two appropriate builds: $$$(7, 6)$$$, $$$(8, 5)$$$.

In the fourth query all builds have too much brains.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are fighting with Zmei Gorynich — a ferocious monster from Slavic myths, a huge dragon-like reptile with multiple heads!

Initially Zmei Gorynich has $$$x$$$ heads. You can deal $$$n$$$ types of blows. If you deal a blow of the $$$i$$$-th type, you decrease the number of Gorynich's heads by $$$min(d_i, curX)$$$, there $$$curX$$$ is the current number of heads. But if after this blow Zmei Gorynich has at least one head, he grows $$$h_i$$$ new heads. If $$$curX = 0$$$ then Gorynich is defeated.

You can deal each blow any number of times, in any order.

For example, if $$$curX = 10$$$, $$$d = 7$$$, $$$h = 10$$$ then the number of heads changes to $$$13$$$ (you cut $$$7$$$ heads off, but then Zmei grows $$$10$$$ new ones), but if $$$curX = 10$$$, $$$d = 11$$$, $$$h = 100$$$ then number of heads changes to $$$0$$$ and Zmei Gorynich is considered defeated.

Calculate the minimum number of blows to defeat Zmei Gorynich!

You have to answer $$$t$$$ independent queries.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) – the number of queries.

The first line of each query contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 100$$$, $$$1 \le x \le 10^9$$$) — the number of possible types of blows and the number of heads Zmei initially has, respectively.

The following $$$n$$$ lines of each query contain the descriptions of types of blows you can deal. The $$$i$$$-th line contains two integers $$$d_i$$$ and $$$h_i$$$ ($$$1 \le d_i, h_i \le 10^9$$$) — the description of the $$$i$$$-th blow.

## Output Format
For each query print the minimum number of blows you have to deal to defeat Zmei Gorynich.

If Zmei Gorynuch cannot be defeated print $$$-1$$$.

## Examples
```input
3
3 10
6 3
8 2
1 4
4 10
4 1
3 2
2 6
1 100
2 15
10 11
14 100
```
```output
2
3
-1
```

## Note
In the first query you can deal the first blow (after that the number of heads changes to $$$10 - 6 + 3 = 7$$$), and then deal the second blow.

In the second query you just deal the first blow three times, and Zmei is defeated.

In third query you can not defeat Zmei Gorynich. Maybe it's better to convince it to stop fighting?

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 python3.

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:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a binary string $$$s$$$ (recall that a string is binary if each character is either $$$0$$$ or $$$1$$$).

Let $$$f(t)$$$ be the decimal representation of integer $$$t$$$ written in binary form (possibly with leading zeroes). For example $$$f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0$$$ and $$$f(000100) = 4$$$.

The substring $$$s_{l}, s_{l+1}, \dots , s_{r}$$$ is good if $$$r - l + 1 = f(s_l \dots s_r)$$$.

For example string $$$s = 1011$$$ has $$$5$$$ good substrings: $$$s_1 \dots s_1 = 1$$$, $$$s_3 \dots s_3 = 1$$$, $$$s_4 \dots s_4 = 1$$$, $$$s_1 \dots s_2 = 10$$$ and $$$s_2 \dots s_4 = 011$$$.

Your task is to calculate the number of good substrings of string $$$s$$$.

You have to answer $$$t$$$ independent queries.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of queries.

The only line of each query contains string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), consisting of only digits $$$0$$$ and $$$1$$$.

It is guaranteed that $$$\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$$$.

## Output Format
For each query print one integer — the number of good substrings of string $$$s$$$.

## Examples
```input
4
0110
0101
00001000
0001000
```
```output
4
3
4
3
```

Now solve the problem and return the code.