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 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
Mike decided to teach programming to children in an elementary school. He knows that it is not an easy task to interest children in that age to code. That is why he decided to give each child two sweets.

Mike has $$$n$$$ sweets with sizes $$$a_1, a_2, \ldots, a_n$$$. All his sweets have different sizes. That is, there is no such pair $$$(i, j)$$$ ($$$1 \leq i, j \leq n$$$) such that $$$i \ne j$$$ and $$$a_i = a_j$$$.

Since Mike has taught for many years, he knows that if he gives two sweets with sizes $$$a_i$$$ and $$$a_j$$$ to one child and $$$a_k$$$ and $$$a_p$$$ to another, where $$$(a_i + a_j) \neq (a_k + a_p)$$$, then a child who has a smaller sum of sizes will be upset. That is, if there are two children who have different sums of sweets, then one of them will be upset. Apparently, Mike does not want somebody to be upset.

Mike wants to invite children giving each of them two sweets. Obviously, he can't give one sweet to two or more children. His goal is to invite as many children as he can.

Since Mike is busy preparing to his first lecture in the elementary school, he is asking you to find the maximum number of children he can invite giving each of them two sweets in such way that nobody will be upset.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \leq n \leq 1\,000$$$) — the number of sweets Mike has.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — the sizes of the sweets. It is guaranteed that all integers are distinct.

## Output Format
Print one integer — the maximum number of children Mike can invite giving each of them two sweets in such way that nobody will be upset.

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

## Note
In the first example, Mike can give $$$9+2=11$$$ to one child, $$$8+3=11$$$ to another one, and $$$7+4=11$$$ to the third child. Therefore, Mike can invite three children. Note that it is not the only solution.

In the second example, Mike can give $$$3+9=12$$$ to one child and $$$1+11$$$ to another one. Therefore, Mike can invite two children. Note that it is not the only solution.

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

# Problem
You are given a string $$$s=s_1s_2\dots s_n$$$ of length $$$n$$$, which only contains digits $$$1$$$, $$$2$$$, ..., $$$9$$$.

A substring $$$s[l \dots r]$$$ of $$$s$$$ is a string $$$s_l s_{l + 1} s_{l + 2} \ldots s_r$$$. A substring $$$s[l \dots r]$$$ of $$$s$$$ is called even if the number represented by it is even.

Find the number of even substrings of $$$s$$$. Note, that even if some substrings are equal as strings, but have different $$$l$$$ and $$$r$$$, they are counted as different substrings.

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

The second line contains a string $$$s$$$ of length $$$n$$$. The string $$$s$$$ consists only of digits $$$1$$$, $$$2$$$, ..., $$$9$$$.

## Output Format
Print the number of even substrings of $$$s$$$.

## Examples
```input
4
1234
```
```output
6
```
-----
```input
4
2244
```
```output
10
```

## Note
In the first example, the $$$[l, r]$$$ pairs corresponding to even substrings are:

- $$$s[1 \dots 2]$$$
- $$$s[2 \dots 2]$$$
- $$$s[1 \dots 4]$$$
- $$$s[2 \dots 4]$$$
- $$$s[3 \dots 4]$$$
- $$$s[4 \dots 4]$$$

In the second example, all $$$10$$$ substrings of $$$s$$$ are even substrings. Note, that while substrings $$$s[1 \dots 1]$$$ and $$$s[2 \dots 2]$$$ both define the substring "2", they are still counted as different substrings.

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 went to the store, selling $$$n$$$ types of chocolates. There are $$$a_i$$$ chocolates of type $$$i$$$ in stock.

You have unlimited amount of cash (so you are not restricted by any prices) and want to buy as many chocolates as possible. However if you buy $$$x_i$$$ chocolates of type $$$i$$$ (clearly, $$$0 \le x_i \le a_i$$$), then for all $$$1 \le j < i$$$ at least one of the following must hold:

- $$$x_j = 0$$$ (you bought zero chocolates of type $$$j$$$)
- $$$x_j < x_i$$$ (you bought less chocolates of type $$$j$$$ than of type $$$i$$$)

For example, the array $$$x = [0, 0, 1, 2, 10]$$$ satisfies the requirement above (assuming that all $$$a_i \ge x_i$$$), while arrays $$$x = [0, 1, 0]$$$, $$$x = [5, 5]$$$ and $$$x = [3, 2]$$$ don't.

Calculate the maximum number of chocolates you can buy.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), denoting the number of types of chocolate.

The next line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$), denoting the number of chocolates of each type.

## Output Format
Print the maximum number of chocolates you can buy.

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

## Note
In the first example, it is optimal to buy: $$$0 + 0 + 1 + 3 + 6$$$ chocolates.

In the second example, it is optimal to buy: $$$1 + 2 + 3 + 4 + 10$$$ chocolates.

In the third example, it is optimal to buy: $$$0 + 0 + 0 + 1$$$ chocolates.

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 a tree (a connected undirected graph without cycles) of $$$n$$$ vertices. Each of the $$$n - 1$$$ edges of the tree is colored in either black or red.

