vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Musicians of a popular band "Flayer" have announced that they are going to "make their exit" with a world tour. Of course, they will visit Berland as well.

There are n cities in Berland. People can travel between cities using two-directional train routes; there are exactly m routes, i-th route can be used to go from city v_{i} to city u_{i} (and from u_{i} to v_{i}), and it costs w_{i} coins to use this route.

Each city will be visited by "Flayer", and the cost of the concert ticket in i-th city is a_{i} coins.

You have friends in every city of Berland, and they, knowing about your programming skills, asked you to calculate the minimum possible number of coins they have to pay to visit the concert. For every city i you have to compute the minimum number of coins a person from city i has to spend to travel to some city j (or possibly stay in city i), attend a concert there, and return to city i (if j ≠ i).

Formally, for every $i \in [ 1, n ]$ you have to calculate $\operatorname{min}_{j = 1} 2 d(i, j) + a_{j}$, where d(i, j) is the minimum number of coins you have to spend to travel from city i to city j. If there is no way to reach city j from city i, then we consider d(i, j) to be infinitely large.


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 2·10^5, 1 ≤ m ≤ 2·10^5).

Then m lines follow, i-th contains three integers v_{i}, u_{i} and w_{i} (1 ≤ v_{i}, u_{i} ≤ n, v_{i} ≠ u_{i}, 1 ≤ w_{i} ≤ 10^12) denoting i-th train route. There are no multiple train routes connecting the same pair of cities, that is, for each (v, u) neither extra (v, u) nor (u, v) present in input.

The next line contains n integers a_1, a_2, ... a_{k} (1 ≤ a_{i} ≤ 10^12) — price to attend the concert in i-th city.


-----Output-----

Print n integers. i-th of them must be equal to the minimum number of coins a person from city i has to spend to travel to some city j (or possibly stay in city i), attend a concert there, and return to city i (if j ≠ i).


-----Examples-----
Input
4 2
1 2 4
2 3 7
6 20 1 25

Output
6 14 1 25 

Input
3 3
1 2 1
2 3 1
1 3 1
30 10 20

Output
12 10 12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer $x$, find two non-negative integers $a$ and $b$ such that $(a \wedge b) + (a \vee b) = x$, where $\wedge$ is the bitwise AND operation and $\vee$ is the bitwise OR operation.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single integer $x$.

-----Output-----
If there is no valid pair $(a, b)$, print a single line containing the integer $-1$. Otherwise, print a single line containing two space-separated integers $a$ and $b$.
If there are multiple solutions, you may print any one of them.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le x \le 10^{18}$

-----Subtasks-----
Subtask #1 (30 points):
- $1 \le T \le 200$
- $1 \le x \le 200$
Subtask #2 (70 points): original constraints

-----Example Input-----
2
1
8

-----Example Output-----
0 1
5 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the official contest this problem has a different statement, for which jury's solution was working incorrectly, and for this reason it was excluded from the contest. This mistake have been fixed and the current given problem statement and model solution corresponds to what jury wanted it to be during the contest.

Vova and Lesha are friends. They often meet at Vova's place and compete against each other in a computer game named The Ancient Papyri: Swordsink. Vova always chooses a warrior as his fighter and Leshac chooses an archer. After that they should choose initial positions for their characters and start the fight. A warrior is good at melee combat, so Vova will try to make the distance between fighters as small as possible. An archer prefers to keep the enemy at a distance, so Lesha will try to make the initial distance as large as possible.

There are n (n is always even) possible starting positions for characters marked along the Ox axis. The positions are given by their distinct coordinates x_1, x_2, ..., x_{n}, two characters cannot end up at the same position.

Vova and Lesha take turns banning available positions, Vova moves first. During each turn one of the guys bans exactly one of the remaining positions. Banned positions cannot be used by both Vova and Lesha. They continue to make moves until there are only two possible positions remaining (thus, the total number of moves will be n - 2). After that Vova's character takes the position with the lesser coordinate and Lesha's character takes the position with the bigger coordinate and the guys start fighting.

Vova and Lesha are already tired by the game of choosing positions, as they need to play it before every fight, so they asked you (the developer of the The Ancient Papyri: Swordsink) to write a module that would automatically determine the distance at which the warrior and the archer will start fighting if both Vova and Lesha play optimally.


-----Input-----

The first line on the input contains a single integer n (2 ≤ n ≤ 200 000, n is even) — the number of positions available initially. The second line contains n distinct integers x_1, x_2, ..., x_{n} (0 ≤ x_{i} ≤ 10^9), giving the coordinates of the corresponding positions.


