vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Error Correct System

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ford Prefect got a job as a web developer for a small company that makes towels. His current work task is to create a search engine for the website of the company. During the development process, he needs to write a subroutine for comparing strings *S* and *T* of equal length to be "similar". After a brief search on the Internet, he learned about the Hamming distance between two strings *S* and *T* of the same length, which is defined as the number of positions in which *S* and *T* have different characters. For example, the Hamming distance between words "permanent" and "pergament" is two, as these words differ in the fourth and sixth letters.

Moreover, as he was searching for information, he also noticed that modern search engines have powerful mechanisms to correct errors in the request to improve the quality of search. Ford doesn't know much about human beings, so he assumed that the most common mistake in a request is swapping two arbitrary letters of the string (not necessarily adjacent). Now he wants to write a function that determines which two letters should be swapped in string *S*, so that the Hamming distance between a new string *S* and string *T* would be as small as possible, or otherwise, determine that such a replacement cannot reduce the distance between the strings.

Help him do this!

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=200<=000) — the length of strings *S* and *T*.

The second line contains string *S*.

The third line contains string *T*.

Each of the lines only contains lowercase Latin letters.

Output Specification:
In the first line, print number *x* — the minimum possible Hamming distance between strings *S* and *T* if you swap at most one pair of letters in *S*.

In the second line, either print the indexes *i* and *j* (1<=≤<=*i*,<=*j*<=≤<=*n*, *i*<=≠<=*j*), if reaching the minimum possible distance is possible by swapping letters on positions *i* and *j*, or print "-1 -1", if it is not necessary to swap characters.

If there are multiple possible answers, print any of them.

Demo Input:
['9\npergament\npermanent\n', '6\nwookie\ncookie\n', '4\npetr\negor\n', '6\ndouble\nbundle\n']

Demo Output:
['1\n4 6\n', '1\n-1 -1\n', '2\n1 2\n', '2\n4 1\n']

Note:
In the second test it is acceptable to print *i* = 2, *j* = 3.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an array of positive integers. While there are at least two equal elements, we will perform the following operation. We choose the smallest value $x$ that occurs in the array $2$ or more times. Take the first two occurrences of $x$ in this array (the two leftmost occurrences). Remove the left of these two occurrences, and the right one is replaced by the sum of this two values (that is, $2 \cdot x$).

Determine how the array will look after described operations are performed.

For example, consider the given array looks like $[3, 4, 1, 2, 2, 1, 1]$. It will be changed in the following way: $[3, 4, 1, 2, 2, 1, 1]~\rightarrow~[3, 4, 2, 2, 2, 1]~\rightarrow~[3, 4, 4, 2, 1]~\rightarrow~[3, 8, 2, 1]$.

If the given array is look like $[1, 1, 3, 1, 1]$ it will be changed in the following way: $[1, 1, 3, 1, 1]~\rightarrow~[2, 3, 1, 1]~\rightarrow~[2, 3, 2]~\rightarrow~[3, 4]$.

Input Specification:
The first line contains a single integer $n$ ($2 \le n \le 150\,000$) — the number of elements in the array.

The second line contains a sequence from $n$ elements $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{9}$) — the elements of the array.

Output Specification:
In the first line print an integer $k$ — the number of elements in the array after all the performed operations. In the second line print $k$ integers — the elements of the array after all the performed operations.

Demo Input:
['7\n3 4 1 2 2 1 1\n', '5\n1 1 3 1 1\n', '5\n10 40 20 50 30\n']

Demo Output:
['4\n3 8 2 1 \n', '2\n3 4 \n', '5\n10 40 20 50 30 \n']

Note:
The first two examples were considered in the statement.

In the third example all integers in the given array are distinct, so it will not change.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string that is made up of words separated by spaces. Your task is to find the word with highest frequency, i.e. it appears maximum times in the sentence. If multiple words have maximum frequency, then print the word that occurs first in the sentence.
Example 1:
 