You are also given an integer $$$k$$$. Consider sequences of $$$k$$$ vertices. Let's call a sequence $$$[a_1, a_2, \ldots, a_k]$$$ good if it satisfies the following criterion:

- We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from $$$a_1$$$ and ending at $$$a_k$$$.
- Start at $$$a_1$$$, then go to $$$a_2$$$ using the shortest path between $$$a_1$$$ and $$$a_2$$$, then go to $$$a_3$$$ in a similar way, and so on, until you travel the shortest path between $$$a_{k-1}$$$ and $$$a_k$$$.
- If you walked over at least one black edge during this process, then the sequence is good.

Consider the tree on the picture. If $$$k=3$$$ then the following sequences are good: $$$[1, 4, 7]$$$, $$$[5, 5, 3]$$$ and $$$[2, 3, 7]$$$. The following sequences are not good: $$$[1, 4, 6]$$$, $$$[5, 5, 5]$$$, $$$[3, 7, 3]$$$.

There are $$$n^k$$$ sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo $$$10^9+7$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$2 \le k \le 100$$$), the size of the tree and the length of the vertex sequence.

Each of the next $$$n - 1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$ and $$$x_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$x_i \in \{0, 1\}$$$), where $$$u_i$$$ and $$$v_i$$$ denote the endpoints of the corresponding edge and $$$x_i$$$ is the color of this edge ($$$0$$$ denotes red edge and $$$1$$$ denotes black edge).

## Output Format
Print the number of good sequences modulo $$$10^9 + 7$$$.

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

## Note
In the first example, all sequences ($$$4^4$$$) of length $$$4$$$ except the following are good:

- $$$[1, 1, 1, 1]$$$
- $$$[2, 2, 2, 2]$$$
- $$$[3, 3, 3, 3]$$$
- $$$[4, 4, 4, 4]$$$

In the second example, all edges are red, hence there aren't any good sequences.

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
Vivek initially has an empty array $$$a$$$ and some integer constant $$$m$$$.

He performs the following algorithm:

1. Select a random integer $$$x$$$ uniformly in range from $$$1$$$ to $$$m$$$ and append it to the end of $$$a$$$.
2. Compute the greatest common divisor of integers in $$$a$$$.
3. In case it equals to $$$1$$$, break
4. Otherwise, return to step $$$1$$$.

Find the expected length of $$$a$$$. It can be shown that it can be represented as $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q\neq 0 \pmod{10^9+7}$$$. Print the value of $$$P \cdot Q^{-1} \pmod{10^9+7}$$$.

## Input Format
The first and only line contains a single integer $$$m$$$ ($$$1 \leq m \leq 100000$$$).

## Output Format
Print a single integer — the expected length of the array $$$a$$$ written as $$$P \cdot Q^{-1} \pmod{10^9+7}$$$.

## Examples
```input
1
```
```output
1
```
-----
```input
2
```
```output
2
```
-----
```input
4
```
```output
333333338
```

## Note
In the first example, since Vivek can choose only integers from $$$1$$$ to $$$1$$$, he will have $$$a=[1]$$$ after the first append operation, and after that quit the algorithm. Hence the length of $$$a$$$ is always $$$1$$$, so its expected value is $$$1$$$ as well.

In the second example, Vivek each time will append either $$$1$$$ or $$$2$$$, so after finishing the algorithm he will end up having some number of $$$2$$$'s (possibly zero), and a single $$$1$$$ in the end. The expected length of the list is $$$1\cdot \frac{1}{2} + 2\cdot \frac{1}{2^2} + 3\cdot \frac{1}{2^3} + \ldots = 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 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
There are $$$m$$$ people living in a city. There are $$$n$$$ dishes sold in the city. Each dish $$$i$$$ has a price $$$p_i$$$, a standard $$$s_i$$$ and a beauty $$$b_i$$$. Each person $$$j$$$ has an income of $$$inc_j$$$ and a preferred beauty $$$pref_j$$$.

A person would never buy a dish whose standard is less than the person's income. Also, a person can't afford a dish with a price greater than the income of the person. In other words, a person $$$j$$$ can buy a dish $$$i$$$ only if $$$p_i \leq inc_j \leq s_i$$$.

Also, a person $$$j$$$ can buy a dish $$$i$$$, only if $$$|b_i-pref_j| \leq (inc_j-p_i)$$$. In other words, if the price of the dish is less than the person's income by $$$k$$$, the person will only allow the absolute difference of at most $$$k$$$ between the beauty of the dish and his/her preferred beauty.

Print the number of dishes that can be bought by each person in the city.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$), the number of dishes available in the city and the number of people living in the city.

The second line contains $$$n$$$ integers $$$p_i$$$ ($$$1 \leq p_i \leq 10^9$$$), the price of each dish.

The third line contains $$$n$$$ integers $$$s_i$$$ ($$$1 \leq s_i \leq 10^9$$$), the standard of each dish.

