vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Berland is very concerned with privacy, so almost all plans and blueprints are secret. However, a spy of the neighboring state managed to steal the Bertown subway scheme.

The Bertown Subway has n stations, numbered from 1 to n, and m bidirectional tunnels connecting them. All Bertown Subway consists of lines. To be more precise, there are two types of lines: circular and radial.

A radial line is a sequence of stations v1, ..., vk (k > 1), where stations vi and vi + 1 (i < k) are connected by a tunnel and no station occurs in the line more than once (vi ≠ vj for i ≠ j).

A loop line is a series of stations, v1, ..., vk (k > 2), where stations vi и vi + 1 are connected by a tunnel. In addition, stations v1 and vk are also connected by a tunnel. No station is occurs in the loop line more than once.

Note that a single station can be passed by any number of lines.

According to Berland standards, there can't be more than one tunnel between two stations and each tunnel belongs to exactly one line. Naturally, each line has at least one tunnel. Between any two stations there is the way along the subway tunnels. In addition, in terms of graph theory, a subway is a vertex cactus: if we consider the subway as a graph in which the stations are the vertexes and the edges are tunnels, then each vertex lies on no more than one simple cycle.

Unfortunately, scheme, stolen by the spy, had only the stations and the tunnels. It was impossible to determine to which line every tunnel corresponds. But to sabotage successfully, the spy needs to know what minimum and maximum number of lines may be in the Bertown subway.

Help him!

Input

The first line contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ 3·105) — the number of stations and the number of tunnels, correspondingly.

Each of the next m lines contain two integers — the numbers of stations connected by the corresponding tunnel. The stations are numbered with integers from 1 to n.

It is guaranteed that the graph that corresponds to the subway has no multiple edges or loops, it is connected and it is a vertex cactus.

Output

Print two numbers — the minimum and maximum number of lines correspondingly.

Examples

Input

3 3
1 2
2 3
3 1


Output

1 3


Input

8 8
1 2
2 3
3 4
4 5
6 4
4 7
7 2
2 8


Output

2 8


Input

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


Output

3 6

Note

The subway scheme with minimum possible number of lines for the second sample is: 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
With one die of 6 sides we will have six different possible results:```  1, 2, 3, 4, 5, 6``` .

With 2 dice of six sides, we will have 36 different possible results:
``` 
(1,1),(1,2),(2,1),(1,3),(3,1),(1,4),(4,1),(1,5),
(5,1), (1,6),(6,1),(2,2),(2,3),(3,2),(2,4),(4,2),
(2,5),(5,2)(2,6),(6,2),(3,3),(3,4),(4,3),(3,5),(5,3),
(3,6),(6,3),(4,4),(4,5),(5,4),(4,6),(6,4),(5,5),
(5,6),(6,5),(6,6)
``` 
So, with 2 dice of 6 sides we get 36 different events.
``` 
([6,6] ---> 36)
``` 
But with 2 different dice we can get for this case, the same number of events.
One die of ```4 sides```  and another of ```9 sides```  will produce the exact amount of events.
``` 
([4,9] ---> 36)
``` 
We say that the dice set ```[4,9]``` is equivalent to ```[6,6]``` because both produce the same number of events.

Also we may have an amount of three dice producing the same amount of events. It will be for:
``` 
[4,3,3] ---> 36
``` 
(One die of 4 sides and two dice of 3 sides each)

Perhaps you may think that the following set is equivalent: ```[6,3,2]``` but unfortunately dice have a **minimum of three sides** (well, really a 
tetrahedron with one empty side)

The task for this kata is to get the amount of equivalent dice sets, having **2 dice at least**,for a given set.

For example, for the previous case: [6,6] we will have 3 equivalent sets that are: ``` [4, 3, 3], [12, 3], [9, 4]``` .

