vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There were n types of swords in the theater basement which had been used during the plays. Moreover there were exactly x swords of each type. y people have broken into the theater basement and each of them has taken exactly z swords of some single type. Note that different people might have taken different types of swords. Note that the values x, y and z are unknown for you.

The next morning the director of the theater discovers the loss. He counts all swords — exactly a_i swords of the i-th type are left untouched.

The director has no clue about the initial number of swords of each type in the basement, the number of people who have broken into the basement and how many swords each of them have taken.

For example, if n=3, a = [3, 12, 6] then one of the possible situations is x=12, y=5 and z=3. Then the first three people took swords of the first type and the other two people took swords of the third type. Note that you don't know values x, y and z beforehand but know values of n and a.

Thus he seeks for your help. Determine the minimum number of people y, which could have broken into the theater basement, and the number of swords z each of them has taken.

Input

The first line of the input contains one integer n (2 ≤ n ≤ 2 ⋅ 10^{5}) — the number of types of swords.

The second line of the input contains the sequence a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^{9}), where a_i equals to the number of swords of the i-th type, which have remained in the basement after the theft. It is guaranteed that there exists at least one such pair of indices (j, k) that a_j ≠ a_k.

Output

Print two integers y and z — the minimum number of people which could have broken into the basement and the number of swords each of them has taken.

Examples

Input


3
3 12 6


Output


5 3


Input


2
2 9


Output


1 7


Input


7
2 1000000000 4 6 8 4 2


Output


2999999987 2


Input


6
13 52 0 13 26 52


Output


12 13

Note

In the first example the minimum value of y equals to 5, i.e. the minimum number of people who could have broken into the basement, is 5. Each of them has taken 3 swords: three of them have taken 3 swords of the first type, and two others have taken 3 swords of the third type.

In the second example the minimum value of y is 1, i.e. the minimum number of people who could have broken into the basement, equals to 1. He has taken 7 swords of the first type.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya has a string of length *n* consisting of small and large English letters and digits.

He performs *m* operations. Each operation is described with two integers *l* and *r* and a character *c*: Petya removes from the string all characters *c* on positions between *l* and *r*, inclusive. It's obvious that the length of the string remains the same or decreases after each operation.

Find how the string will look like after Petya performs all *m* operations.

Input Specification:
The first string contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=2·105) — the length of the string and the number of operations.

The second line contains the string of length *n*, consisting of small and large English letters and digits. Positions in the string are enumerated from 1.

Each of the next *m* lines contains two integers *l* and *r* (1<=≤<=*l*<=≤<=*r*), followed by a character *c*, which is a small or large English letter or a digit. This line describes one operation. It is guaranteed that *r* doesn't exceed the length of the string *s* before current operation.

Output Specification:
Print the string Petya will obtain after performing all *m* operations. If the strings becomes empty after all operations, print an empty line.

Demo Input:
['4 2\nabac\n1 3 a\n2 2 c\n', '3 2\nA0z\n1 3 0\n1 1 z\n', '10 4\nagtFrgF4aF\n2 5 g\n4 9 F\n1 5 4\n1 7 a\n', '9 5\naAAaBBccD\n1 4 a\n5 6 c\n2 3 B\n4 4 D\n2 3 A\n']

Demo Output:
['b\n', 'Az\n', 'tFrg4\n', 'AB\n']

Note:
In the first example during the first operation both letters 'a' are removed, so the string becomes "bc". During the second operation the letter 'c' (on the second position) is removed, and the string becomes "b".

In the second example during the first operation Petya removes '0' from the second position. After that the string becomes "Az". During the second operations the string doesn't change.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The numbers 12, 63 and 119 have something in common related with their divisors and their prime factors, let's see it.
```
Numbers PrimeFactorsSum(pfs)        DivisorsSum(ds)              Is ds divisible by pfs
12         2 + 2 + 3 = 7         1 + 2 + 3 + 4 + 6 + 12 = 28            28 / 7 = 4,  Yes
63         3 + 3 + 7 = 13        1 + 3 + 7 + 9 + 21 + 63 = 104         104 / 13 = 8, Yes
119        7 + 17 = 24           1 + 7 + 17 + 119 = 144                144 / 24 = 6, Yes
```
There is an obvius property you can see: the sum of the divisors of a number is divisible by the sum of its prime factors.

We need the function ```ds_multof_pfs()``` that receives two arguments: ```nMin``` and  ```nMax```, as a lower and upper limit (inclusives), respectively, and outputs a sorted list with the numbers that fulfill the property described above.

