vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
One day maths teacher gave the following task for the students, only upon completion students will be taken out for a school fun trip.
First you are a given a list of n numbers and q queries. For each query you are given two indices x and y , you have to report the between the maximum number and minimum number whose indices lie within x and y (both inclusive)

 

Input
First line of input has two integers n and q , denoting the size of list and number of queries
Next line consists of n spaced integers denoting the elements of the array
Next q lines consists of two integer x and y , denoting the leftmost and rightmost indices of the query

Note : List is 0-indexed 


Output
For each query , print the answer in a new line.

Constraints
0< n,q < 100000
0< element of list < 1000000000
0 < x,y < n

Example
Input:
5 2
1 2 3 4 5
1 2
4 4


Output:
1
0


Explanation
Example case .

First query maximum number in given range is 3 and minimum number is 2 so difference 1

Second Query maximum and mimimum both are 5 ,difference is 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, S.The string can contain small case English letters or '?'. You can replace '?' with any small English letter. Now if it is possible to make the string S a palindrome after replacing all '?' then find the palindromic string with a minimum ascii sum of the absolute difference of adjacent characters. Otherwise, return -1.
Example 1:
Input: S = a???c??c????
Output: 4
Explanation:
We can see that we can make the string
palindrome. Now to get minimum ascii sum we should
replace all the '?' between 'a' and 'c' with
'b' and all the '?' between two 'c' with 'c'.
So after replacing all the '?' the string: 
abbbccccbbba.
The sum of differences of adjacent characters is 4.   
Example 2:
Input: S = a???c??c???c
Output: -1
Explanation:
It is not possible to make the string palindrome.
Your Task:
You don't need to read input or print anything. Your task is to complete the function minimumSum() which takes a string S input parameter and returns an integer denoting the sum of differences of adjacent characters. If it is not possible to make string palindrome, return -1. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= |S| <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Converting a normal (12-hour) time like "8:30 am" or "8:30 pm" to 24-hour time (like "0830" or "2030") sounds easy enough, right?  Well, let's see if you can do it!

You will have to define a function named "to24hourtime", and you will be given an hour (always in the range of 1 to 12, inclusive), a minute (always in the range of 0 to 59, inclusive), and a period (either "am" or "pm") as input.

Your task is to return a four-digit string that encodes that time in 24-hour time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation of integers from 1 to n. Exactly once you apply the following operation to this permutation: pick a random segment and shuffle its elements. Formally:

  1. Pick a random segment (continuous subsequence) from l to r. All <image> segments are equiprobable. 
  2. Let k = r - l + 1, i.e. the length of the chosen segment. Pick a random permutation of integers from 1 to k, p1, p2, ..., pk. All k! permutation are equiprobable. 
  3. This permutation is applied to elements of the chosen segment, i.e. permutation a1, a2, ..., al - 1, al, al + 1, ..., ar - 1, ar, ar + 1, ..., an is transformed to a1, a2, ..., al - 1, al - 1 + p1, al - 1 + p2, ..., al - 1 + pk - 1, al - 1 + pk, ar + 1, ..., an. 



Inversion if a pair of elements (not necessary neighbouring) with the wrong relative order. In other words, the number of inversion is equal to the number of pairs (i, j) such that i < j and ai > aj. Find the expected number of inversions after we apply exactly one operation mentioned above.

Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the length of the permutation.

The second line contains n distinct integers from 1 to n — elements of the permutation.

Output

Print one real value — the expected number of inversions. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 9. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Example

Input

3
2 3 1


Output

1.916666666666666666666666666667

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
John Doe wants to transport his possessions from one bank of Lake Michigan to the other. His possessions consist of $W$ wolves, $S$ sheep, and $C$ cabbages. The transportation will be carried out using a boat that can hold up to $K$ of these items at the same time. During each step, John can take some items from one bank and transfer them to the other bank. Unfortunately, when left unsupervised, wolves will eat sheep and sheep will eat cabbages (but wolves don’t eat cabbages). John doesn’t want to lose his possessions, so he has to devise a scheme such that this doesn’t happen. With John present, any combination of items is allowed (both on the bank and in the boat). This is also true during the loading process. Since John isn’t very good at solving problems like this, he asks you to help him.