-----Output-----

Print the distance between the warrior and the archer at the beginning of the fight, provided that both Vova and Lesha play optimally.


-----Examples-----
Input
6
0 1 3 7 15 31

Output
7

Input
2
73 37

Output
36



-----Note-----

In the first sample one of the optimum behavior of the players looks like that:  Vova bans the position at coordinate 15;  Lesha bans the position at coordinate 3;  Vova bans the position at coordinate 31;  Lesha bans the position at coordinate 1. 

After these actions only positions 0 and 7 will remain, and the distance between them is equal to 7.

In the second sample there are only two possible positions, so there will be no bans.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a follow up from my kata The old switcheroo

Write
```python
def encode(str)
```
that takes in a string ```str``` and replaces all the letters with their respective positions in the English alphabet.

```python
encode('abc') == '123'   # a is 1st in English alpabet, b is 2nd and c is 3rd
encode('codewars') == '315452311819'
encode('abc-#@5') == '123-#@5'
```
String are case sensitive.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Emily and Mia are friends. Emily got Mia’s essay paper, but since she is a prankster, she decided to meddle with the words present in the paper. She changes all the words in the paper into palindromes. To do this, she follows two rules: 
- In one operation she can only reduce the value of an alphabet by 1, i.e.  she can change ‘d’ to ‘c’, but she cannot change ‘c’ to ‘d’ or ‘d’ to ‘b’. 
- The alphabet ‘a’ will not be reduced any further. 
Each reduction in the value of any alphabet is counted as a single operation. Find the minimum number of operations required to convert a given string into a palindrome.

-----Input:-----
- The first line contains an integer $T$, denoting the number of test cases. 
- Each test case consists of a string $S$ containing only lowercase characters with no spaces.

-----Output:-----
For each test case on a new line, print the minimum number of operations for the corresponding test case.

-----Constraints-----
- $1<=T<=10$
- $1<=|S|<=10^7$, where $|S|$ denotes length of string S.

-----Sample Input:-----
4 
abc 
abcba 
abcd 
cba

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

-----EXPLANATION:-----
For the first test case string = “abc” 
c->b->a so the string become “aba” which is a palindrome. For this we perform 2 operations

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N points in a two-dimensional plane.

The coordinates of the i-th point (1 \leq i \leq N) are (x_i,y_i).

Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior.

Here, points on the sides of the rectangle are considered to be in the interior.

Find the minimum possible area of such a rectangle.  

-----Constraints-----
 - 2 \leq K \leq N \leq 50 
 - -10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N) 
 - x_i≠x_j (1 \leq i<j \leq N) 
 - y_i≠y_j (1 \leq i<j \leq N) 
 - All input values are integers. (Added at 21:50 JST)  

-----Input-----
Input is given from Standard Input in the following format:  
N K  
x_1 y_1
:  
x_{N} y_{N}

-----Output-----
Print the minimum possible area of a rectangle that satisfies the condition.  

-----Sample Input-----
4 4
1 4
3 3
6 2
8 1

-----Sample Output-----
21

One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1), (8,1), (1,4) and (8,4).

Its area is (8-1) × (4-1) = 21.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:


       If there exists a solution, it is guaranteed to be unique.
       Both input arrays are non-empty and have the same length.
       Each element in the input arrays is a non-negative integer.


Example 1:


Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.


Example 2:


Input: 
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a grid of H rows and W columns. Initially, there is a stone in the top left cell. Shik is trying to move the stone to the bottom right cell. In each step, he can move the stone one cell to its left, up, right, or down (if such cell exists). It is possible that the stone visits a cell multiple times (including the bottom right and the top left cell).

You are given a matrix of characters a_{ij} (1 \leq i \leq H, 1 \leq j \leq W). After Shik completes all moving actions, a_{ij} is `#` if the stone had ever located at the i-th row and the j-th column during the process of moving. Otherwise, a_{ij} is `.`. Please determine whether it is possible that Shik only uses right and down moves in all steps.

Constraints

* 2 \leq H, W \leq 8
* a_{i,j} is either `#` or `.`.
* There exists a valid sequence of moves for Shik to generate the map a.

Input

The input is given from Standard Input in the following format:


H W
a_{11}a_{12}...a_{1W}
:
a_{H1}a_{H2}...a_{HW}


Output

If it is possible that Shik only uses right and down moves, print `Possible`. Otherwise, print `Impossible`.

Examples

Input

4 5
##...
.##..
..##.
...##


Output

Possible


Input

