vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Connecting Universities

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Treeland is a country in which there are *n* towns connected by *n*<=-<=1 two-way road such that it's possible to get from any town to any other town. 

In Treeland there are 2*k* universities which are located in different towns. 

Recently, the president signed the decree to connect universities by high-speed network.The Ministry of Education understood the decree in its own way and decided that it was enough to connect each university with another one by using a cable. Formally, the decree will be done! 

To have the maximum sum in the budget, the Ministry decided to divide universities into pairs so that the total length of the required cable will be maximum. In other words, the total distance between universities in *k* pairs should be as large as possible. 

Help the Ministry to find the maximum total distance. Of course, each university should be present in only one pair. Consider that all roads have the same length which is equal to 1.

Input Specification:
The first line of the input contains two integers *n* and *k* (2<=≤<=*n*<=≤<=200<=000, 1<=≤<=*k*<=≤<=*n*<=/<=2) — the number of towns in Treeland and the number of university pairs. Consider that towns are numbered from 1 to *n*. 

The second line contains 2*k* distinct integers *u*1,<=*u*2,<=...,<=*u*2*k* (1<=≤<=*u**i*<=≤<=*n*) — indices of towns in which universities are located. 

The next *n*<=-<=1 line contains the description of roads. Each line contains the pair of integers *x**j* and *y**j* (1<=≤<=*x**j*,<=*y**j*<=≤<=*n*), which means that the *j*-th road connects towns *x**j* and *y**j*. All of them are two-way roads. You can move from any town to any other using only these roads.

Output Specification:
Print the maximum possible sum of distances in the division of universities into *k* pairs.

Demo Input:
['7 2\n1 5 6 2\n1 3\n3 2\n4 5\n3 7\n4 3\n4 6\n', '9 3\n3 2 1 6 5 9\n8 9\n3 2\n2 7\n3 4\n7 6\n4 5\n2 1\n2 8\n']

Demo Output:
['6\n', '9\n']

Note:
The figure below shows one of possible division into pairs in the first test. If you connect universities number 1 and 6 (marked in red) and universities number 2 and 5 (marked in blue) by using the cable, the total distance will equal 6 which will be the maximum sum in this example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Match sticks can be used to form digital numbers. The arrangement of matches that forms each digit between ‘0’ and ‘9’ is illustrated in the figure.

You are given two sequences of digits $X$ and $Y$. There are matches that have been arranged to form the digits in $X$. Can you move exactly one match from them, so that the resulting matches form the other sequence $Y$?

-----Input-----
The input contains one line with two sequences of digits $X$ and $Y$. It is guaranteed that $X$ and $Y$ have the same length but are different sequences. Each sequence contains digits between ‘0’ and ‘9’ and has at least one and no more than $12$ digits. A sequence may contain leading zeros.

-----Output-----
Output “yes” if it is possible to move exactly one match to change $X$ into $Y$. Otherwise output “no”.

-----Examples-----
Sample Input 1:
60 58
Sample Output 1:
yes

Sample Input 2:
046 040
Sample Output 2:
yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N trees in a circle. Each tree has a fruit value associated with it. A bird has to sit on a tree for 0.5 sec to gather all the fruits present on the tree and then the bird can move to a neighboring tree. It takes the bird 0.5 seconds to move from one tree to another. Once all the fruits are picked from a particular tree, she cant pick any more fruits from that tree. The maximum number of fruits she can gather is infinite.
Given N and M (the total number of seconds the bird has), and an array arr[] containing the fruit values of the trees. Maximize the total fruit value that the bird can gather. The bird can start from any tree.
 
Example 1:
Input:
N=7 M=3
arr[] = { 2 ,1 ,3 ,5 ,0 ,1 ,4 }
Output: 9
Explanation: 
She can start from tree 1 and move
to tree2 and then to tree 3.
Hence, total number of gathered fruits
= 1 + 3 + 5 = 9.
 
Example 2:
Input:
N=6 M=2
arr[] = { 1, 6, 2, 5, 3, 4 }
Output: 8
Explanation: 
She can start from tree 1 and move 
to tree 2. In this case she will gather
6 + 2 = 8 fruits. She can also start 
from tree 3 and move to tree 4. In this
case, too, she will gather 5 + 3 = 8 
fruits.
 