You may assume that dice are available from 3 and above for any value up to an icosahedral die (20 sides).
``` 
[5,6,4] ---> 5 (they are [10, 4, 3], [8, 5, 3], [20, 6], [15, 8], [12, 10])
``` 
For the cases we cannot get any equivalent set the result will be `0`.
For example for the set `[3,3]` we will not have equivalent dice.

Range of inputs for Random Tests:
``` 
3 <= sides <= 15
2 <= dices <= 7
``` 
See examples in the corresponding box.

Enjoy it!!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a list of 32 bit unsigned integers N. Find X, the unsigned integer you get by flipping bits in the binary representation of N. i.e. unset bits must be set, and set bits must be unset. Also find the binary representation of X in reverse order.
Example 1:
Input: N = 1
Output: 4294967294 01111111111111111111111111111111
Explaination: 
1 as unsigned 32-bits is 00000000000000000000000000000001. 
Flipping its bits we get 11111111111111111111111111111110.
Its binary representation is 4294967294.
Its reverse order is 01111111111111111111111111111111.
 
Example 2:
Input: N = 2
Output: 4294967293 10111111111111111111111111111111
Explaination: 
2 as unsigned 32-bits is 00000000000000000000000000000010. 
Flipping its bits we get 11111111111111111111111111111101.
Its binary representation is 4294967293.
Its reverse order is 1011111111111111111111111111111.
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function flipBits() which takes N as input parameter and returns a list of strings containing two values, X and  binary representation of X in reverse order.
 
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(logN)
 
Constraints:
1 ≤ N < 4294967296

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera has got a rectangle table consisting of *n* rows and *m* columns. Valera numbered the table rows starting from one, from top to bottom and the columns – starting from one, from left to right. We will represent cell that is on the intersection of row *x* and column *y* by a pair of integers (*x*,<=*y*).

Valera wants to place exactly *k* tubes on his rectangle table. A tube is such sequence of table cells (*x*1,<=*y*1), (*x*2,<=*y*2), ..., (*x**r*,<=*y**r*), that: 
 -  *r*<=≥<=2; -  for any integer *i* (1<=≤<=*i*<=≤<=*r*<=-<=1) the following equation |*x**i*<=-<=*x**i*<=+<=1|<=+<=|*y**i*<=-<=*y**i*<=+<=1|<==<=1 holds; -  each table cell, which belongs to the tube, must occur exactly once in the sequence. 
Valera thinks that the tubes are arranged in a fancy manner if the following conditions are fulfilled: 
 -  no pair of tubes has common cells; -  each cell of the table belongs to some tube. 
Help Valera to arrange *k* tubes on his rectangle table in a fancy manner.

Input Specification:
The first line contains three space-separated integers *n*,<=*m*,<=*k* (2<=≤<=*n*,<=*m*<=≤<=300; 2<=≤<=2*k*<=≤<=*n*·*m*) — the number of rows, the number of columns and the number of tubes, correspondingly.

Output Specification:
Print *k* lines. In the *i*-th line print the description of the *i*-th tube: first print integer *r**i* (the number of tube cells), then print 2*r**i* integers *x**i*1,<=*y**i*1,<=*x**i*2,<=*y**i*2,<=...,<=*x**ir**i*,<=*y**ir**i* (the sequence of table cells).

If there are multiple solutions, you can print any of them. It is guaranteed that at least one solution exists.

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

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

Note:
Picture for the first sample: 

Picture for the second sample:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Omkar's last class of math, he learned about the least common multiple, or $LCM$. $LCM(a, b)$ is the smallest positive integer $x$ which is divisible by both $a$ and $b$.

Omkar, having a laudably curious mind, immediately thought of a problem involving the $LCM$ operation: given an integer $n$, find positive integers $a$ and $b$ such that $a + b = n$ and $LCM(a, b)$ is the minimum value possible.

Can you help Omkar solve his ludicrously challenging math problem?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10$). Description of the test cases follows.

Each test case consists of a single integer $n$ ($2 \leq n \leq 10^{9}$).


-----Output-----

For each test case, output two positive integers $a$ and $b$, such that $a + b = n$ and $LCM(a, b)$ is the minimum possible.