-----Input-----
Input contains a single line with four integers: $W$, $S$, $C$, $K$. The input satisfies the following constraints:\[ 0 \leq W, S, C, K \leq 10^6, \]\[ 1 \leq max(W, S, C). \]

-----Output-----
If it’s possible to perform the transportation without the loss of items, print YES, otherwise print NO.

-----Examples-----
Sample Input:
1 1 1 1
Sample Output:
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string text, you want to use the characters of text to form as many instances of the word "balloon" as possible.
You can use each character in text at most once. Return the maximum number of instances that can be formed.
 
Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:
Input: text = "leetcode"
Output: 0

 
Constraints:

1 <= text.length <= 10^4
text consists of lower case English letters only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a directed graph G with N vertices and M edges.

The vertices are numbered 1 to N, and the i-th edge is directed from Vertex A_i to Vertex B_i.

It is guaranteed that the graph contains no self-loops or multiple edges.
Determine whether there exists an induced subgraph (see Notes) of G such that the in-degree and out-degree of every vertex are both 1. If the answer is yes, show one such subgraph.

Here the null graph is not considered as a subgraph.

-----Notes-----
For a directed graph G = (V, E), we call a directed graph G' = (V', E') satisfying the following conditions an induced subgraph of G:
 - V' is a (non-empty) subset of V.
 - E' is the set of all the edges in E that have both endpoints in V'.

-----Constraints-----
 - 1 \leq N \leq 1000
 - 0 \leq M \leq 2000
 - 1 \leq A_i,B_i \leq N
 - A_i \neq B_i
 - All pairs (A_i, B_i) are distinct.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 B_1
A_2 B_2
:
A_M B_M

-----Output-----
If there is no induced subgraph of G that satisfies the condition, print -1.
Otherwise, print an induced subgraph of G that satisfies the condition, in the following format:
K
v_1
v_2
:
v_K

This represents the induced subgraph of G with K vertices whose vertex set is \{v_1, v_2, \ldots, v_K\}. (The order of v_1, v_2, \ldots, v_K does not matter.)
If there are multiple subgraphs of G that satisfy the condition, printing any of them is accepted.

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

-----Sample Output-----
3
1
2
4

The induced subgraph of G whose vertex set is \{1, 2, 4\} has the edge set \{(1, 2), (2, 4), (4, 1)\}. The in-degree and out-degree of every vertex in this graph are both 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little town Nsk consists of n junctions connected by m bidirectional roads. Each road connects two distinct junctions and no two roads connect the same pair of junctions. It is possible to get from any junction to any other junction by these roads. The distance between two junctions is equal to the minimum possible number of roads on a path between them.

In order to improve the transportation system, the city council asks mayor to build one new road. The problem is that the mayor has just bought a wonderful new car and he really enjoys a ride from his home, located near junction s to work located near junction t. Thus, he wants to build a new road in such a way that the distance between these two junctions won't decrease. 

You are assigned a task to compute the number of pairs of junctions that are not connected by the road, such that if the new road between these two junctions is built the distance between s and t won't decrease.


-----Input-----

The firt line of the input contains integers n, m, s and t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) — the number of junctions and the number of roads in Nsk, as well as the indices of junctions where mayors home and work are located respectively. The i-th of the following m lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}), meaning that this road connects junctions u_{i} and v_{i} directly. It is guaranteed that there is a path between any two junctions and no two roads connect the same pair of junctions.


-----Output-----

Print one integer — the number of pairs of junctions not connected by a direct road, such that building a road between these two junctions won't decrease the distance between junctions s and t.


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

Output
0

Input
5 4 3 5
1 2
2 3
3 4
4 5

Output
5

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

Output
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef wants to rent a car to travel to his restaurant which is N kilometers away. He can either rent a petrol car or a diesel car.

One litre of petrol costs X rupees and one litre of diesel costs Y rupees. Chef can travel A kilometers with one litre of petrol and B kilometers with one litre of diesel.