We represent the features of the described function:
```python
ds_multof_pfs(nMin, nMax) -----> [n1, n2, ....., nl] # nMin ≤ n1 < n2 < ..< nl ≤ nMax
```
Let's see some cases:
```python
ds_multof_pfs(10, 100) == [12, 15, 35, 42, 60, 63, 66, 68, 84, 90, 95]

ds_multof_pfs(20, 120) == [35, 42, 60, 63, 66, 68, 84, 90, 95, 110, 114, 119]
```
Enjoy it!!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Memory is now interested in the de-evolution of objects, specifically triangles. He starts with an equilateral triangle of side length x, and he wishes to perform operations to obtain an equilateral triangle of side length y.

In a single second, he can modify the length of a single side of the current triangle such that it remains a non-degenerate triangle (triangle of positive area). At any moment of time, the length of each side should be integer.

What is the minimum number of seconds required for Memory to obtain the equilateral triangle of side length y?


-----Input-----

The first and only line contains two integers x and y (3 ≤ y < x ≤ 100 000) — the starting and ending equilateral triangle side lengths respectively.


-----Output-----

Print a single integer — the minimum number of seconds required for Memory to obtain the equilateral triangle of side length y if he starts with the equilateral triangle of side length x.


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

Output
4

Input
8 5

Output
3

Input
22 4

Output
6



-----Note-----

In the first sample test, Memory starts with an equilateral triangle of side length 6 and wants one of side length 3. Denote a triangle with sides a, b, and c as (a, b, c). Then, Memory can do $(6,6,6) \rightarrow(6,6,3) \rightarrow(6,4,3) \rightarrow(3,4,3) \rightarrow(3,3,3)$.

In the second sample test, Memory can do $(8,8,8) \rightarrow(8,8,5) \rightarrow(8,5,5) \rightarrow(5,5,5)$.

In the third sample test, Memory can do: $(22,22,22) \rightarrow(7,22,22) \rightarrow(7,22,16) \rightarrow(7,10,16) \rightarrow(7,10,4) \rightarrow$

$(7,4,4) \rightarrow(4,4,4)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. X stays in a mansion whose door opens in the North. He travels every morning to meet his friend Ms. Y walking a predefined path.

To cut the distance short, one day he decides to construct a skywalk from his place to his friend’s place. Help him to find the shortest distance between the two residences.


-----Input-----

The first line contains a single positive integer T <= 100, the number of test cases. T test cases follow. The only line of each test case contains a string which is the path from X to Y. The integer value represents the distance. The character R or L represents a Right or a Left respectively.

-----Output-----

For each test case, output a single line containing the minimum distance and the direction(N,S,W,E,NE,NW,SE,SW) of Y’s residence with respect to X’s residence. The output distance should have only 1 decimal place with no approximation. Print “0.0” if X’s and Y’s residence coincide.

-----Example-----
Input:
1
2 L 2 R 2 L 1

Output:
5.0NW

Explanation
Mr. X travels 2units and then takes a Left, and then he travels 2units and takes a Right, then after travelling 2units he takes a Left and finally travels 1unit to reach Y’s residence.
(Unlike Input, Output does not have spaces between the distance and direction)

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The Hedgehog recently remembered one of his favorite childhood activities, — solving puzzles, and got into it with new vigor. He would sit day in, day out with his friend buried into thousands of tiny pieces of the picture, looking for the required items one by one.

Soon the Hedgehog came up with a brilliant idea: instead of buying ready-made puzzles, one can take his own large piece of paper with some picture and cut it into many small rectangular pieces, then mix them and solve the resulting puzzle, trying to piece together the picture. The resulting task is even more challenging than the classic puzzle: now all the fragments have the same rectangular shape, and one can assemble the puzzle only relying on the picture drawn on the pieces.

All puzzle pieces turn out to be of the same size *X*<=×<=*Y*, because the picture is cut first by horizontal cuts with the pitch of *X*, then with vertical cuts with the pitch of *Y*. If we denote the initial size of the picture as *A*<=×<=*B*, then *A* must be divisible by *X* and *B* must be divisible by *Y* (*X* and *Y* are integer numbers). 

However, not every such cutting of the picture will result in a good puzzle. The Hedgehog finds a puzzle good if no two pieces in it are the same (It is allowed to rotate the pieces when comparing them, but it is forbidden to turn them over). 

Your task is to count for a given picture the number of good puzzles that you can make from it, and also to find the puzzle with the minimal piece size.

Input Specification:
The first line contains two numbers *A* and *B* which are the sizes of the picture. They are positive integers not exceeding 20.

Then follow *A* lines containing *B* symbols each, describing the actual picture. The lines only contain uppercase English letters.

