vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Kuro is living in a country called Uberland, consisting of $n$ towns, numbered from $1$ to $n$, and $n - 1$ bidirectional roads connecting these towns. It is possible to reach each town from any other. Each road connects two towns $a$ and $b$. Kuro loves walking and he is planning to take a walking marathon, in which he will choose a pair of towns $(u, v)$ ($u \neq v$) and walk from $u$ using the shortest path to $v$ (note that $(u, v)$ is considered to be different from $(v, u)$).

Oddly, there are 2 special towns in Uberland named Flowrisa (denoted with the index $x$) and Beetopia (denoted with the index $y$). Flowrisa is a town where there are many strong-scent flowers, and Beetopia is another town where many bees live. In particular, Kuro will avoid any pair of towns $(u, v)$ if on the path from $u$ to $v$, he reaches Beetopia after he reached Flowrisa, since the bees will be attracted with the flower smell on Kuro’s body and sting him.

Kuro wants to know how many pair of city $(u, v)$ he can take as his route. Since he’s not really bright, he asked you to help him with this problem.


-----Input-----

The first line contains three integers $n$, $x$ and $y$ ($1 \leq n \leq 3 \cdot 10^5$, $1 \leq x, y \leq n$, $x \ne y$) - the number of towns, index of the town Flowrisa and index of the town Beetopia, respectively.

$n - 1$ lines follow, each line contains two integers $a$ and $b$ ($1 \leq a, b \leq n$, $a \ne b$), describes a road connecting two towns $a$ and $b$.

It is guaranteed that from each town, we can reach every other town in the city using the given roads. That is, the given map of towns and roads is a tree.


-----Output-----

A single integer resembles the number of pair of towns $(u, v)$ that Kuro can use as his walking route.


-----Examples-----
Input
3 1 3
1 2
2 3

Output
5
Input
3 1 3
1 2
1 3

Output
4


-----Note-----

On the first example, Kuro can choose these pairs:   $(1, 2)$: his route would be $1 \rightarrow 2$,  $(2, 3)$: his route would be $2 \rightarrow 3$,  $(3, 2)$: his route would be $3 \rightarrow 2$,  $(2, 1)$: his route would be $2 \rightarrow 1$,  $(3, 1)$: his route would be $3 \rightarrow 2 \rightarrow 1$. 

Kuro can't choose pair $(1, 3)$ since his walking route would be $1 \rightarrow 2 \rightarrow 3$, in which Kuro visits town $1$ (Flowrisa) and then visits town $3$ (Beetopia), which is not allowed (note that pair $(3, 1)$ is still allowed because although Kuro visited Flowrisa and Beetopia, he did not visit them in that order).

On the second example, Kuro can choose the following pairs:   $(1, 2)$: his route would be $1 \rightarrow 2$,  $(2, 1)$: his route would be $2 \rightarrow 1$,  $(3, 2)$: his route would be $3 \rightarrow 1 \rightarrow 2$,  $(3, 1)$: his route would be $3 \rightarrow 1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Spotting patterns in seemingly random strings is a problem with many applications. E.g., in our efforts to understand the genome we investigate the structure of DNA strings. In data compression we are interested in finding repetitions, so the data can be represented more efficiently with pointers. Another plausible example arises from the area of artificial intelligence, as how to interpret information given to you in a language you do not know. The natural thing to do in order to decode the information message would be to look for repetitions in it. So if the SETI project (the Search for Extra Terrestrial Intelligence) ever get a signal in the H21-spectra, we need to know how to decompose it.

One way of capturing the redundancy of a string is to find its factoring. If two or more identical substrings $A$ follow each other in a string $S$, we can represent this aprt of $S$ as the substring $A$, enclosed by parentheses, raised to the power of the number of repetitions. E.g., the string $DOODOO$ can be factored as $(DOO)^2$, but also as $(D(O)^2)^2$. Naturally, the latter factoring is considered better since it cannot be factored any further. We say that a factoring is irreducible if it does not contain any consecutive repetition of a substring. A string may have several irreducible factorings, as seen by the example string $POPPOP$. It can be factored as $(POP)^2$, as well as $PO(P)^2OP$. The first factoring has a shorter representation and motivates the following definition. The weigh of a factoring equals the number of characters in it, excluding the parentheses and the exponents. Thus the weight of $(POP)^2$ is $3$, whereas $PO(P)^2OP$ has weight $5$. A maximal facotring is a factoring with the smallest possible weight. It should be clear that a maximal factoring is always an irreducible one, but there may still be several maximal factorings. E.g., the string $ABABA$ has two maximal factorings $(AB)^2A$ and $A(BA)^2$.