4 5
...
.##..
..##.
...##


Output

Possible


Input

5 3

..#

..


Output

Impossible


Input

4 5
...
.###.
.###.
...##


Output

Impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Most problems on CodeChef highlight chef's love for food and cooking but little is known about his love for racing sports. He is an avid Formula 1 fan. He went to watch this year's Indian Grand Prix at New Delhi. He noticed that one segment of the circuit was a long straight road. It was impossible for a car to overtake other cars on this segment. Therefore, a car had to lower down its speed if there was a slower car in front of it. While watching the race, Chef started to wonder how many cars were moving at their maximum speed.
Formally, you're given the maximum speed of N cars in the order they entered the long straight segment of the circuit. Each car prefers to move at its maximum speed. If that's not possible because of the front car being slow, it might have to lower its speed. It still moves at the fastest possible speed while avoiding any collisions. For the purpose of this problem, you can assume that the straight segment is infinitely long.
Count the number of cars which were moving at their maximum speed on the straight segment.

-----Input-----
The first line of the input contains a single integer T denoting the number of test cases to follow. Description of each test case contains 2 lines. The first of these lines contain a single integer N, the number of cars. The second line contains N space separated integers, denoting the maximum speed of the cars in the order they entered the long straight segment.

-----Output-----
For each test case, output a single line containing the number of cars which were moving at their maximum speed on the segment.

-----Example-----
Input:
3
1
10
3
8 3 6
5
4 5 1 2 3

Output:
1
2
2

-----Constraints-----

1 ≤ T ≤ 100

1 ≤ N ≤ 10,000

All speeds are distinct positive integers that fit in a 32 bit signed integer.

Each input file will not be larger than 4 MB (4,000,000,000 bytes) in size.

WARNING! The input files are very large. Use faster I/O.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer n. Output its prime factorization.

If n = a1b1a2b2 ... akbk, where ak are prime numbers, the output of your program should look as follows: a1 a1 ... a1 a2 a2 ... a2 ... ak ak ... ak, where factors are ordered in non-decreasing order, and each factor ai is printed bi times.

Input

The only line of input contains an integer n (2 ≤ n ≤ 250).

Output

Output the prime factorization of n, as described above.

Examples

Input

245


Output

5 7 7 


Input

13


Output

13

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Anton's favourite geometric figures are regular polyhedrons. Note that there are five kinds of regular polyhedrons: 
 -  Tetrahedron. Tetrahedron has 4 triangular faces. -  Cube. Cube has 6 square faces. -  Octahedron. Octahedron has 8 triangular faces. -  Dodecahedron. Dodecahedron has 12 pentagonal faces. -  Icosahedron. Icosahedron has 20 triangular faces. 
All five kinds of polyhedrons are shown on the picture below:

Anton has a collection of *n* polyhedrons. One day he decided to know, how many faces his polyhedrons have in total. Help Anton and find this number!

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=200<=000) — the number of polyhedrons in Anton's collection.

Each of the following *n* lines of the input contains a string *s**i* — the name of the *i*-th polyhedron in Anton's collection. The string can look like this:
 -  "Tetrahedron" (without quotes), if the *i*-th polyhedron in Anton's collection is a tetrahedron. -  "Cube" (without quotes), if the *i*-th polyhedron in Anton's collection is a cube. -  "Octahedron" (without quotes), if the *i*-th polyhedron in Anton's collection is an octahedron. -  "Dodecahedron" (without quotes), if the *i*-th polyhedron in Anton's collection is a dodecahedron. -  "Icosahedron" (without quotes), if the *i*-th polyhedron in Anton's collection is an icosahedron.

Output Specification:
Output one number — the total number of faces in all the polyhedrons in Anton's collection.

Demo Input:
['4\nIcosahedron\nCube\nTetrahedron\nDodecahedron\n', '3\nDodecahedron\nOctahedron\nOctahedron\n']

Demo Output:
['42\n', '28\n']

Note:
In the first sample Anton has one icosahedron, one cube, one tetrahedron and one dodecahedron. Icosahedron has 20 faces, cube has 6 faces, tetrahedron has 4 faces and dodecahedron has 12 faces. In total, they have 20 + 6 + 4 + 12 = 42 faces.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N points on the 2D plane, i-th of which is located on (x_i, y_i).
There can be multiple points that share the same coordinate.
What is the maximum possible Manhattan distance between two distinct points?
Here, the Manhattan distance between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

-----Constraints-----
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq x_i,y_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
:
x_N y_N

-----Output-----
Print the answer.