Output Specification:
In the first line print the number of possible good puzzles (in other words, the number of pairs (*X*,<=*Y*) such that the puzzle with the corresponding element sizes will be good). This number should always be positive, because the whole picture is a good puzzle itself. 

In the second line print two numbers — the sizes *X* and *Y* of the smallest possible element among all good puzzles. The comparison is made firstly by the area *XY* of one element and secondly — by the length *X*.

Demo Input:
['2 4\nABDC\nABDC\n', '2 6\nABCCBA\nABCCBA\n']

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

Note:
The picture in the first sample test has the following good puzzles: (2, 1), (2, 2), (2, 4).

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

Time Limit: 5 seconds

Memory Limit: 256 megabytes

Problem Description:
Little Masha loves arranging her toys into piles on the floor. And she also hates it when somebody touches her toys. One day Masha arranged all her *n* toys into several piles and then her elder brother Sasha came and gathered all the piles into one. Having seen it, Masha got very upset and started crying. Sasha still can't calm Masha down and mom is going to come home soon and punish Sasha for having made Masha crying. That's why he decides to restore the piles' arrangement. However, he doesn't remember at all the way the toys used to lie. Of course, Masha remembers it, but she can't talk yet and can only help Sasha by shouting happily when he arranges the toys in the way they used to lie. That means that Sasha will have to arrange the toys in every possible way until Masha recognizes the needed arrangement. The relative position of the piles and toys in every pile is irrelevant, that's why the two ways of arranging the toys are considered different if can be found two such toys that when arranged in the first way lie in one and the same pile and do not if arranged in the second way. Sasha is looking for the fastest way of trying all the ways because mom will come soon. With every action Sasha can take a toy from any pile and move it to any other pile (as a result a new pile may appear or the old one may disappear). Sasha wants to find the sequence of actions as a result of which all the pile arrangement variants will be tried exactly one time each. Help Sasha. As we remember, initially all the toys are located in one pile.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=10) — the number of toys.

Output Specification:
In the first line print the number of different variants of arrangement of toys into piles. Then print all the ways of arranging toys into piles in the order in which Sasha should try them (i.e. every next way must result from the previous one through the operation described in the statement). Every way should be printed in the following format. In every pile the toys should be arranged in ascending order of the numbers. Then the piles should be sorted in ascending order of the numbers of the first toys there. Output every way on a single line. Cf. the example to specify the output data format. If the solution is not unique, output any of them.

Demo Input:
['3\n']

Demo Output:
['5\n{1,2,3}\n{1,2},{3}\n{1},{2,3}\n{1},{2},{3}\n{1,3},{2}']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Amr bought a new video game "Guess Your Way Out!". The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node. 

Let's index all the leaf nodes from the left to the right from 1 to 2^{h}. The exit is located at some node n where 1 ≤ n ≤ 2^{h}, the player doesn't know where the exit is so he has to guess his way out!

Amr follows simple algorithm to choose the path. Let's consider infinite command string "LRLRLRLRL..." (consisting of alternating characters 'L' and 'R'). Amr sequentially executes the characters of the string using following rules:  Character 'L' means "go to the left child of the current node";  Character 'R' means "go to the right child of the current node";  If the destination node is already visited, Amr skips current command, otherwise he moves to the destination node;  If Amr skipped two consecutive commands, he goes back to the parent of the current node before executing next command;  If he reached a leaf node that is not the exit, he returns to the parent of the current node;  If he reaches an exit, the game is finished. 

Now Amr wonders, if he follows this algorithm, how many nodes he is going to visit before reaching the exit?


-----Input-----

Input consists of two integers h, n (1 ≤ h ≤ 50, 1 ≤ n ≤ 2^{h}).


-----Output-----

Output a single integer representing the number of nodes (excluding the exit node) Amr is going to visit before reaching the exit by following this algorithm.


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

Output
2
Input
2 3

Output
5
Input
3 6

Output
10
Input
10 1024

Output
2046


-----Note-----

A perfect binary tree of height h is a binary tree consisting of h + 1 levels. Level 0 consists of a single node called root, level h consists of 2^{h} nodes called leaves. Each node that is not a leaf has exactly two children, left and right one. 

Following picture illustrates the sample test number 3. Nodes are labeled according to the order of visit.

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Batman is about to face Superman so he decides to prepare for the battle by upgrading his Batmobile. He manufactures multiple duplicates of his standard Batmobile each tweaked in a different way such that the maximum speed of each is never less than that of the standard model.
After carrying out this process, he wishes to know how many of his prototypes are faster than his standard Batmobile?

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follow: 
- The first line of each test case contains a single integer N denoting the number of copies of the standard Batmobile.
- The second line contains a sequence of N+1 space-separated integers, S0 to SN, sorted in non-decreasing order separated by space. S0 is the maximum speed of the standard Batmobile. S1 to SN denote the maximum speeds of the prototypes.