Your Task:
You don't need to read input, or print anything. You just need to complete the function maxFruits() that takes array arr, integer N and integer M as parameters and returns the maximum number of fruits she can gather.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
2 ≤ N ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string as input, move all of its vowels to the end of the string, in the same order as they were before.

Vowels are (in this kata): `a, e, i, o, u`

Note: all provided input strings are lowercase.

## Examples
```python
"day"    ==>  "dya"
"apple"  ==>  "pplae"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Implement a function, `multiples(m, n)`, which returns an array of the first `m` multiples of the real number `n`. Assume that `m` is a positive integer.

Ex.
```
multiples(3, 5.0)
```
should return
```
[5.0, 10.0, 15.0]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A correct expression of the form a+b=c was written; a, b and c are non-negative integers without leading zeros. In this expression, the plus and equally signs were lost. The task is to restore the expression. In other words, one character '+' and one character '=' should be inserted into given sequence of digits so that:   character'+' is placed on the left of character '=',  characters '+' and '=' split the sequence into three non-empty subsequences consisting of digits (let's call the left part a, the middle part — b and the right part — c),  all the three parts a, b and c do not contain leading zeros,  it is true that a+b=c. 

It is guaranteed that in given tests answer always exists.


-----Input-----

The first line contains a non-empty string consisting of digits. The length of the string does not exceed 10^6.


-----Output-----

Output the restored expression. If there are several solutions, you can print any of them.

Note that the answer at first should contain two terms (divided with symbol '+'), and then the result of their addition, before which symbol'=' should be. 

Do not separate numbers and operation signs with spaces. Strictly follow the output format given in the examples.

If you remove symbol '+' and symbol '=' from answer string you should get a string, same as string from the input data.


-----Examples-----
Input
12345168

Output
123+45=168

Input
099

Output
0+9=9

Input
199100

Output
1+99=100

Input
123123123456456456579579579

Output
123123123+456456456=579579579

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a table consisting of n rows and m columns.

Numbers in each row form a permutation of integers from 1 to m.

You are allowed to pick two elements in one row and swap them, but no more than once for each row. Also, no more than once you are allowed to pick two columns and swap them. Thus, you are allowed to perform from 0 to n + 1 actions in total. Operations can be performed in any order.

You have to check whether it's possible to obtain the identity permutation 1, 2, ..., m in each row. In other words, check if one can perform some of the operation following the given rules and make each row sorted in increasing order.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 20) — the number of rows and the number of columns in the given table. 

Each of next n lines contains m integers — elements of the table. It's guaranteed that numbers in each line form a permutation of integers from 1 to m.


-----Output-----

If there is a way to obtain the identity permutation in each row by following the given rules, print "YES" (without quotes) in the only line of the output. Otherwise, print "NO" (without quotes).


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

Output
YES

Input
4 4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Output
NO

Input
3 6
2 1 3 4 5 6
1 2 4 3 5 6
1 2 3 4 6 5

Output
YES



-----Note-----

In the first sample, one can act in the following way:   Swap second and third columns. Now the table is 1 2 3 4 1 4 3 2  In the second row, swap the second and the fourth elements. Now the table is 1 2 3 4 1 2 3 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Do you remember a kind cartoon "Beauty and the Beast"? No, no, there was no firing from machine guns or radiation mutants time-travels!

There was a beauty named Belle. Once she had violated the Beast's order and visited the West Wing. After that she was banished from the castle... 

Everybody was upset. The beautiful Belle was upset, so was the Beast, so was Lumiere the candlestick. But the worst thing was that Cogsworth was upset. Cogsworth is not a human, but is the mantel clock, which was often used as an alarm clock.

Due to Cogsworth's frustration all the inhabitants of the castle were in trouble: now they could not determine when it was time to drink morning tea, and when it was time for an evening stroll. 

Fortunately, deep in the basement are lying digital clock showing the time in the format HH:MM. Now the residents of the castle face a difficult task. They should turn Cogsworth's hour and minute mustache hands in such a way, that Cogsworth began to show the correct time. Moreover they need to find turn angles in degrees for each mustache hands. The initial time showed by Cogsworth is 12:00.

You can only rotate the hands forward, that is, as is shown in the picture: 

<image>

As since there are many ways too select such angles because of full rotations, choose the smallest angles in the right (non-negative) direction.

Note that Cogsworth's hour and minute mustache hands move evenly and continuously. Hands are moving independently, so when turning one hand the other hand remains standing still.

Input

The only line of input contains current time according to the digital clock, formatted as HH:MM (00 ≤ HH ≤ 23, 00 ≤ MM ≤ 59). The mantel clock initially shows 12:00.

Pretests contain times of the beginning of some morning TV programs of the Channel One Russia.

Output

Print two numbers x and y — the angles of turning the hour and minute hands, respectively (0 ≤ x, y < 360). The absolute or relative error in the answer should not exceed 10 - 9.

Examples

Input

12:00


Output

0 0

Input

04:30


Output

135 180

Input

08:17


Output

248.5 102

Note

A note to the second example: the hour hand will be positioned exactly in the middle, between 4 and 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are planning to buy an apartment in a $n$-floor building. The floors are numbered from $1$ to $n$ from the bottom to the top. At first for each floor you want to know the minimum total time to reach it from the first (the bottom) floor.

Let:  $a_i$ for all $i$ from $1$ to $n-1$ be the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the stairs;  $b_i$ for all $i$ from $1$ to $n-1$ be the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the elevator, also there is a value $c$ — time overhead for elevator usage (you need to wait for it, the elevator doors are too slow!). 

In one move, you can go from the floor you are staying at $x$ to any floor $y$ ($x \ne y$) in two different ways:  If you are using the stairs, just sum up the corresponding values of $a_i$. Formally, it will take $\sum\limits_{i=min(x, y)}^{max(x, y) - 1} a_i$ time units.  If you are using the elevator, just sum up $c$ and the corresponding values of $b_i$. Formally, it will take $c + \sum\limits_{i=min(x, y)}^{max(x, y) - 1} b_i$ time units. 

You can perform as many moves as you want (possibly zero).

So your task is for each $i$ to determine the minimum total time it takes to reach the $i$-th floor from the $1$-st (bottom) floor.


-----Input-----

The first line of the input contains two integers $n$ and $c$ ($2 \le n \le 2 \cdot 10^5, 1 \le c \le 1000$) — the number of floors in the building and the time overhead for the elevator rides.

The second line of the input contains $n - 1$ integers $a_1, a_2, \dots, a_{n-1}$ ($1 \le a_i \le 1000$), where $a_i$ is the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the stairs.

The third line of the input contains $n - 1$ integers $b_1, b_2, \dots, b_{n-1}$ ($1 \le b_i \le 1000$), where $b_i$ is the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the elevator.


-----Output-----

Print $n$ integers $t_1, t_2, \dots, t_n$, where $t_i$ is the minimum total time to reach the $i$-th floor from the first floor if you can perform as many moves as you want.


-----Examples-----
Input
10 2
7 6 18 6 16 18 1 17 17
6 9 3 10 9 1 10 1 5

Output
0 7 13 18 24 35 36 37 40 45 

Input
10 1
3 2 3 1 3 3 1 4 1
1 2 3 4 4 1 2 1 3

Output
0 2 4 7 8 11 13 14 16 17

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day, liouzhou_101 got a chat record of Freda and Rainbow. Out of curiosity, he wanted to know which sentences were said by Freda, and which were said by Rainbow. According to his experience, he thought that Freda always said "lala." at the end of her sentences, while Rainbow always said "miao." at the beginning of his sentences. For each sentence in the chat record, help liouzhou_101 find whose sentence it is. 

Input

The first line of the input contains an integer n (1 ≤ n ≤ 10), number of sentences in the chat record. Each of the next n lines contains a sentence. A sentence is a string that contains only Latin letters (A-Z, a-z), underline (_), comma (,), point (.) and space ( ). Its length doesn’t exceed 100.

Output

For each sentence, output "Freda's" if the sentence was said by Freda, "Rainbow's" if the sentence was said by Rainbow, or "OMG>.< I don't know!" if liouzhou_101 can’t recognize whose sentence it is. He can’t recognize a sentence if it begins with "miao." and ends with "lala.", or satisfies neither of the conditions. 

Examples

Input

5
I will go to play with you lala.
wow, welcome.
miao.lala.
miao.
miao .


Output

Freda's
OMG&gt;.&lt; I don't know!
OMG&gt;.&lt; I don't know!
Rainbow's
OMG&gt;.&lt; I don't know!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a five-card hand drawn from a standard $52$-card deck. The strength of your hand is the maximum value $k$ such that there are $k$ cards in your hand that have the same rank.

Compute the strength of your hand.

-----Input-----
The input will consist of a single line, with five two-character strings separated by spaces.

The first character in each string will be the rank of the card, and will be one of A23456789TJQK. The second character in the string will be the suit of the card, and will be one of CDHS.

You may assume all the strings are distinct.

-----Output-----
Output, on a single line, the strength of your hand.

-----Examples-----
Sample Input 1:
AC AD AH AS KD
Sample Output 1:
4

Sample Input 2:
2C 4D 4H 2D 2H
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Harry the Hamster lives in a giant hamster cage. Inside the cage there is a set of $n$ plastic balls connected by unidirectional hamster tubes of varying lengths. Harry is currently in ball $s$ and his bed is in ball $t$.

Being a simple hamster, the hemispheres of Harry’s brain are not so great at communicating with each other and have a mind of their own. Harry’s left hemisphere, usually being active when Harry is in the hamster wheel, likes running for as long as possible. Harry’s right hemisphere, rarely active at all, would like to go to sleep as soon as possible. Together, Harry’s hemispheres will be navigating Harry through the maze of tubes, in each ball deciding which of the outgoing tubes to follow.

Harry’s hemispheres get really tired after making a decision and then need to rest a bit, so they cannot make two decisions in a row. Thus, they make decisions on which tube to take in alternating turns, with the left hemisphere going first. So starting in ball $s$, Harry’s left hemisphere will decide on a tube to follow, ending in some ball $u$, where Harry’s left hemisphere will rest and Harry’s right hemisphere will pick an outgoing tube, et cetera.

Counterintuitively, the hemispheres are familiar with the entire hamster cage and can plan arbitrarily far ahead. Assuming both hemispheres make optimal decisions, how long will it take for Harry to reach his bed? It is guaranteed that each ball has at least one outgoing tube, except the ball containing Harry’s bed which has none (there Harry will rest easily). There are no tubes connecting a ball to itself, but there may be multiple tubes going from one ball to another.

-----Input-----
 - On the first line are four space-separated integers: the number of plastic balls $1 \leq n \leq 10^5$, the number of tubes $0 \leq m \leq 2 \cdot 10^5$, and the locations of Harry and his bed $0 \leq s, t < n$.
 - Then $m$ lines follow, each containing three space-separated integers describing a single tube: the ball in which the tube starts $0 \leq a_ i < n$, in which it ends $0 \leq b_ i < n$ and the time it takes to traverse $1 \leq w_ i \leq 10^4$. Note that each tube can only be traversed in one direction.

-----Output-----
Print the time it takes for Harry to reach his bed, or the string infinity if Harry is doomed to roam the tubes forever.

-----Examples-----
Sample Input 1:
4 5 0 3
0 1 1
1 2 2
2 0 4
2 3 1
2 3 3
Sample Output 1:
11

Sample Input 2:
5 5 0 4
0 1 1
1 2 1
2 3 1
3 0 1
2 4 1
Sample Output 2:
infinity

Sample Input 3:
2 1 0 1
0 1 2
Sample Output 3:
2

Sample Input 4:
3 3 1 2
0 1 1
1 0 1
1 2 1
Sample Output 4:
infinity

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Surya loves to play with primes. One day, he asked his friend don to print any number in the form of multiple of prime factors. Help don in solving the problem. 

Input
The first line will contain an integer t (1 ≤ t ≤ 10^6) denoting number of test case. 
For each test case, you will be given an integer n (2 ≤ n ≤ 10^6).

Output
Print a string showing prime factors which should look like :
2^e1 * p2^e2 * .........* pk^ek 
where p1, p2, ...., pn are the prime factors and e1, e2, ....., en is the degree of corresponding prime factor.

Note: power of 2 should always be given.
For a prime number , only 2^0 is printed.

SAMPLE INPUT
3
32
100
9085

SAMPLE OUTPUT
2^5
2^2*5^2
2^0*5^1*23^1*79^1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Fox and Perfect Sets

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fox Ciel studies number theory.

She thinks a non-empty set *S* contains non-negative integers is perfect if and only if for any  (*a* can be equal to *b*), . Where operation *xor* means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive_or).