-----Sample Input-----
3
1 1
2 4
3 2

-----Sample Output-----
4

The Manhattan distance between the first point and the second point is |1-2|+|1-4|=4, which is maximum possible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ã¢â¬â¹Given a number x, your task is to find if this number is Deficient number or not. A number x is said to be Deficient Number if sum of all the divisors of the number denoted by divisorsSum(x) is less than twice the value of the number x. And the difference between these two values is called the deficiency.
Mathematically, if below condition holds the number is said to be Deficient:
divisorsSum(x) < 2*x
deficiency = (2*x) - divisorsSum(x)
Example 1:
Input: x = 21
Output: YES 
Explanation: Divisors are 1, 3, 7 and
21.Sum of divisors is 32. 
This sum is less than 2*21 or 42.
Example 2:
Input: x = 12
Output: NO
Explanation: Divisors are 1, 2, 3, 4,
6 and 12.Sum of divisors is 28.
This sum is not less than 2*12 or 24.
Your Task:  
You dont need to read input or print anything. Complete the function isDeficient() which takes x as input parameter and returns YES if the number is Deficient otherwise returns NO.
Expected Time Complexity: O(sqrt(n))
Expected Auxiliary Space: O(1)
Constraints:
1<= x <=10000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have got a new job, and it's very interesting, you are a ship captain. Your first task is to move your ship from one point to another point, and for sure you want to move it at the minimum cost.

And it's well known that the shortest distance between any 2 points is the length of the line segment between these 2 points. But unfortunately there is an island in the sea, so sometimes you won't be able to move your ship in the line segment between the 2 points.

You can only move to safe points. A point is called safe if it's on the line segment between the start and end points, or if it's on the island's edge.

But you are too lucky, you have got some clever and strong workers and they can help you in your trip, they can help you move the ship in the sea and they will take 1 Egyptian pound for each moving unit in the sea, and they can carry the ship (yes, they are very strong) and walk on the island and they will take 2 Egyptian pounds for each moving unit in the island. The money which you will give to them will be divided between all workers, so the number of workers does not matter here.

You can move your ship on the island edge, and it will be considered moving in the sea.

Now you have a sea map, and you have to decide what is the minimum cost for your trip.

Your starting point is (xStart, yStart), and the end point is (xEnd, yEnd), both points will be different.

The island will be a convex polygon and there will be no more than 2 polygon points on the same line, also the starting and the end points won't be inside or on the boundary of the island. The points for the polygon will be given in the anti-clockwise order.

Input

The first line contains 4 integers, xStart, yStart, xEnd and yEnd ( - 100 ≤ xStart, yStart, xEnd, yEnd ≤ 100). The second line contains an integer n, which is the number of points in the polygon (3 ≤ n ≤ 30), followed by a line containing n pairs of integers x and y, which are the coordinates of the points ( - 100 ≤ x, y ≤ 100), the polygon points will be distinct.

Output

Print one line which contains the minimum possible cost. The absolute or relative error in the answer should not exceed 10 - 6.

Examples

Input

1 7 6 7
4
4 2 4 12 3 12 3 2


Output

6.000000000


Input

-1 0 2 0
4
0 0 1 0 1 1 0 1


Output

3.000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya likes everything infinite. Now he is studying the properties of a sequence s, such that its first element is equal to a (s_1 = a), and the difference between any two neighbouring elements is equal to c (s_{i} - s_{i} - 1 = c). In particular, Vasya wonders if his favourite integer b appears in this sequence, that is, there exists a positive integer i, such that s_{i} = b. Of course, you are the person he asks for a help.


-----Input-----

The first line of the input contain three integers a, b and c ( - 10^9 ≤ a, b, c ≤ 10^9) — the first element of the sequence, Vasya's favorite number and the difference between any two neighbouring elements of the sequence, respectively.


-----Output-----

If b appears in the sequence s print "YES" (without quotes), otherwise print "NO" (without quotes).


-----Examples-----
Input
1 7 3

Output
YES

Input
10 10 0

Output
YES

Input
1 -4 5

Output
NO

Input
0 60 50

Output
NO



-----Note-----

In the first sample, the sequence starts from integers 1, 4, 7, so 7 is its element.

In the second sample, the favorite integer of Vasya is equal to the first element of the sequence.

In the third sample all elements of the sequence are greater than Vasya's favorite integer.

In the fourth sample, the sequence starts from 0, 50, 100, and all the following elements are greater than Vasya's favorite integer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.
The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.
If no land or water exists in the grid, return -1.
 
Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

 
Note:

1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1

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