-----Input-----
The input consists of a single line, containing a string of at least one, but at most $200$ characters from the capital alphabet A-Z.

-----Output-----
Output the weight of a maximal factoring of the input string.

-----Examples-----
Sample Input 1:
PRATTATTATTIC
Sample Output 1:
6

Sample Input 2:
GGGGGGGGG
Sample Output 2:
1

Sample Input 3:
PRIME
Sample Output 3:
5

Sample Input 4:
BABBABABBABBA
Sample Output 4:
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to develop physical strength and judgment by running on a straight road. The rabbit is now standing at the starting line and looking out over a long, long road.

There are some carrots along the way, and rabbits can accelerate by eating carrots. Rabbits run at U meters per second when not accelerating, but by eating carrots, the speed is V meters per second from the last carrot eaten to T seconds later. Rabbits can also carry up to K carrots without eating them. Even if you have a carrot, the running speed does not change.

Assuming that it does not take long to bring and eat carrots, I would like to find the shortest time required to reach the goal.



Input


N K T U V L
D1
...
DN


N is the number of carrots, L is the distance from the start to the goal (meters), and Di (1 ≤ i ≤ N) is the distance from the start where the i-th carrot is located (meters).

1 ≤ N ≤ 200, 1 ≤ K ≤ N, 1 ≤ T ≤ 10,000, 1 ≤ U <V ≤ 10,000, 2 ≤ L ≤ 10,000, 0 <D1 <D2 <... <DN <L. All input values ​​are integers.

Output

Output the shortest required time (seconds) on one line. Absolute errors of 10-6 or less are allowed.

Examples

Input

1 1 1 2 3 100
50


Output

49.500000000


Input

3 1 1 2 3 100
49
50
51


Output

48.666666667

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Water Tree

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mad scientist Mike has constructed a rooted tree, which consists of *n* vertices. Each vertex is a reservoir which can be either empty or filled with water.

The vertices of the tree are numbered from 1 to *n* with the root at vertex 1. For each vertex, the reservoirs of its children are located below the reservoir of this vertex, and the vertex is connected with each of the children by a pipe through which water can flow downwards.

Mike wants to do the following operations with the tree: 
 1.  Fill vertex *v* with water. Then *v* and all its children are filled with water. 1.  Empty vertex *v*. Then *v* and all its ancestors are emptied. 1.  Determine whether vertex *v* is filled with water at the moment. 
Mike has already compiled a full list of operations that he wants to perform in order. Before experimenting with the tree Mike decided to run the list through a simulation. Help Mike determine what results will he get after performing all the operations.

Input Specification:
The first line of the input contains an integer *n* (1<=≤<=*n*<=≤<=500000) — the number of vertices in the tree. Each of the following *n*<=-<=1 lines contains two space-separated numbers *a**i*, *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*, *a**i*<=≠<=*b**i*) — the edges of the tree.

The next line contains a number *q* (1<=≤<=*q*<=≤<=500000) — the number of operations to perform. Each of the following *q* lines contains two space-separated numbers *c**i* (1<=≤<=*c**i*<=≤<=3), *v**i* (1<=≤<=*v**i*<=≤<=*n*), where *c**i* is the operation type (according to the numbering given in the statement), and *v**i* is the vertex on which the operation is performed.

It is guaranteed that the given graph is a tree.

Output Specification:
For each type 3 operation print 1 on a separate line if the vertex is full, and 0 if the vertex is empty. Print the answers to queries in the order in which the queries are given in the input.