-----Example-----
Input
3
4
6
9

Output
2 2
3 3
3 6



-----Note-----

For the first test case, the numbers we can choose are $1, 3$ or $2, 2$. $LCM(1, 3) = 3$ and $LCM(2, 2) = 2$, so we output $2 \ 2$.

For the second test case, the numbers we can choose are $1, 5$, $2, 4$, or $3, 3$. $LCM(1, 5) = 5$, $LCM(2, 4) = 4$, and $LCM(3, 3) = 3$, so we output $3 \ 3$.

For the third test case, $LCM(3, 6) = 6$. It can be shown that there are no other pairs of numbers which sum to $9$ that have a lower $LCM$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dr.Dawood is another mathematician who is more geekier than Osama (that's why, ++). Dawood deals with more complex problems than Osama usually deals with. He also recruits people to be his sub-ordinates. He usually gives them "trivial" problems as test for them to solve and earn their position to be his sub-ordinate. 

You went to attend such a test and you were given the following question.

Lets define a function A(N,K) where it signifies the number of ways in which we can draw K objects from a pool of N objects. 

Lets define another function B(x1,x2,x3,x4,...) where it signifies the largest integer which can perfectly divide all the integers x1,x2,x3,...

Using these two functions , Dawood gave you a problem. The problem is stated as follows..

Given an integer N find the value of the equation,
O = B(A(2N,1),A(2N,3),A(2N,5),....,A(2N,(2*N)-1)
Input consists of T in the first line, which is the total number of testcases to be processed. Followed by T lines of inputs. Each testcase consists of value N.

Output the value of the equation O in a new line.

1 ≤ T ≤ 1000

1 ≤ N ≤ 10^12

SAMPLE INPUT
4
3
1
2
5

SAMPLE OUTPUT
2
2
4
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nimions speak a funny form of language.

Whichever word they are trying to say, from which ever language, it doesn’t quite come out the same. There are several rules for converting words, from any language, to nimionese.

For any word:
 - All nimion words start with ‘hard’ consonants (b, c, d, g, k, n, p, t) so you must replace each first letter with the nearest one (choose the option nearest to ‘A’ if there is a tie).
 - “Each” becomes “Dach”.
 - Any hard consonant in subsequent syllables after the first one is remarkably better if it is replaced with the same consonant as the one at the start of the word.
 - “Hip-po” becomes “Gip-go”.
 - No word ends in a hard consonant. You must add an ‘ah’, ‘oh’ or ‘uh’ at the end, whichever is nearest, rounding toward ‘A’ in the case of a tie, to the last hard consonant in the word.
 - “Dog” becomes “Dogah”
 - “Hip” becomes “Gipoh”.

-----Input-----
The only line of input contains a sentence of between $1$ and $50$ words and up to $10^4$ symbols, including single whitespace characters (‘ ’) between words and the dashes (‘-’) between each syllable.

Apart from dashes, the sentence will contain solely lower-and-upper-case Latin letters—and only the first letters of words can be upper-case.

-----Output-----
Write to standard output the same sentence from the input, translated to nimionese. Remove any dashes before printing.

It is guaranteed that the output will fit within $5 \cdot 10^4$ characters.

-----Examples-----
Sample Input 1:
I love ba-na-na
Sample Output 1:
Gah kove bababa

Sample Input 2:
Cat-a-pil-lar
Sample Output 2:
Catacillar

Sample Input 3:
Co-ding is the best
Sample Output 3:
Cociccah gs the bestuh

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
Task:
Write
```
smallest(n)
```
that will find the smallest positive number that is evenly divisible by all of the numbers from 1 to n (n <= 40). 
E.g
```python
smallest(5) == 60 # 1 to 5 can all divide evenly into 60
smallest(10) == 2520
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your security guard friend recently got a new job at a new security company. The company requires him to patrol an area of the city encompassing exactly N city blocks, but they let him choose which blocks. That is, your friend must walk the perimeter of a region whose area is exactly N blocks. Your friend is quite lazy and would like your help to find the shortest possible route that meets the requirements. The city is laid out in a square grid pattern, and is large enough that for the sake of the problem it can be considered infinite.


-----Input-----

Input will consist of a single integer N (1 ≤ N ≤ 10^6), the number of city blocks that must be enclosed by the route.


-----Output-----

Print the minimum perimeter that can be achieved.


-----Examples-----
Input
4

Output
8

Input
11

Output
14

Input
22

Output
20



-----Note-----

Here are some possible shapes for the examples:

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given integer $n$. You have to arrange numbers from $1$ to $2n$, using each of them exactly once, on the circle, so that the following condition would be satisfied:

For every $n$ consecutive numbers on the circle write their sum on the blackboard. Then any two of written on the blackboard $2n$ numbers differ not more than by $1$.

For example, choose $n = 3$. On the left you can see an example of a valid arrangement: $1 + 4 + 5 = 10$, $4 + 5 + 2 = 11$, $5 + 2 + 3 = 10$, $2 + 3 + 6 = 11$, $3 + 6 + 1 = 10$, $6 + 1 + 4 = 11$, any two numbers differ by at most $1$. On the right you can see an invalid arrangement: for example, $5 + 1 + 6 = 12$, and $3 + 2 + 4 = 9$, $9$ and $12$ differ more than by $1$.

 [Image] 


-----Input-----

The first and the only line contain one integer $n$ ($1 \le n \le 10^5$).


-----Output-----

If there is no solution, output "NO" in the first line. 

If there is a solution, output "YES" in the first line. In the second line output $2n$ numbers — numbers from $1$ to $2n$ in the order they will stay in the circle. Each number should appear only once. If there are several solutions, you can output any of them.


-----Examples-----
Input
3

Output
YES
1 4 5 2 3 6 
Input
4

Output
NO


-----Note-----

Example from the statement is shown for the first example. 

It can be proved that there is no solution in the second example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ylva loves bonbons, probably more than anything else on this planet. She loves them so much that she made a large plate of $R \cdot C$ bonbons for her fikaraster1.

Ylva has a large wooden tray which can fit $R$ rows of $C$ bonbons per row, that she will put the bonbons on. Her bonbons have three different fillings: Nutella Buttercream, Red Wine Chocolate Ganache, and Strawberry Whipped Cream. Since Ylva is a master chocolatier, she knows that presentation is $90\% $ of the execution. In particular, it looks very bad if two bonbons of the same color are adjacent to each other within a row or a column on the tray. We call an arrangement of bonbons where this is never the case a good arrangement.

Given the number of bonbons of each flavour, and the size of Ylva’s tray, can you help her find a good arrangement of the bonbons, or determine that no such arrangement exists?

-----Input-----
The first line of input contains the two space-separated integers $2 \le R, C \le 1000$. The next line contains three non-negative space-separated integers $a, b, c$ – the number of bonbons of the three flavours which Ylva has baked. It is guaranteed that $a + b + c = R \cdot C$. Both $R$ and $C$ will be even.

-----Output-----
If no good arrangement can be found, output impossible. Otherwise, output $R$ lines, each containing $C$ characters, representing a good arrangement. Each row should contain only characters A, B, C, depending on which flavour should be placed on a certain position. The number of A bonbons placed must be equal to $A$, and so on.

-----Examples-----
Sample Input:
4 4
10 3 3
Sample Output:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam». 

Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.

Let's look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:

• «b» — 1..1 • «bab» — 1..3 • «a» — 2..2 • «b» — 3..3 • «bb» — 3..4 • «b» — 4..4

Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:

1. 1..1 cross with 1..3 2. 1..3 cross with 2..2 3. 1..3 cross with 3..3 4. 1..3 cross with 3..4 5. 3..3 cross with 3..4 6. 3..4 cross with 4..4

Since it's very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.

Input

The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from a to z).

Output

In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.

Examples

Input

4
babb


Output

6


Input

2
aa


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
First Orchard is a cooperative game for children 2 years and up. In this simple game, the players pick colored fruits from trees in an orchard and place them into a basket. To make the game more interesting, a raven tries to reach the orchard to steal the fruits. If the players are successful in moving all fruits into the basket before the raven can get to the orchard, they’ll win. If the raven gets there first, the players lose!

Your task is to determine the probability with which the players will win!

The game is played as follows. There are $4$ trees in the orchard, each bearing a different type of fruit: red apples, green apples, blue plums, and yellow pears. The raven tries to reach the orchard through a pathway containing one or more steps.

At each turn, the players roll a six-sided die. Four of the faces show a color (red, green, yellow, blue), the fifth face shows a fruit basket, and the sixth face shows a raven. All six faces can appear with equal probability.
 - Red, Green, Yellow, Blue. In these cases, a fruit with the corresponding color is placed into the basket, provided the tree corresponding to this color still has any fruits left to pick. Otherwise, the players move on to the next turn.
 - Fruit Basket. If the players roll the ’basket’ face, they will pick a fruit from the tree that has the largest number of fruits left. If there are multiple such trees with the same number of fruits, any of the trees can be chosen.
 - Raven. If the ’raven’ face appears on the die, then the raven moves one step closer towards the orchard.

The game is over if either the players have picked all fruits, or if the raven reaches the orchard, whichever happens first. If the raven reaches the orchard before the players have placed all fruits into the basket, the players lose.

-----Input-----
The input consists of a single test case with a single line of input. The input contains five integer numbers: $R$, $G$, $B$, $Y$ and $S$. The values of $R, G, B$ and $Y$ are the number of red, green, blue, and yellow fruits initially on each tree, respectively, and $S$ denotes the number of steps on the raven’s pathway. Since the game is intended for young children, there will be at most $4$ fruits of each color: $0 \le R, G, B, Y \le 4$. There will be at least one fruit overall: $0 < R + G + B + Y$. The raven will require at least $1$ and at most $8$ steps: $1 \le S \le 8$. The number of steps is equal to the number of times the raven must appear on the die for the players to lose.

-----Output-----
Output the probability that the players will win as a floating point number. The absolute error of your result should be less than $10^{-5}$.

-----Examples-----
Sample Input 1:
1 1 0 0 3
Sample Output 1:
0.920138888889

Sample Input 2:
4 4 4 4 5
Sample Output 2:
0.631357306601

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Chef joined a new company. In this company, the employees have to work for X hours each day from Monday to Thursday. Also, in this company, Friday is called Chill Day — employees only have to work for Y hours (Y < X) on Friday. Saturdays and Sundays are holidays.

Determine the total number of working hours in one week.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space-separated integers X and Y — the number of working hours on each day from Monday to Thursday and the number of working hours on Friday respectively.

------ Output Format ------ 

For each test case, output the total number of working hours in one week.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$2 ≤ X ≤ 12$
$1 ≤Y < X$

----- Sample Input 1 ------ 
3
10 5
12 2
8 7

----- Sample Output 1 ------ 
45
50
39

----- explanation 1 ------ 
Test case $1$: The total number of working hours in a week are: $10 \texttt{(Monday)} + 10 \texttt{(Tuesday)} + 10 \texttt{(Wednesday)} + 10 \texttt{(Thursday)} + 5 \texttt{(Friday)} = 45$

Test Case 2: The total number of working hours in a week are: $12 \texttt{(Monday)} + 12 \texttt{(Tuesday)} + 12 \texttt{(Wednesday)} + 12 \texttt{(Thursday)} + 2 \texttt{(Friday)} = 50$

Test Case 3: The total number of working hours in a week are: $8 \texttt{(Monday)} + 8 \texttt{(Tuesday)} + 8 \texttt{(Wednesday)} + 8 \texttt{(Thursday)} + 7 \texttt{(Friday)} = 39$

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