Chef can buy petrol and diesel in any amount, not necessarily integer. For example, if X = 95, Chef can buy half a litre of petrol by paying 95/2 = 47.5 rupees.

Which car should the chef rent in order to minimize the cost of his travel?

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains 5 space-separated integers, N, X, Y, A, and B - distance that chef needs to travel, the per litre prices of petrol and diesel and the distance chef can travel using one litre of petrol and diesel respectively.

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

For each test case, output on a new line PETROL if the cost of travel is less using petrol car, DIESEL if the cost of travel is less using diesel car or ANY if cost of travel is same in both the cases.

You may print each character of the string in either uppercase or lowercase (for example, the strings PETrol, petrol, Petrol, and PETROL will all be treated as identical).

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

$1 ≤ T ≤ 100$
$1 ≤ N,x,y,a,b ≤ 100$

----- Sample Input 1 ------ 
4
20 10 8 2 4
50 12 12 4 3
40 3 15 8 40
21 9 9 2 9

----- Sample Output 1 ------ 
DIESEL
PETROL
ANY
DIESEL

----- explanation 1 ------ 
Test case $1$: The cost of travelling by the petrol car will be $100$ rupees while that of using the diesel car will be $40$ rupees. Hence, diesel car is better.

Test case $2$: The cost of travelling by the petrol car will be $150$ rupees while that of using the diesel car will be $200$ rupees. Hence, petrol car is better.

Test case $3$: The cost of travel for petrol and diesel car will be $15$ rupees.

Test case $4$: The cost of travelling by the petrol car will be $94.5$ rupees while that of using the diesel car will be $21$ rupees. Hence, diesel car is better.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $A$ and $B$, calculate the number of pairs $(a, b)$ such that $1 \le a \le A$, $1 \le b \le B$, and the equation $a \cdot b + a + b = conc(a, b)$ is true; $conc(a, b)$ is the concatenation of $a$ and $b$ (for example, $conc(12, 23) = 1223$, $conc(100, 11) = 10011$). $a$ and $b$ should not contain leading zeroes.


-----Input-----

The first line contains $t$ ($1 \le t \le 100$) — the number of test cases.

Each test case contains two integers $A$ and $B$ $(1 \le A, B \le 10^9)$.


-----Output-----

Print one integer — the number of pairs $(a, b)$ such that $1 \le a \le A$, $1 \le b \le B$, and the equation $a \cdot b + a + b = conc(a, b)$ is true.


-----Example-----
Input
3
1 11
4 2
191 31415926

Output
1
0
1337



-----Note-----