Input : S = "the devil in the sky"
Output : the 2
Explanation:
The frequency of the is 2, so we return "the" and
its frequency "2" i.e., "the 2" 
Example 2:
Input : S = "this is not right"
Output : this 1
Explanation:
Every word has the frequency of "1", so we return 
"this 1" as this occurs first in the sentence. 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function maximumFrequency() that takes a string S and return the answer as a string. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ |S| ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Buy Low Sell High

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You can perfectly predict the price of a certain stock for the next *N* days. You would like to profit on this knowledge, but only want to transact one share of stock per day. That is, each day you will either buy one share, sell one share, or do nothing. Initially you own zero shares, and you cannot sell shares when you don't own any. At the end of the *N* days you would like to again own zero shares, but want to have as much money as possible.

Input Specification:
Input begins with an integer *N* (2<=≤<=*N*<=≤<=3·105), the number of days.

Following this is a line with exactly *N* integers *p*1,<=*p*2,<=...,<=*p**N* (1<=≤<=*p**i*<=≤<=106). The price of one share of stock on the *i*-th day is given by *p**i*.

Output Specification:
Print the maximum amount of money you can end up with at the end of *N* days.

Demo Input:
['9\n10 5 4 7 9 12 6 2 10\n', '20\n3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4\n']

Demo Output:
['20\n', '41\n']

Note:
In the first example, buy a share at 5, buy another at 4, sell one at 9 and another at 12. Then buy at 2 and sell at 10. The total profit is  - 5 - 4 + 9 + 12 - 2 + 10 = 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dilpreet wants to paint his dog's home that has n boards with different lengths. The length of i^{th }board is given by arr[i] where arr[] is an array of n integers. He hired k painters for this work and each painter takes 1 unit time to paint 1 unit of the board. 
The problem is to find the minimum time to get this job done if all painters start together with the constraint that any painter will only paint continuous boards, say boards numbered {2,3,4} or only board {1} or nothing but not boards {2,4,5}.
Example 1:
Input:
n = 5
k = 3
arr[] = {5,10,30,20,15}
Output: 35
Explanation: The most optimal way will be:
Painter 1 allocation : {5,10}
Painter 2 allocation : {30}
Painter 3 allocation : {20,15}
Job will be done when all painters finish
i.e. at time = max(5+10, 30, 20+15) = 35
Example 2:
Input:
n = 4
k = 2
arr[] = {10,20,30,40}
Output: 60
Explanation: The most optimal way to paint:
Painter 1 allocation : {10,20,30}
Painter 2 allocation : {40}
Job will be complete at time = 60
Your task:
Your task is to complete the function minTime() which takes the integers n and k and the array arr[] as input and returns the minimum time required to paint all partitions.
Expected Time Complexity: O(n log m) , m = sum of all boards' length
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ k ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Optimistan is a strange country. It is situated on an island with a huge desert in the middle, so most people live in port towns along the coast. As the name suggests, people of Optimistan (also called Optimists) like to optimise everything, so they only built roads necessary to connect all port towns together and not a single extra road. That means that there is only one way to get from one port town to another without visiting the same place twice.

The government installed multi-directional distance signs in $1$-kilometre intervals on one side of the road, to provide important information to drivers. Thus whenever you go from one port town to another, you pass the first sign at the port town and then one each kilometre. Every distance sign contains the shortest distances to all port towns, each written on a separate small sign directed towards the goal town.

The signs also serve another important function: to guide drivers on intersections. This means that distance of each intersection from every port town is an integer number of kilometres.

You bought a tourist guide of Optimistan which does not have a map of the country, but it contains a huge table with the shortest distances between all pairs of port towns. You quickly calculated the average shortest distance between all pairs of port towns, but then you started wondering: if the signs also contained shortest distances to all other signs, what would be the average number written on a sign? Could this be calculated just from the distance table in the tourist guide?

-----Input-----
The input consists of:
 - one line with an integer $n$ ($2 \le n \le 500$), the number of ports;
 - $n-1$ lines, the $i$th of which contains $n-i$ integers. The $j$th integer on the $i$th line denotes the distance between port $i$ and port $i+j$ in kilometres. Each distance is between $1$ and $10^6$ (inclusive).

You can assume that the distances correspond to a road network in which there is exactly one path between two port towns that does not visit the same place twice. All roads can be used in both directions.

-----Output-----
Output one line with the average distances in kilometres between all pairs of distance signs in Optimistan. Your answer should have an absolute or relative error of at most $10^{-9}$.

If it is impossible to determine the exact average of distances between all pairs of distance signs in Optimistan, output “impossible”.