Demo Input:
['5\n1 2\n5 1\n2 3\n4 2\n12\n1 1\n2 3\n3 1\n3 2\n3 3\n3 4\n1 2\n2 4\n3 1\n3 3\n3 4\n3 5\n']

Demo Output:
['0\n0\n0\n1\n0\n1\n0\n1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N represented in the form of a string, remove consecutive repeated digits from it.
Example 1:
Input:
N = 1224
Output: 124
Explanation: Two consecutive occurrences of 
2 have been reduced to one.
Ã¢â¬â¹Example 2:
Input: 
N = 1242
Output: 1242
Explanation: No digit is repeating 
consecutively in N.
Your Task:
You don't need to read input or print anything. Your task is to complete the function modify() which takes the integer N as input and returns the modified integer by removing all the consecutive duplicate occurrences in N.
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(1).
Constraints:
1<=N<=10^{18}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Ivan and Powers of Two

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ivan has got an array of *n* non-negative integers *a*1,<=*a*2,<=...,<=*a**n*. Ivan knows that the array is sorted in the non-decreasing order. 

Ivan wrote out integers 2*a*1,<=2*a*2,<=...,<=2*a**n* on a piece of paper. Now he wonders, what minimum number of integers of form 2*b* (*b*<=≥<=0) need to be added to the piece of paper so that the sum of all integers written on the paper equalled 2*v*<=-<=1 for some integer *v* (*v*<=≥<=0). 

Help Ivan, find the required quantity of numbers.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105). The second input line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=2·109). It is guaranteed that *a*1<=≤<=*a*2<=≤<=...<=≤<=*a**n*.

Output Specification:
Print a single integer — the answer to the problem.

Demo Input:
['4\n0 1 1 1\n', '1\n3\n']

Demo Output:
['0\n', '3\n']

Note:
In the first sample you do not need to add anything, the sum of numbers already equals 2<sup class="upper-index">3</sup> - 1 = 7.

In the second sample you need to add numbers 2<sup class="upper-index">0</sup>, 2<sup class="upper-index">1</sup>, 2<sup class="upper-index">2</sup>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Levko loves permutations very much. A permutation of length n is a sequence of distinct positive integers, each is at most n.

Let’s assume that value gcd(a, b) shows the greatest common divisor of numbers a and b. Levko assumes that element pi of permutation p1, p2, ... , pn is good if gcd(i, pi) > 1. Levko considers a permutation beautiful, if it has exactly k good elements. Unfortunately, he doesn’t know any beautiful permutation. Your task is to help him to find at least one of them.

Input

The single line contains two integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ n).

Output

In a single line print either any beautiful permutation or -1, if such permutation doesn’t exist.

If there are multiple suitable permutations, you are allowed to print any of them.

Examples

Input

4 2


Output

2 4 3 1

Input

1 1


Output

-1

Note

In the first sample elements 4 and 3 are good because gcd(2, 4) = 2 > 1 and gcd(3, 3) = 3 > 1. Elements 2 and 1 are not good because gcd(1, 2) = 1 and gcd(4, 1) = 1. As there are exactly 2 good elements, the permutation is beautiful.

The second sample has no beautiful permutations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Serial Time!

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The Cereal Guy's friend Serial Guy likes to watch soap operas. An episode is about to start, and he hasn't washed his plate yet. But he decided to at least put in under the tap to be filled with water. The plate can be represented by a parallelepiped *k*<=×<=*n*<=×<=*m*, that is, it has *k* layers (the first layer is the upper one), each of which is a rectangle *n*<=×<=*m* with empty squares ('.') and obstacles ('#'). The water can only be present in the empty squares. The tap is positioned above the square (*x*,<=*y*) of the first layer, it is guaranteed that this square is empty. Every minute a cubical unit of water falls into the plate. Find out in how many minutes the Serial Guy should unglue himself from the soap opera and turn the water off for it not to overfill the plate. That is, you should find the moment of time when the plate is absolutely full and is going to be overfilled in the next moment.

Note: the water fills all the area within reach (see sample 4). Water flows in each of the 6 directions, through faces of 1<=×<=1<=×<=1 cubes.