Please calculate the number of perfect sets consisting of integers not greater than *k*. The answer can be very large, so print it modulo 1000000007 (109<=+<=7).

Input Specification:
The first line contains an integer *k* (0<=≤<=*k*<=≤<=109).

Output Specification:
Print a single integer — the number of required sets modulo 1000000007 (109<=+<=7).

Demo Input:
['1\n', '2\n', '3\n', '4\n']

Demo Output:
['2\n', '3\n', '5\n', '6\n']

Note:
In example 1, there are 2 such sets: {0} and {0, 1}. Note that {1} is not a perfect set since 1 xor 1 = 0 and {1} doesn't contain zero.

In example 4, there are 6 such sets: {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4} and {0, 1, 2, 3}.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Arkady plays Gardenscapes a lot. Arkady wants to build two new fountains. There are *n* available fountains, for each fountain its beauty and cost are known. There are two types of money in the game: coins and diamonds, so each fountain cost can be either in coins or diamonds. No money changes between the types are allowed.

Help Arkady to find two fountains with maximum total beauty so that he can buy both at the same time.

Input Specification:
The first line contains three integers *n*, *c* and *d* (2<=≤<=*n*<=≤<=100<=000, 0<=≤<=*c*,<=*d*<=≤<=100<=000) — the number of fountains, the number of coins and diamonds Arkady has.