-----Examples-----
Sample Input:
3
4 4
2
Sample Output:
2.13333333333333

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a sequence of n integers *a*1,<=*a*2,<=...,<=*a**n*. 

Determine a real number *x* such that the weakness of the sequence *a*1<=-<=*x*,<=*a*2<=-<=*x*,<=...,<=*a**n*<=-<=*x* is as small as possible.

The weakness of a sequence is defined as the maximum value of the poorness over all segments (contiguous subsequences) of a sequence.

The poorness of a segment is defined as the absolute value of sum of the elements of segment.

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=200<=000), the length of a sequence.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (|*a**i*|<=≤<=10<=000).

Output Specification:
Output a real number denoting the minimum possible weakness of *a*1<=-<=*x*,<=*a*2<=-<=*x*,<=...,<=*a**n*<=-<=*x*. Your answer will be considered correct if its relative or absolute error doesn't exceed 10<=-<=6.

Demo Input:
['3\n1 2 3\n', '4\n1 2 3 4\n', '10\n1 10 2 9 3 8 4 7 5 6\n']

Demo Output:
['1.000000000000000\n', '2.000000000000000\n', '4.500000000000000\n']

Note:
For the first case, the optimal value of *x* is 2 so the sequence becomes  - 1, 0, 1 and the max poorness occurs at the segment "-1" or segment "1". The poorness value (answer) equals to 1 in this case. 

For the second sample the optimal value of *x* is 2.5 so the sequence becomes  - 1.5,  - 0.5, 0.5, 1.5 and the max poorness occurs on segment "-1.5 -0.5" or "0.5 1.5". The poorness value (answer) equals to 2 in this case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's assume that we have a sequence of doubles a1, a2, ..., a|a| and a double variable x. You are allowed to perform the following two-staged operation:

  1. choose an index of the sequence element i (1 ≤ i ≤ |a|); 
  2. consecutively perform assignments: <image>. 



Let's use function g(a, x) to represent the largest value that can be obtained from variable x, using the described operation any number of times and sequence a.

Sereja has sequence b1, b2, ..., b|b|. Help Sereja calculate sum: <image>. Record [bi, bi + 1, ..., bj] represents a sequence containing the elements in brackets in the given order. To avoid problems with precision, please, print the required sum divided by |b|2.

Input

The first line contains integer |b| (1 ≤ |b| ≤ 3·105) — the length of sequence b. The second line contains |b| integers b1, b2, ..., b|b| (1 ≤ bi ≤ 105).

Output

In a single line print a real number — the required sum divided by |b|2. Your answer will be considered correct if its absolute or relative error won't exceed 10 - 6.

Examples

Input

5
1 2 3 4 1


Output

1.238750000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer, return its corresponding column title as appear in an Excel sheet.
Excel columns has a pattern like A, B, C, … ,Z, AA, AB, AC,…. ,AZ, BA, BB, … ZZ, AAA, AAB ….. etc. In other words, column 1 is named as “A”, column 2 as “B”, column 27 as “AA” and so on.
Example 1:
Input:
N = 28
Output: AB
Explanation: 1 to 26 are A to Z.
Then, 27 is AA and 28 = AB.
Ã¢â¬â¹Example 2:
Input: 
N = 13
Output: M
Explanation: M is the 13th character of
alphabet.
Your Task:
You don't need to read input or print anything. Your task is to complete the function colName() which takes the column number N as input and returns the column name represented as a string.
 
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 4294967295

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n integers a1, a2, ..., an.

A sequence of integers x1, x2, ..., xk is called a "xor-sequence" if for every 1 ≤ i ≤ k - 1 the number of ones in the binary representation of the number xi <image> xi + 1's is a multiple of 3 and <image> for all 1 ≤ i ≤ k. The symbol <image> is used for the binary exclusive or operation.

How many "xor-sequences" of length k exist? Output the answer modulo 109 + 7.

Note if a = [1, 1] and k = 1 then the answer is 2, because you should consider the ones from a as different.

Input

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1018) — the number of given integers and the length of the "xor-sequences".

The second line contains n integers ai (0 ≤ ai ≤ 1018).

Output

Print the only integer c — the number of "xor-sequences" of length k modulo 109 + 7.

Examples

Input

5 2
15 1 2 4 8


Output

13


Input