Input Specification:
The first line contains three numbers *k*, *n*, *m* (1<=≤<=*k*,<=*n*,<=*m*<=≤<=10) which are the sizes of the plate. Then follow *k* rectangles consisting of *n* lines each containing *m* characters '.' or '#', which represents the "layers" of the plate in the order from the top to the bottom. The rectangles are separated by empty lines (see the samples). The last line contains *x* and *y* (1<=≤<=*x*<=≤<=*n*,<=1<=≤<=*y*<=≤<=*m*) which are the tap's coordinates. *x* is the number of the line and *y* is the number of the column. Lines of each layer are numbered from left to right by the integers from 1 to *n*, columns of each layer are numbered from top to bottom by the integers from 1 to *m*.

Output Specification:
The answer should contain a single number, showing in how many minutes the plate will be filled.

Demo Input:
['1 1 1\n\n.\n\n1 1\n', '2 1 1\n\n.\n\n#\n\n1 1\n', '2 2 2\n\n.#\n##\n\n..\n..\n\n1 1\n', '3 2 2\n\n#.\n##\n\n#.\n.#\n\n..\n..\n\n1 2\n', '3 3 3\n\n.#.\n###\n##.\n\n.##\n###\n##.\n\n...\n...\n...\n\n1 1\n']

Demo Output:
['1\n', '1\n', '5\n', '7\n', '13\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Hahn, our very own DJ, was seeing Chester and Mike fighting over such questions lately. Being a geek himself, he thought of showing off his skills and gave the both of them a question. 

He gave them a single positive integer, N. For all the numbers under 10^N(inclusive) they had to add the square of the digits of the number. They had to do this again for the new number obtained. This process was to be repeated until a cycle was formed. Now Mike figured out that a cycle could only be formed when they reached either 89 or 1 and also that a cycle is always formed. They had to find the number of numbers under 10^N which form a cycle at 89 and also number of those numbers that formed a cycle at 1.

Input:
A single positive integer, N.

Output:
A single line containing two space-separated positive integers. The first being the number of numbers which form a cycle at 89 and the second denoting  the number of numbers which form a cycle at 1.

Constraints:
1 ≤ N ≤ 10

Problem Setter: Chintan Shah

SAMPLE INPUT
1

SAMPLE OUTPUT
7 3

Explanation

As N = 1 they have to count for all numbers under 10^1 = 10

1 -> 1
 2 -> 4 -> 16 -> 37 -> 58 -> 89
 3 -> 9 -> 81 -> 65 -> 61 -> 37 -> 58 -> 89
 4 -> 16 -> 37 -> 58 -> 89
and so on...

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The entire network is under the inspection and direct control of the Decepticons. They have learned our language through the World Wide Web and can easily understand the messages which are being sent. Sam is trying to send the information to Autobots to locate “ALL SPARK” which is the only source of energy that can be used to create universe. He is bit cautious in sending the message. He is sending the messages in a form of special pattern of string that contains important message in form of substrings. But Decepticons have learnt to recognize the Data Mining and string comparison patterns. He is sending a big message in form of a string (say M) and let there are N smaller substrings. Decepticons have to find whether each of these N substrings is a sub-string of M. All strings consist of only alphanumeric characters.

-----Input-----
Input to the program consists of two line. The first line contains the string M (where size of M should be <=40). The next line contain a string S.

-----Output-----
Output should consist of a line with a character 'Y'/'N' indicating whether the string S is a sub-string of String M or not.

-----Example-----
Input:
techtrishna online event
onlin
Output:
Y

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a string of decimal digits s. Let's define b_{ij} = s_{i}·s_{j}. Find in matrix b the number of such rectangles that the sum b_{ij} for all cells (i, j) that are the elements of the rectangle equals a in each rectangle.

A rectangle in a matrix is a group of four integers (x, y, z, t) (x ≤ y, z ≤ t). The elements of the rectangle are all cells (i, j) such that x ≤ i ≤ y, z ≤ j ≤ t.


-----Input-----

The first line contains integer a (0 ≤ a ≤ 10^9), the second line contains a string of decimal integers s (1 ≤ |s| ≤ 4000).


-----Output-----

Print a single integer — the answer to a problem.

Please, do not write 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
12345

Output
6

Input
16
439873893693495623498263984765

Output
40

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Special Offer! Super Price 999 Bourles!

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus is an amateur businessman. Recently he was surprised to find out that the market for paper scissors is completely free! Without further ado, Polycarpus decided to start producing and selling such scissors.

Polycaprus calculated that the optimal celling price for such scissors would be *p* bourles. However, he read somewhere that customers are attracted by prices that say something like "Special Offer! Super price 999 bourles!". So Polycarpus decided to lower the price a little if it leads to the desired effect.

Polycarpus agrees to lower the price by no more than *d* bourles so that the number of nines at the end of the resulting price is maximum. If there are several ways to do it, he chooses the maximum possible price.

Note, Polycarpus counts only the trailing nines in a price.

Input Specification:
The first line contains two integers *p* and *d* (1<=≤<=*p*<=≤<=1018; 0<=≤<=*d*<=&lt;<=*p*) — the initial price of scissors and the maximum possible price reduction.

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

Output Specification:
Print the required price — the maximum price that ends with the largest number of nines and that is less than *p* by no more than *d*.

The required number shouldn't have leading zeroes.

Demo Input:
['1029 102\n', '27191 17\n']

Demo Output:
['999\n', '27189\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sam has opened a new sushi train restaurant - a restaurant where sushi is served on plates that travel around the bar on a conveyor belt and customers take the plate that they like.

Sam is using Glamazon's new visual recognition technology that allows a computer to record the number of plates at a customer's table and the colour of those plates.  The number of plates is returned as a string.  For example, if a customer has eaten 3 plates of sushi on a red plate the computer will return the string 'rrr'.

Currently, Sam is only serving sushi on red plates as he's trying to attract customers to his restaurant.  There are also small plates on the conveyor belt for condiments such as ginger and wasabi - the computer notes these in the string that is returned as a space ('rrr r' //denotes 4 plates of red sushi and a plate of condiment).

Sam would like your help to write a program for the cashier's machine to read the string and return the total amount a customer has to pay when they ask for the bill.  The current price for the dishes are as follows:  

 * Red plates of sushi ('r') - $2 each, but if a customer eats 5 plates the 5th one is free.
 * Condiments (' ') - free.

```
Input: String
Output: Number

Examples:

Input: 'rr'  Output: 4
Input: 'rr rrr' Output: 8
Input: 'rrrrr rrrrr' Output: 16

```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has a non-negative integer n. He wants to round it to nearest integer, which ends up with 0. If n already ends up with 0, Vasya considers it already rounded.

For example, if n = 4722 answer is 4720. If n = 5 Vasya can round it to 0 or to 10. Both ways are correct.

For given n find out to which integer will Vasya round it.


-----Input-----

The first line contains single integer n (0 ≤ n ≤ 10^9) — number that Vasya has.


-----Output-----

Print result of rounding n. Pay attention that in some cases answer isn't unique. In that case print any correct answer.


-----Examples-----
Input
5

Output
0

Input
113

Output
110

Input
1000000000

Output
1000000000

Input
5432359

Output
5432360



-----Note-----

In the first example n = 5. Nearest integers, that ends up with zero are 0 and 10. Any of these answers is correct, so you can print 0 or 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Joty has got a task to do. She has a line of n tiles indexed from 1 to n. She has to paint them in a strange pattern.

An unpainted tile should be painted Red if it's index is divisible by a and an unpainted tile should be painted Blue if it's index is divisible by b. So the tile with the number divisible by a and b can be either painted Red or Blue.

After her painting is done, she will get p chocolates for each tile that is painted Red and q chocolates for each tile that is painted Blue.

Note that she can paint tiles in any order she wants.

Given the required information, find the maximum number of chocolates Joty can get.


-----Input-----

The only line contains five integers n, a, b, p and q (1 ≤ n, a, b, p, q ≤ 10^9).


-----Output-----

Print the only integer s — the maximum number of chocolates Joty can get.

Note that the answer can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Examples-----
Input
5 2 3 12 15

Output
39

Input
20 2 3 3 5

Output
51

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.