There is only one suitable pair in the first test case: $a = 1$, $b = 9$ ($1 + 9 + 1 \cdot 9 = 19$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Petr and a calendar

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petr wants to make a calendar for current month. For this purpose he draws a table in which columns correspond to weeks (a week is seven consequent days from Monday to Sunday), rows correspond to weekdays, and cells contain dates. For example, a calendar for January 2017 should look like on the picture:

Petr wants to know how many columns his table should have given the month and the weekday of the first date of that month? Assume that the year is non-leap.

Input Specification:
The only line contain two integers *m* and *d* (1<=≤<=*m*<=≤<=12, 1<=≤<=*d*<=≤<=7) — the number of month (January is the first month, December is the twelfth) and the weekday of the first date of this month (1 is Monday, 7 is Sunday).

Output Specification:
Print single integer: the number of columns the table should have.

Demo Input:
['1 7\n', '1 1\n', '11 6\n']

Demo Output:
['6\n', '5\n', '5\n']

Note:
The first example corresponds to the January 2017 shown on the picture in the statements.

In the second example 1-st January is Monday, so the whole month fits into 5 columns.

In the third example 1-st November is Saturday and 5 columns is enough.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera has 2·n cubes, each cube contains an integer from 10 to 99. He arbitrarily chooses n cubes and puts them in the first heap. The remaining cubes form the second heap. 

Valera decided to play with cubes. During the game he takes a cube from the first heap and writes down the number it has. Then he takes a cube from the second heap and write out its two digits near two digits he had written (to the right of them). In the end he obtained a single fourdigit integer — the first two digits of it is written on the cube from the first heap, and the second two digits of it is written on the second cube from the second heap.

Valera knows arithmetic very well. So, he can easily count the number of distinct fourdigit numbers he can get in the game. The other question is: how to split cubes into two heaps so that this number (the number of distinct fourdigit integers Valera can get) will be as large as possible?

Input

The first line contains integer n (1 ≤ n ≤ 100). The second line contains 2·n space-separated integers ai (10 ≤ ai ≤ 99), denoting the numbers on the cubes.

Output

In the first line print a single number — the maximum possible number of distinct four-digit numbers Valera can obtain. In the second line print 2·n numbers bi (1 ≤ bi ≤ 2). The numbers mean: the i-th cube belongs to the bi-th heap in your division.

If there are multiple optimal ways to split the cubes into the heaps, print any of them.

Examples

Input

1
10 99


Output

1
2 1 


Input

2
13 24 13 45


Output

4
1 2 2 1 

Note

In the first test case Valera can put the first cube in the first heap, and second cube — in second heap. In this case he obtain number 1099. If he put the second cube in the first heap, and the first cube in the second heap, then he can obtain number 9910. In both cases the maximum number of distinct integers is equal to one.

In the second test case Valera can obtain numbers 1313, 1345, 2413, 2445. Note, that if he put the first and the third cubes in the first heap, he can obtain only two numbers 1324 and 1345.

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

You are given a dictionary/hash/object containing some languages and your test results in the given languages. Return the list of languages where your test score is at least `60`, in descending order of the results.

Note: the scores will always be unique (so no duplicate values)

## Examples

```python
{"Java": 10, "Ruby": 80, "Python": 65}    -->  ["Ruby", "Python"]
{"Hindi": 60, "Dutch" : 93, "Greek": 71}  -->  ["Dutch", "Greek", "Hindi"]
{"C++": 50, "ASM": 10, "Haskell": 20}     -->  []
```
---

## My other katas

If you enjoyed this kata then please try [my other katas](https://www.codewars.com/collections/katas-created-by-anter69)! :-)

### _Translations are welcome!_

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ever wonder what will happen when you meet a person who uses a different base system to talk about numbers? For example, when you hear someone saying this mysterious number 1010110001 (which is in binary), can you quickly convert it to its decimal form, 689?

In Harkerland, everyone uses the octal numeral system (base $8$) when talking about numbers. Therefore, new immigrants often have difficulties parsing numbers quickly. One of them is Alex. Alex used to live in a place where the hexadecimal numeral system (base $16$) is adopted. In order to adapt to the Harkerland lifestyle as soon as possible, he trains hard to perform fast octal-to-hexadecimal conversion. Before Alex’s training finishes, he is going to rely on a program for the base conversion. Help Alex write such a program.

Use capital letters A, B, $\dots $, F to represent the values $10, 11, \ldots , 15$ in hexadecimal.

-----Input-----
The only line of input consists of a non-negative integer, written in base $8$. The given integer will have no leading zeroes and will be strictly smaller than $8^{200000}$.

-----Output-----
Output the same integer, written in base $16$. The output must not include any extra leading zeroes.

-----Explanation for sample data-----
For Sample Input 1, $4444_8 = 2340_{10} = 924_{16}$.

-----Examples-----
Sample Input 1:
4444
Sample Output 1:
924

Sample Input 2:
20
Sample Output 2:
10

Sample Input 3:
3211
Sample Output 3:
689

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
Jack is working on his jumping skills recently. Currently he's located at point zero of the number line. He would like to get to the point *x*. In order to train, he has decided that he'll first jump by only one unit, and each subsequent jump will be exactly one longer than the previous one. He can go either left or right with each jump. He wonders how many jumps he needs to reach *x*.

Input Specification:
The input data consists of only one integer *x* (<=-<=109<=≤<=*x*<=≤<=109).

Output Specification:
Output the minimal number of jumps that Jack requires to reach *x*.

Demo Input:
['2\n', '6\n', '0\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: New Year Book Reading

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
New Year is coming, and Jaehyun decided to read many books during 2015, unlike this year. He has *n* books numbered by integers from 1 to *n*. The weight of the *i*-th (1<=≤<=*i*<=≤<=*n*) book is *w**i*.

As Jaehyun's house is not large enough to have a bookshelf, he keeps the *n* books by stacking them vertically. When he wants to read a certain book *x*, he follows the steps described below.
 1.  He lifts all the books above book *x*. 1.  He pushes book *x* out of the stack. 1.  He puts down the lifted books without changing their order. 1.  After reading book *x*, he puts book *x* on the top of the stack. 
 

He decided to read books for *m* days. In the *j*-th (1<=≤<=*j*<=≤<=*m*) day, he will read the book that is numbered with integer *b**j* (1<=≤<=*b**j*<=≤<=*n*). To read the book, he has to use the process described in the paragraph above. It is possible that he decides to re-read the same book several times.

After making this plan, he realized that the total weight of books he should lift during *m* days would be too heavy. So, he decided to change the order of the stacked books before the New Year comes, and minimize the total weight. You may assume that books can be stacked in any possible order. Note that book that he is going to read on certain step isn't considered as lifted on that step. Can you help him?

Input Specification:
The first line contains two space-separated integers *n* (2<=≤<=*n*<=≤<=500) and *m* (1<=≤<=*m*<=≤<=1000) — the number of books, and the number of days for which Jaehyun would read books.

The second line contains *n* space-separated integers *w*1,<=*w*2,<=...,<=*w**n* (1<=≤<=*w**i*<=≤<=100) — the weight of each book.

The third line contains *m* space separated integers *b*1,<=*b*2,<=...,<=*b**m* (1<=≤<=*b**j*<=≤<=*n*) — the order of books that he would read. Note that he can read the same book more than once.

Output Specification:
Print the minimum total weight of books he should lift, which can be achieved by rearranging the order of stacked books.

Demo Input:
['3 5\n1 2 3\n1 3 2 3 1\n']

Demo Output:
['12\n']

Note:
Here's a picture depicting the example. Each vertical column presents the stacked books.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A Hackerrank number is a magic number that can be used to get sudo permissions on the site. We are going to generate a hackerrank number from two integers A & B. Each number has two parts to it - the left (L) & the right side (R).  

For eg: for the number 100101, 

L could be 100 & R could be 101 (or) 
L could be 1 and R could be 00101 and so on.. 

How to generate a hackerrank number?

Let x & y be integers such that,

(1 <= x <= A & 1 <= y <= B) 

Generate the left part of any hackerrank number (L) by multiplying x and y (i.e) x*y 

and the right part of any hackerrank number (R) by bitwise xor-ing x and y (i.e) x^y

Add leading zeros to R to make length(R) = length(B) + 1. Concatenate both L & R to form the hackerrank number.

Can you find the sum of all possible hackerrank numbers generated by this rule?

Input format

Each input contains 2 integers A and B separated by a space. 

Constraints

1 <= A <= 30 

1 <= B <= 10^{8}

Output format

Print the sum of all possible numbers that satisfy the above mentioned property. 

Sample Input

2 4

Sample Output

14502

The left value can be one of  {1 * 1, 1 * 2, 1 * 3, 1 * 4, 2 * 1, 2 * 2, 2 * 3, 2 * 4} 

which is {1,2,3,4,2,4,6,8} 

and the distinct values are {1, 2, 3, 4, 6, 8}

The right value can be one of {1^1,1^2,1^3,1^4,2^1,2^2,2^3,2^4} 

which is {0, 3, 2, 5, 3, 0, 1, 6} 
and the distinct values are {0, 1, 2, 3, 5, 6} 

All the possible value are

{
    100, 101, 102, 103, 105, 106,
    200, 201, 202, 203, 205, 206,
    300, 301, 302, 303, 305, 306,
    400, 401, 402, 403, 405, 406,
    600, 601, 602, 603, 605, 606,
    800, 801, 802, 803, 805, 806 
}

S = all the sum of the above = 14502.

Note: Any number can only be added once.

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