The next *n* lines describe fountains. Each of these lines contain two integers *b**i* and *p**i* (1<=≤<=*b**i*,<=*p**i*<=≤<=100<=000) — the beauty and the cost of the *i*-th fountain, and then a letter "C" or "D", describing in which type of money is the cost of fountain *i*: in coins or in diamonds, respectively.

Output Specification:
Print the maximum total beauty of exactly two fountains Arkady can build. If he can't build two fountains, print 0.

Demo Input:
['3 7 6\n10 8 C\n4 3 C\n5 6 D\n', '2 4 5\n2 5 C\n2 1 D\n', '3 10 10\n5 5 C\n5 5 C\n10 11 D\n']

Demo Output:
['9\n', '0\n', '10\n']

Note:
In the first example Arkady should build the second fountain with beauty 4, which costs 3 coins. The first fountain he can't build because he don't have enough coins. Also Arkady should build the third fountain with beauty 5 which costs 6 diamonds. Thus the total beauty of built fountains is 9.

In the second example there are two fountains, but Arkady can't build both of them, because he needs 5 coins for the first fountain, and Arkady has only 4 coins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dom and Brian have come across this locker which they can't open. The fate of the mission depends on it. They have to open it at any cost. Tej has found the pattern in the combination. The pattern goes like this, given a number X between 0 to 10^9+6 find smallest positive integer Y such that the products of digits of Y modulo 10^9+7 is X. This Y is the combination of the lock. Help Dom and Brian open this safe.

Input: 
A single integer, X.

Output: 
A single integer, Y.

Input: 
0 ≤ X ≤ 10^9+6

SAMPLE INPUT
16

SAMPLE OUTPUT
28

Explanation

If X is 16 then Y is 28 as (2*8)%1000000007 = 16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an award-winning garden and everyday the plants need exactly 40mm of water. You created a great piece of JavaScript to calculate the amount of water your plants will need when you have taken into consideration the amount of rain water that is forecast for the day. Your jealous neighbour hacked your computer and filled your code with bugs. 

Your task is to debug the code before your plants die!

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