5 1
15 1 2 4 8


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dawid has four bags of candies. The $i$-th of them contains $a_i$ candies. Also, Dawid has two friends. He wants to give each bag to one of his two friends. Is it possible to distribute the bags in such a way that each friend receives the same amount of candies in total?

Note, that you can't keep bags for yourself or throw them away, each bag should be given to one of the friends.


-----Input-----

The only line contains four integers $a_1$, $a_2$, $a_3$ and $a_4$ ($1 \leq a_i \leq 100$) — the numbers of candies in each bag.


-----Output-----

Output YES if it's possible to give the bags to Dawid's friends so that both friends receive the same amount of candies, or NO otherwise. Each character can be printed in any case (either uppercase or lowercase).


-----Examples-----
Input
1 7 11 5

Output
YES

Input
7 3 2 5

Output
NO



-----Note-----

In the first sample test, Dawid can give the first and the third bag to the first friend, and the second and the fourth bag to the second friend. This way, each friend will receive $12$ candies.

In the second sample test, it's impossible to distribute the bags.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Primes or Palindromes?

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Rikhail Mubinchik believes that the current definition of prime numbers is obsolete as they are too complex and unpredictable. A palindromic number is another matter. It is aesthetically pleasing, and it has a number of remarkable properties. Help Rikhail to convince the scientific community in this!

Let us remind you that a number is called prime if it is integer larger than one, and is not divisible by any positive integer other than itself and one.

Rikhail calls a number a palindromic if it is integer, positive, and its decimal representation without leading zeros is a palindrome, i.e. reads the same from left to right and right to left.

One problem with prime numbers is that there are too many of them. Let's introduce the following notation: π(*n*) — the number of primes no larger than *n*, *rub*(*n*) — the number of palindromic numbers no larger than *n*. Rikhail wants to prove that there are a lot more primes than palindromic ones.

He asked you to solve the following problem: for a given value of the coefficient *A* find the maximum *n*, such that π(*n*)<=≤<=*A*·*rub*(*n*).

Input Specification:
The input consists of two positive integers *p*, *q*, the numerator and denominator of the fraction that is the value of *A* (, ).

Output Specification:
If such maximum number exists, then print it. Otherwise, print "Palindromic tree is better than splay tree" (without the quotes).

Demo Input:
['1 1\n', '1 42\n', '6 4\n']

Demo Output:
['40\n', '1\n', '172\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).
The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.
You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.
You now have to take Q practical tests of your ability as a magical girl.
The i-th test will be conducted as follows:
 - Initially, a piece is placed on the square where the integer L_i is written.
 - Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.
 - Here, it is guaranteed that R_i-L_i is a multiple of D.
For each test, find the sum of magic points consumed during that test.

-----Constraints-----
 - 1 \leq H,W \leq 300
 - 1 \leq D \leq H×W
 - 1 \leq A_{i,j} \leq H×W
 - A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))
 - 1 \leq Q \leq 10^5
 - 1 \leq L_i \leq R_i \leq H×W
 - (R_i-L_i) is a multiple of D.

-----Input-----
Input is given from Standard Input in the following format:
H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

-----Output-----
For each test, print the sum of magic points consumed during that test.
Output should be in the order the tests are conducted.

-----Sample Input-----
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8

-----Sample Output-----
5

 - 4 is written in Square (1,2).
 - 6 is written in Square (3,3).
 - 8 is written in Square (3,1).
Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.
 
Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:
Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

Example 3:
Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3

Example 4:
Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2

 
Constraints:

1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Kyoya and Colored Balls

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kyoya Ootori has a bag with *n* colored balls that are colored with *k* different colors. The colors are labeled from 1 to *k*. Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of color *i* before drawing the last ball of color *i*<=+<=1 for all *i* from 1 to *k*<=-<=1. Now he wonders how many different ways this can happen.

Input Specification:
The first line of input will have one integer *k* (1<=≤<=*k*<=≤<=1000) the number of colors.

Then, *k* lines will follow. The *i*-th line will contain *c**i*, the number of balls of the *i*-th color (1<=≤<=*c**i*<=≤<=1000).

The total number of balls doesn't exceed 1000.

Output Specification:
A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo 1<=000<=000<=007.

Demo Input:
['3\n2\n2\n1\n', '4\n1\n2\n3\n4\n']

Demo Output:
['3\n', '1680\n']

Note:
In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are:

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