vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Alice and Bob begin their day with a quick game. They first choose a starting number X0 ≥ 3 and try to reach one million by the process described below. 

Alice goes first and then they take alternating turns. In the i-th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number.

Formally, he or she selects a prime p < Xi - 1 and then finds the minimum Xi ≥ Xi - 1 such that p divides Xi. Note that if the selected prime p already divides Xi - 1, then the number does not change.

Eve has witnessed the state of the game after two turns. Given X2, help her determine what is the smallest possible starting number X0. Note that the players don't necessarily play optimally. You should consider all possible game evolutions.

Input

The input contains a single integer X2 (4 ≤ X2 ≤ 106). It is guaranteed that the integer X2 is composite, that is, is not prime.

Output

Output a single integer — the minimum possible X0.

Examples

Input

14


Output

6


Input

20


Output

15


Input

8192


Output

8191

Note

In the first test, the smallest possible starting number is X0 = 6. One possible course of the game is as follows: 

  * Alice picks prime 5 and announces X1 = 10
  * Bob picks prime 7 and announces X2 = 14. 



In the second case, let X0 = 15. 

  * Alice picks prime 2 and announces X1 = 16
  * Bob picks prime 5 and announces X2 = 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has is the one with headID.
Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also it's guaranteed that the subordination relationships have a tree structure.
The head of the company wants to inform all the employees of the company of an urgent piece of news. He will inform his direct subordinates and they will inform their subordinates and so on until all employees know about the urgent news.
The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e After informTime[i] minutes, all his direct subordinates can start spreading the news).
Return the number of minutes needed to inform all the employees about the urgent news.
 
Example 1:
Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.

Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

Example 3:

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
Output: 21
Explanation: The head has id = 6. He will inform employee with id = 5 in 1 minute.
The employee with id = 5 will inform the employee with id = 4 in 2 minutes.
The employee with id = 4 will inform the employee with id = 3 in 3 minutes.
The employee with id = 3 will inform the employee with id = 2 in 4 minutes.
The employee with id = 2 will inform the employee with id = 1 in 5 minutes.
The employee with id = 1 will inform the employee with id = 0 in 6 minutes.
Needed time = 1 + 2 + 3 + 4 + 5 + 6 = 21.

Example 4:
Input: n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]
Output: 3
Explanation: The first minute the head will inform employees 1 and 2.
The second minute they will inform employees 3, 4, 5 and 6.
The third minute they will inform the rest of employees.

Example 5:
Input: n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914]
Output: 1076

 
Constraints:

1 <= n <= 10^5
0 <= headID < n
manager.length == n
0 <= manager[i] < n
manager[headID] == -1
informTime.length == n
0 <= informTime[i] <= 1000
informTime[i] == 0 if employee i has no subordinates.
It is guaranteed that all the employees can be informed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Stewie the Rabbit explores a new parallel universe. This two dimensional universe has the shape of a rectangular grid, containing n lines and m columns. The universe is very small: one cell of the grid can only contain one particle. Each particle in this universe is either static or dynamic. Each static particle always remains in one and the same position. Due to unintelligible gravitation laws no two static particles in the parallel universe can be present in one column or row, and they also can't be present in the diagonally adjacent cells. A dynamic particle appears in a random empty cell, randomly chooses the destination cell (destination cell may coincide with the start cell, see the samples) and moves there along the shortest path through the cells, unoccupied by the static particles. All empty cells have the same probability of being selected as the beginning or end of the path. Having reached the destination cell, the particle disappears. Only one dynamic particle can exist at one moment of time. This particle can move from a cell to a cell if they have an adjacent side, and this transition takes exactly one galactic second. Stewie got interested in what is the average lifespan of one particle in the given universe.

Input

The first line contains two space-separated integers: n, m (2 ≤ n, m ≤ 1000) which represent the sizes of the universe. The next n lines containing m symbols each describe the universe without dynamic particles — the j-th symbol of the i-th line equals to 'X' if the cell is occupied by a static particle, and to '.' if it is empty. It is guaranteed that the described universe satisfies the properties described above, that is no two static particles can be in one column or in one row, besides, they can't be positioned in the diagonally adjacent cells.

Output

You have to print on a single line a single number which is the average life span of a particle with an accuracy of at least 6 decimal places.

The answer will be accepted if it is within 10 - 6 of absolute or relative error from the correct answer.

Examples

Input

2 2
..
.X


Output

0.888888888889


Input

3 3
...
.X.
...


Output

2.000000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shaun is very much interested in Subarrays. Shaun wants to count the number of subarrays in his chosen array with sum being a multiple of $10^9$. Since, Shaun is interested in huge numbers.He chose his array such that it contains only $10^8$ and $9*10^8$ as its elements.
Help shaun to count the number of required subarrays.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each testcase contains one integer $N$,size of array $A$. 
- Second line of each testcase contains $N$ space separated array elements