-----Output-----
- For each test case, output a single line containing an integer denoting the answer.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 1000
- 1 ≤ Si ≤ 109

-----Example-----
Input:
2
4
1 2 3 4 5
5
1 10 100 1000 10000 100000

Output:
4
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the number of ways of distributing N objects into R groups such that each group gets 1 or more objects.

Input:
The one and only line of input contains two numbers separated by a single space, which are N and R respectively.

Output:
The corresponding answer modulo 10000007 in a  single line and if no answer exist then print "-1".

Constraints:
1 ≤ N ≤ 100
1 ≤ R ≤ 100  

SAMPLE INPUT
4 2

SAMPLE OUTPUT
3

Explanation

Let the 2 groups be A and B respectively.
Case 1: A gets 1 object and B gets 3
Case 2: A gets 2 objects and B gets 2
Case 3: A gets 3 objects and B gets 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array (or list or vector) of arrays (or, guess what, lists or vectors) of integers, your goal is to return the sum of a specific set of numbers, starting with elements whose position is equal to the main array length and going down by one at each step.

Say for example the parent array (etc, etc) has 3 sub-arrays inside: you should consider the third  element of the first sub-array, the second of the second array and the first element in the third one: `[[3, 2, 1, 0], [4, 6, 5, 3, 2], [9, 8, 7, 4]]` would have you considering `1` for `[3, 2, 1, 0]`, `6` for `[4, 6, 5, 3, 2]` and `9` for `[9, 8, 7, 4]`, which sums up to `16`.

One small note is that not always each sub-array will have enough elements, in which case you should then use a default value (if provided) or `0` (if not provided), as shown in the test cases.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two binary strings $a$ and $b$ of the same length. You can perform the following two operations on the string $a$:

  Swap any two bits at indices $i$ and $j$ respectively ($1 \le i, j \le n$), the cost of this operation is $|i - j|$, that is, the absolute difference between $i$ and $j$.  Select any arbitrary index $i$ ($1 \le i \le n$) and flip (change $0$ to $1$ or $1$ to $0$) the bit at this index. The cost of this operation is $1$. 

Find the minimum cost to make the string $a$ equal to $b$. It is not allowed to modify string $b$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the length of the strings $a$ and $b$.

The second and third lines contain strings $a$ and $b$ respectively.

Both strings $a$ and $b$ have length $n$ and contain only '0' and '1'.


-----Output-----

Output the minimum cost to make the string $a$ equal to $b$.


-----Examples-----
Input
3
100
001

Output
2

Input
4
0101
0011

Output
1



-----Note-----

In the first example, one of the optimal solutions is to flip index $1$ and index $3$, the string $a$ changes in the following way: "100" $\to$ "000" $\to$ "001". The cost is $1 + 1 = 2$.

The other optimal solution is to swap bits and indices $1$ and $3$, the string $a$ changes then "100" $\to$ "001", the cost is also $|1 - 3| = 2$.

In the second example, the optimal solution is to swap bits at indices $2$ and $3$, the string $a$ changes as "0101" $\to$ "0011". The cost is $|2 - 3| = 1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya wants to climb up a stair of certain amount of steps (Input parameter 1). There are 2 simple rules that he has to stick to.

1. Vasya can climb 1 or 2 steps at each move.
2. Vasya wants the number of moves to be a multiple of a certain integer. (Input parameter 2).

### Task:
What is the `MINIMAL` number of moves making him climb to the top of the stairs that satisfies his conditions?

### Input

1. Number of stairs:    `0 <  N  ≤ 10000` ;
2. Integer to be multiplied : `1 < M ≤ 10 `;

### Output

1. Return a single integer - the minimal number of moves being a multiple of M;
2. If there is no way he can climb satisfying condition return - 1 instead. (`Nothing` in Haskell)

### Examples

```python
numberOfSteps(10, 2) => 6  # Sequence of steps : {2, 2, 2, 2, 1, 1}

numberOfSteps(3, 5) => -1 # !Possible sequences of steps : {2, 1}, {1, 2}, {1, 1, 1}
```
``` haskell
numberOfSteps 10 2 == Just 6  -- Sequence of steps : {2, 2, 2, 2, 1, 1}
numberOfSteps  3 5 == Nothing -- Not possible, since the sequences of steps would be {2, 1}, {1, 2} or {1, 1, 1}
```

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