The fourth line contains $$$n$$$ integers $$$b_i$$$ ($$$1 \leq b_i \leq 10^9$$$), the beauty of each dish.

The fifth line contains $$$m$$$ integers $$$inc_j$$$ ($$$1 \leq inc_j \leq 10^9$$$), the income of every person.

The sixth line contains $$$m$$$ integers $$$pref_j$$$ ($$$1 \leq pref_j \leq 10^9$$$), the preferred beauty of every person.

It is guaranteed that for all integers $$$i$$$ from $$$1$$$ to $$$n$$$, the following condition holds: $$$p_i \leq s_i$$$.

## Output Format
Print $$$m$$$ integers, the number of dishes that can be bought by every person living in the city.

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

## Note
In the first example, the first person can buy dish $$$2$$$, the second person can buy dishes $$$1$$$ and $$$2$$$ and the third person can buy no dishes.

In the second example, the first person can buy no dishes, the second person can buy dishes $$$1$$$ and $$$4$$$, and the third person can buy dishes $$$1$$$, $$$2$$$ and $$$4$$$.

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
Kurt reaches nirvana when he finds the product of all the digits of some positive integer. Greater value of the product makes the nirvana deeper.

Help Kurt find the maximum possible product of digits among all integers from $$$1$$$ to $$$n$$$.

## Input Format
The only input line contains the integer $$$n$$$ ($$$1 \le n \le 2\cdot10^9$$$).

## Output Format
Print the maximum product of digits among all integers from $$$1$$$ to $$$n$$$.

## Examples
```input
390
```
```output
216
```
-----
```input
7
```
```output
7
```
-----
```input
1000000000
```
```output
387420489
```

## Note
In the first example the maximum product is achieved for $$$389$$$ (the product of digits is $$$3\cdot8\cdot9=216$$$).

In the second example the maximum product is achieved for $$$7$$$ (the product of digits is $$$7$$$).

In the third example the maximum product is achieved for $$$999999999$$$ (the product of digits is $$$9^9=387420489$$$).

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
Let's write all the positive integer numbers one after another from $$$1$$$ without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536...

Your task is to print the $$$k$$$-th digit of this sequence.

## Input Format
The first and only line contains integer $$$k$$$ ($$$1 \le k \le 10000$$$) — the position to process ($$$1$$$-based index).

## Output Format
Print the $$$k$$$-th digit of the resulting infinite sequence.

## Examples
```input
7
```
```output
7
```
-----
```input
21
```
```output
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 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
Let's write all the positive integer numbers one after another from $$$1$$$ without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536...

Your task is to print the $$$k$$$-th digit of this sequence.

## Input Format
The first and only line contains integer $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — the position to process ($$$1$$$-based index).

## Output Format
Print the $$$k$$$-th digit of the resulting infinite sequence.

## Examples
```input
7
```
```output
7
```
-----
```input
21
```
```output
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 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 knows that if the sum of the digits of a number is divisible by $$$3$$$, then the number itself is divisible by $$$3$$$. He assumes that the numbers, the sum of the digits of which is divisible by $$$4$$$, are also somewhat interesting. Thus, he considers a positive integer $$$n$$$ interesting if its sum of digits is divisible by $$$4$$$.

Help Polycarp find the nearest larger or equal interesting number for the given number $$$a$$$. That is, find the interesting number $$$n$$$ such that $$$n \ge a$$$ and $$$n$$$ is minimal.

## Input Format
The only line in the input contains an integer $$$a$$$ ($$$1 \le a \le 1000$$$).

## Output Format
Print the nearest greater or equal interesting number for the given number $$$a$$$. In other words, print the interesting number $$$n$$$ such that $$$n \ge a$$$ and $$$n$$$ is minimal.

## Examples
```input
432
```
```output
435
```
-----
```input
99
```
```output
103
```
-----
```input
237
```
```output
237
```
-----
```input
42
```
```output
44
```

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

# Problem
This problem is actually a subproblem of problem G from the same contest.

There are $$$n$$$ candies in a candy box. The type of the $$$i$$$-th candy is $$$a_i$$$ ($$$1 \le a_i \le n$$$).

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type $$$1$$$ and two candies of type $$$2$$$ is bad).

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

Your task is to find out the maximum possible size of the single gift you can prepare using the candies you have.

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

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries. Each query is represented by two lines.

The first line of each query contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of candies.

The second line of each query contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the type of the $$$i$$$-th candy in the box.

It is guaranteed that the sum of $$$n$$$ over all queries does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each query print one integer — the maximum possible size of the single gift you can compose using candies you got in this query with the restriction described in the problem statement.

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

## Note
In the first query, you can prepare a gift with two candies of type $$$8$$$ and one candy of type $$$5$$$, totalling to $$$3$$$ candies.

Note that this is not the only possible solution — taking two candies of type $$$4$$$ and one candy of type $$$6$$$ is also valid.

Now solve the problem and return the code.