-----Output:-----
For each testcase, output in a single line number of subarrays with sum being multiple of $10^9$.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $A[i]$=$10^8$ , $9*10^8$

-----Sample Input:-----
2
3
100000000 900000000 100000000
1
900000000

-----Sample Output:-----
2
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a rooted tree with N nodes and the root of the tree, R, is also given. Each node of the tree contains a value, that is initially empty. You have to mantain the tree under two operations:

Update Operation
Report Operation

Update Operation 

Each Update Operation begins with the character U. Character U is followed by 3 integers T, V and K. For every node which is the descendent of the node T, update it's value by adding V + d*K, where V and K are the parameters of the query and d is the distance of the node from T. Note that V is added to node T.  

Report Operation 

Each Report Operation begins with the character Q. Character Q is followed by 2 integers, A and B. Output the sum of values of nodes in the path from A to B modulo ($10^{9}$ + 7)  

Input Format 

The first Line consists of 3 space separated integers, N E R, where N is the number of nodes present, E is the total number of queries (update + report), and R is root of the tree.  

Each of the next N-1 lines contains 2 space separated integers, X and Y (X and Y are connected by an edge).

Thereafter, E lines follows: each line can represent either the Update Operation or the Report Operation.

Update Operation is of the form : U T V K.
Report Operation is of the form : Q A B.

Output Format 

Output the answer for every given report operation.

Constraints  

1 ≤ N, E ≤ $10^{5} $

1 ≤ E ≤ $10^{5} $

1 ≤ R, X, Y, T, A, B ≤ N 

1 ≤ V, K ≤ $10^{9} $

X ≠ Y

Sample Input

7 7 1
1 2
2 3
2 4
2 5
5 6
6 7
U 5 10 2
U 4 5 3
Q 1 7
U 6 7 4
Q 2 7
Q 1 4
Q 2 4

Sample Output

36
54
5
5

Explanation  

Values of Nodes after U 5 10 2: [0 0 0 0 10 12 14].
Values of Nodes after U 4 5 3: [0 0 0 5 10 12 14]. 
Sum of the Nodes from 1 to 7: 0 + 0 + 10 + 12 + 14 = 36.
Values of Nodes after U 6 7 4: [0 0 0 5 10 19 25].  
Sum of the Nodes from 2 to 7: 0 + 10 + 19 + 25 = 54. 
Sum of the Nodes from 1 to 4: 0 + 0 + 5 = 5.
Sum of the Nodes from 2 to 4: 0 + 5 = 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
 
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1

Example 3:
Input: coins = [1], amount = 0
Output: 0

Example 4:
Input: coins = [1], amount = 1
Output: 1

Example 5:
Input: coins = [1], amount = 2
Output: 2

 
Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the ith seat, and seats[i] = 0 represents that the ith seat is empty (0-indexed).
There is at least one empty seat, and at least one person sitting.
Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized. 
Return that maximum distance to the closest person.
 
Example 1:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:
Input: seats = [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat (i.e. seats[3]), the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Example 3:
Input: seats = [0,1]
Output: 1

 
Constraints:

2 <= seats.length <= 2 * 104
seats[i] is 0 or 1.
At least one seat is empty.
At least one seat is occupied.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
YOLO is a simple card game played between two players with a normal deck of 52 WWE cards, each having a rank, forming a sequence of 52 distinct values.

The game is composed of three rounds, and a player must win two rounds to win the game. At the beginning of the game the deck is shuffled and each player is given a hand of three cards. In each round the players show one card to each other, and the player with the wrestler of greater rank wins the round. The wrestlers contested in a round are discarded (i.e., they cannot be shown again).

It's post raksha-bandhan and Master Y and his sister love to play YOLO. Master Y is not very smart, losing frequently to his little sister. And when he loses, he cries so loud that no one can stand it. The assistant who deals the cards to Master Y and his sister is afraid he will lose his job if Master Y continues to lose the games. The assistant is allowed to see every card he deals, and after dealing five cards (three to the sister and two to Master Y) he wants to know which is the lowest ranked wrestler he should deal to Master Y so that there is no chance he will lose the game, no matter how badly Master Y plays.

SAMPLE INPUT
28 51 29 50 52
50 26 19 10 27
46 48 49 47 50
0

SAMPLE OUTPUT
30
-1
51

Explanation

Each test case is given in a single line that contains five distinct integers A, B, C, P and Q , describing the ranks dealt to the players. The first three cards are given to the sister (1 ≤ A, B, C ≤ 52) and the last two cards are given to Mr. Y (1 ≤ P, Q ≤ 52). The last test case is followed by a line containing a zero.

For each test case output a single line. If there exists a card that will make the Mr. Y win the game no matter how badly he plays, you must print the lowest rank on such a card. Otherwise, print ‘-1’.

This question is all about skills of test-case making.
Another 'good' test case:

10 20 30 24 26

Output: 21

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya commutes by train every day. There are n train stations in the city, and at the i-th station it's possible to buy only tickets to stations from i + 1 to a_{i} inclusive. No tickets are sold at the last station.

Let ρ_{i}, j be the minimum number of tickets one needs to buy in order to get from stations i to station j. As Vasya is fond of different useless statistic he asks you to compute the sum of all values ρ_{i}, j among all pairs 1 ≤ i < j ≤ n.


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of stations.

The second line contains n - 1 integer a_{i} (i + 1 ≤ a_{i} ≤ n), the i-th of them means that at the i-th station one may buy tickets to each station from i + 1 to a_{i} inclusive.


-----Output-----

Print the sum of ρ_{i}, j among all pairs of 1 ≤ i < j ≤ n.


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

Output
6

Input
5
2 3 5 5

Output
17



-----Note-----

In the first sample it's possible to get from any station to any other (with greater index) using only one ticket. The total number of pairs is 6, so the answer is also 6.

Consider the second sample:   ρ_{1, 2} = 1  ρ_{1, 3} = 2  ρ_{1, 4} = 3  ρ_{1, 5} = 3  ρ_{2, 3} = 1  ρ_{2, 4} = 2  ρ_{2, 5} = 2  ρ_{3, 4} = 1  ρ_{3, 5} = 1  ρ_{4, 5} = 1 

Thus the answer equals 1 + 2 + 3 + 3 + 1 + 2 + 2 + 1 + 1 + 1 = 17.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Stepan is a very experienced olympiad participant. He has n cups for Physics olympiads and m cups for Informatics olympiads. Each cup is characterized by two parameters — its significance c_{i} and width w_{i}.

Stepan decided to expose some of his cups on a shelf with width d in such a way, that:  there is at least one Physics cup and at least one Informatics cup on the shelf,  the total width of the exposed cups does not exceed d,  from each subjects (Physics and Informatics) some of the most significant cups are exposed (i. e. if a cup for some subject with significance x is exposed, then all the cups for this subject with significance greater than x must be exposed too). 

Your task is to determine the maximum possible total significance, which Stepan can get when he exposes cups on the shelf with width d, considering all the rules described above. The total significance is the sum of significances of all the exposed cups.


-----Input-----

The first line contains three integers n, m and d (1 ≤ n, m ≤ 100 000, 1 ≤ d ≤ 10^9) — the number of cups for Physics olympiads, the number of cups for Informatics olympiads and the width of the shelf.

Each of the following n lines contains two integers c_{i} and w_{i} (1 ≤ c_{i}, w_{i} ≤ 10^9) — significance and width of the i-th cup for Physics olympiads.

Each of the following m lines contains two integers c_{j} and w_{j} (1 ≤ c_{j}, w_{j} ≤ 10^9) — significance and width of the j-th cup for Informatics olympiads.


-----Output-----

Print the maximum possible total significance, which Stepan can get exposing cups on the shelf with width d, considering all the rules described in the statement.

If there is no way to expose cups on the shelf, then print 0.


-----Examples-----
Input
3 1 8
4 2
5 5
4 2
3 2

Output
8

Input
4 3 12
3 4
2 4
3 5
3 4
3 5
5 2
3 4

Output
11

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

Output
0



-----Note-----

In the first example Stepan has only one Informatics cup which must be exposed on the shelf. Its significance equals 3 and width equals 2, so after Stepan exposes it, the width of free space on the shelf becomes equal to 6. Also, Stepan must expose the second Physics cup (which has width 5), because it is the most significant cup for Physics (its significance equals 5). After that Stepan can not expose more cups on the shelf, because there is no enough free space. Thus, the maximum total significance of exposed cups equals to 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Frosh commencing their studies at Waterloo have diverse interests, as evidenced by their desire to take various combinations of courses from among those available.

University administrators are uncomfortable with this situation, and therefore wish to offer a conformity prize to frosh who choose one of the most popular combinations of courses. How many frosh will win the prize?

-----Input-----
The input begins with an integer $1 \leq n \leq 10000$, the number of frosh. For each frosh, a line follows containing the course numbers of five distinct courses selected by the frosh. Each course number is an integer between $100$ and $499$.

-----Output-----
The popularity of a combination is the number of frosh selecting exactly the same combination of courses. A combination of courses is considered most popular if no other combination has higher popularity. Output a single line giving the total number of students taking some combination of courses that is most popular.

-----Examples-----
Sample Input:
3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100
Sample Output:
2

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

Since everybody hates chaos and loves sorted lists we should implement some more sorting algorithms. Your task is to implement a Bubble sort (for some help look at https://en.wikipedia.org/wiki/Bubble_sort) and return a list of snapshots after **each change** of the initial list.

e.g. 

If the initial list would be l=[1,2,4,3] my algorithm rotates l[2] and l[3] and after that it adds [1,2,3,4] to the result, which is a list of snapshots.
```
[1,2,4,3] should return [ [1,2,3,4] ]
[2,1,4,3] should return [ [1,2,4,3], [1,2,3,4] ]
[1,2,3,4] should return []
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Jones Trucking Company tracks the location of each of its trucks on a grid similar to an (x, y) plane. The home office is at the location (0, 0). Read the coordinates of truck A and the coordinates of truck B and determine which is closer to the office.

-----Input:-----
The first line of the data set for this problem is an integer representing the number of collections of data that follow. Each collection contains 4 integers: the x-coordinate and then the 
y-coordinate of truck A followed by the x-coordinate and then the  y-coordinate of truck B.

-----Output:-----
All letters are upper case.
The output is to be formatted exactly like that for the sample output given below.

-----Assumptions:-----
The x-coordinate is in the range –20 .. 20. The y-coordinate is in the range –20 .. 20.

-----Discussion:-----
The distance between point #1 with coordinates (x1, y1) and point #2 with coordinates (x2, y2) is:

-----Sample Input:-----
4
3 -2 -5 -3
0 6 1 2
-7 8 4 -1
3 3 -2 2

-----Sample Output:-----
A IS CLOSER
B IS CLOSER
B IS CLOSER
B IS CLOSER

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of ones and zeroes, convert the equivalent binary value to an integer.

Eg: `[0, 0, 0, 1]` is treated as `0001` which is the binary representation of `1`.

Examples:
```
Testing: [0, 0, 0, 1] ==> 1
Testing: [0, 0, 1, 0] ==> 2
Testing: [0, 1, 0, 1] ==> 5
Testing: [1, 0, 0, 1] ==> 9
Testing: [0, 0, 1, 0] ==> 2
Testing: [0, 1, 1, 0] ==> 6
Testing: [1, 1, 1, 1] ==> 15
Testing: [1, 0, 1, 1] ==> 11
```

However, the arrays can have varying lengths, not just limited to `4`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an array, $\mbox{A}$, of length $n$. We can split $\mbox{A}$ into contiguous segments called pieces and store them as another array, $\mbox{B}$. For example, if $A=[1,2,3]$, we have the following arrays of pieces:

$B=[(1),(2),(3)]$ contains three $\mbox{1}$-element pieces.
$B=[(1,2),(3)]$ contains two pieces, one having $2$ elements and the other having $\mbox{1}$ element.
$B=[(1),(2,3)]$ contains two pieces, one having $\mbox{1}$ element and the other having $2$ elements.
$B=[(1,2,3)]$ contains one $3$-element piece.

We consider the value of a piece in some array $\mbox{B}$ to be $\textit{(sum of all numbers in the piece)}\times\textit{(length of piece)}$, and we consider the total value of some array $\mbox{B}$ to be the sum of the values for all pieces in that $\mbox{B}$. For example, the total value of $B=[(1,2,4),(5,1),(2)]$ is $(1+2+4)\times3+(5+1)\times2+(2)\times1=35$.

Given $\mbox{A}$, find the total values for all possible $\mbox{B}$'s, sum them together, and print this sum modulo $(10^9+7)$ on a new line.

Input Format

The first line contains a single integer, $n$, denoting the size of array $\mbox{A}$. 

The second line contains $n$ space-separated integers describing the respective values in $\mbox{A}$ (i.e., $a_0,a_1,\ldots,a_{n-1}$).

Constraints

$1\leq n\leq10^{6}$
$1\leq a_i\leq10^9$

Output Format

Print a single integer denoting the sum of the total values for all piece arrays ($\mbox{B}$'s) of $\mbox{A}$, modulo $(10^9+7)$.

Sample Input 0

3
1 3 6

Sample Output 0

73

Explanation 0 

Given $A=[1,3,6]$, our piece arrays are:

$B=[(1),(3),(6)]$, and $total value=(1)\times1+(3)\times1+(6)\times1=10$.
$B=[(1,3),(6)]$, and $total value=(1+3)\times2+(6)\times1=14$.
$B=[(1),(3,6)]$, and $total value=(1)\times1+(3+6)\times2=19$.
$B=[(1,3,6)]$, and $total value=(1+3+6)\times3=30$.

When we sum all the total values, we get $10+14+19+30=73$. Thus, we print the result of $73\ \text{mod}\ (10^9+7)=73$ on a new line.

Sample Input 1

5
4 2 9 10 1

Sample Output 1

971

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