vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A farmer has $n$ goats. Coincidentally, he also has $n$ fixed posts in a field where he wants the goats to graze. He wants to tie each goat to a post with a length of rope. He wants to give each goat as much leeway as possible – but, goat ropes are notorious for getting tangled, so he cannot allow any goat to be able to wander into another goat’s territory. What is the maximum amount of rope he could possibly use?

-----Input-----
There will be a single test case in the input. This test case will begin with an integer $n$ ($2 \le n \le 50$), indicating the number of posts in the field. On each of the next $n$ lines will be a pair of integers, $x$ and $y$ ($0 \le x \le 1000$, $0 \le y \le 1000$) which indicate the cartesian coordinates (in meters) of that post in the field. No two posts will be in the same position. You may assume that the field is large enough that the goats will never encounter its border.

-----Output-----
Output a single floating point number, which indicates the maximum amount of rope that the farmer could possibly use, in meters. Output this value with exactly two decimal places, rounded to the nearest value.

-----Examples-----
Sample Input:
2
250 250
250 750
Sample Output:
500.00

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pasha has recently bought a new phone jPager and started adding his friends' phone numbers there. Each phone number consists of exactly *n* digits.

Also Pasha has a number *k* and two sequences of length *n*<=/<=*k* (*n* is divisible by *k*) *a*1,<=*a*2,<=...,<=*a**n*<=/<=*k* and *b*1,<=*b*2,<=...,<=*b**n*<=/<=*k*. Let's split the phone number into blocks of length *k*. The first block will be formed by digits from the phone number that are on positions 1, 2,..., *k*, the second block will be formed by digits from the phone number that are on positions *k*<=+<=1, *k*<=+<=2, ..., 2·*k* and so on. Pasha considers a phone number good, if the *i*-th block doesn't start from the digit *b**i* and is divisible by *a**i* if represented as an integer. 

To represent the block of length *k* as an integer, let's write it out as a sequence *c*1, *c*2,...,*c**k*. Then the integer is calculated as the result of the expression *c*1·10*k*<=-<=1<=+<=*c*2·10*k*<=-<=2<=+<=...<=+<=*c**k*.

Pasha asks you to calculate the number of good phone numbers of length *n*, for the given *k*, *a**i* and *b**i*. As this number can be too big, print it modulo 109<=+<=7.

Input Specification:
The first line of the input contains two integers *n* and *k* (1<=≤<=*n*<=≤<=100<=000, 1<=≤<=*k*<=≤<=*min*(*n*,<=9)) — the length of all phone numbers and the length of each block, respectively. It is guaranteed that *n* is divisible by *k*.

The second line of the input contains *n*<=/<=*k* space-separated positive integers — sequence *a*1,<=*a*2,<=...,<=*a**n*<=/<=*k* (1<=≤<=*a**i*<=&lt;<=10*k*).

The third line of the input contains *n*<=/<=*k* space-separated positive integers — sequence *b*1,<=*b*2,<=...,<=*b**n*<=/<=*k* (0<=≤<=*b**i*<=≤<=9).

Output Specification:
Print a single integer — the number of good phone numbers of length *n* modulo 109<=+<=7.

Demo Input:
['6 2\n38 56 49\n7 3 4\n', '8 2\n1 22 3 44\n5 4 3 2\n']

Demo Output:
['8\n', '32400\n']

Note:
In the first test sample good phone numbers are: 000000, 000098, 005600, 005698, 380000, 380098, 385600, 385698.

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

Soundex is an interesting phonetic algorithm developed nearly 100 years ago for indexing names as they are pronounced in English. The goal is for homophones to be encoded to the same representation so that they can be matched despite minor differences in spelling.

Reference: https://en.wikipedia.org/wiki/Soundex



# Preface

I first read about Soundex over 30 years ago. At the time it seemed to me almost  like  A.I. that you could just type in somebody's name the way it sounded and there was still a pretty good chance it could match the correct person record. That was about the same year as the first "Terminator" movie so it was easy for me to put 2 and 2 together and conclude that Arnie must have had some kind of futuristic Soundex chip in his titanium skull helping him to locate ```Serah Coner```... or was it ```Sarh Connor```... or maybe ```Sayra Cunnarr```...

:-)



# Task

In this Kata you will encode strings using a Soundex variation called "American Soundex" using the following (case insensitive) steps:

* Save the first letter. Remove all occurrences of ```h``` and ```w``` except first letter.
* Replace all consonants (include the first letter) with digits as follows:
 * ```b```, ```f```, ```p```, ```v``` = 1
 * ```c```, ```g```, ```j```, ```k```, ```q```, ```s```, ```x```, ```z``` = 2
 * ```d```, ```t``` = 3
 * ```l``` = 4
 * ```m```, ```n``` = 5
 * ```r``` = 6
* Replace all adjacent same digits with one digit.
* Remove all occurrences of ```a```, ```e```, ```i```, ```o```, ```u```, ```y``` except first letter.
* If first symbol is a digit replace it with letter saved on step 1.
* Append 3 zeros if result contains less than 3 digits. Remove all except first letter and 3 digits after it

## Input

A space separated string of one or more names. E.g.

```Sarah Connor```

## Output

Space separated string of equivalent Soundex codes (the first character of each code must be uppercase). E.g.

```S600 C560```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of integers a_{1},a_{2},a_{3}.....a_{n}. You are free to replace any integer with any other positive integer. How many integers must be replaced to make the resulting sequence strictly increasing? 

Input Format 

The first line of the test case contains an integer $N$ - the number of entries in the sequence. 

The next line contains $N$ space separated integers where the $i^{\mbox{th}}$ integer is $a_i$.

Output Format 

Output the minimal number of integers that should be replaced to make the sequence strictly increasing.

Constraints 

$0<N\leq10^6$ 

$0<a_i\leq10^9$  

Sample Input #00

3
4 10 20

Sample Output #00

0

Sample Input #01

6
1 7 10 2 20 22

Sample Output #01

1

Sample Input #02

5
1 2 2 3 4 

Sample Output #02

3

Explanation 

In the first sample input, we need not replace anything, hence the output is 0. 

In the second sample input, we can replace 2 with any integer between 11 and 19 to make the sequence strictly increasing, hence the output is 1. 

In the third sample input, we can obtain 1, 2, 3, 4, 5 by changing the last three elements of the sequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer sequence $A_1, A_2, \ldots, A_N$ and an integer $X$. Consider a $N \times N$ matrix $B$, where $B_{i,j} = A_i + A_j$ for each valid $i$ and $j$.
You need to find the number of square submatrices of $B$ such that the sum of their elements is $X$. Formally, find the number of quartets $(x_1, y_1, x_2, y_2)$ such that $1 \le x_1 \le x_2 \le N$, $1 \le y_1 \le y_2 \le N$, $x_2-x_1 = y_2-y_1$ and $\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2} B_{i,j} = X$.

-----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 line of each test case contains two space-separated integers $N$ and $X$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of square submatrices with sum $X$.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le X \le 10^6$
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^6$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points): the sum of $N$ over all test cases does not exceed $1,000$
Subtask #2 (50 points): original constraints

-----Example Input-----
2
5 36
1 2 3 1 12
4 54
3 3 3 3

-----Example Output-----
6
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A forest fire has been spotted at *fire*, a simple 2 element array with x, y coordinates.

The forest service has decided to send smoke jumpers in by plane and drop them in the forest.

The terrain is dangerous and surveyors have determined that there are three possible safe *dropzones*, an array of three simple arrays with x, y coordinates. 

The plane is en route and time is of the essence. Your mission is to return a simple [x,y] array with the coordinates of the dropzone closest to the fire. 

EDIT: 
The airplane is leaving from the origin at 0,0. If your result returns two possible dropzones that are both an equal distance from the fire, choose the dropzone that is closest to 0,0.

If the two dropzones are both equal distance away from 0,0, then return the dropzone that is first in the given array. 

For example, if you are given: fire = [1,1], possibleDZ = [0,1],[1,0],[2,2] . The answer is [0,1] because that is the first possible drop zone in the given array.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tanya and Nina are very close friends, still Tanya is jealous of Nina's problem solving skills. To prove Nina that she is even better than her, Tanya challenged Nina in a game known as Connecting the Dots which she described to her as follows:

There are N dots numbered from 1 to N.

M pair of dots are connected to each other using a ray pointing from one dot to other. 

Each ray will be of one of the K colors.

The objective of the game is to reach dot N starting from dot 1 moving on minimum number of rays pointing from one dot to another.

Nina interrupted Tanya and said "Ohh thats so easy!". Tanya smiled and said, "Wait a moment dear, it's not yet over. There is a special constraint to the above problem i.e. the path of rays connecting dot 1 and dot N should be such that no two successive edges are of the same color, and the path of rays to Node N from Node 1 should be the shortest."

Nina thought for a while bu then realized that the number of dots could be large enough to calculate the answer manually, so she seeks your help. 

Input:

The first line of the input file consists of two integers N and M (). 
Next M lines contain descriptions of the rays. 

Each ray description is a list of three integers X, Y, C which means there exists a C colored ray starting from dot X and pointing to dot Y. All the 3 integers are separated by a single space.

Output:

Print the length of the shortes path between the first dot and the N'th dot.
Print "-1" if no such path exists.

Constraints:

2 ≤ N ≤ 1000

0 ≤ M ≤ N*N

1 ≤ X, Y ≤ N

1 ≤ C ≤ 3

Update: A test file for the problem Connecting the dots has been removed, and hence the points for the problem is decreased by 5.

SAMPLE INPUT
4 4
1 2 1
2 3 2
2 4 1
3 4 3

SAMPLE OUTPUT
3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Nicholas has an array *a* that contains *n* distinct integers from 1 to *n*. In other words, Nicholas has a permutation of size *n*.

Nicholas want the minimum element (integer 1) and the maximum element (integer *n*) to be as far as possible from each other. He wants to perform exactly one swap in order to maximize the distance between the minimum and the maximum elements. The distance between two elements is considered to be equal to the absolute difference between their positions.

Input Specification:
The first line of the input contains a single integer *n* (2<=≤<=*n*<=≤<=100) — the size of the permutation.

The second line of the input contains *n* distinct integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=*n*), where *a**i* is equal to the element at the *i*-th position.

Output Specification:
Print a single integer — the maximum possible distance between the minimum and the maximum elements Nicholas can achieve by performing exactly one swap.

Demo Input:
['5\n4 5 1 3 2\n', '7\n1 6 5 3 4 7 2\n', '6\n6 5 4 3 2 1\n']

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

Note:
In the first sample, one may obtain the optimal answer by swapping elements 1 and 2.

In the second sample, the minimum and the maximum elements will be located in the opposite ends of the array if we swap 7 and 2.

In the third sample, the distance between the minimum and the maximum elements is already maximum possible, so we just perform some unnecessary swap, for example, one can swap 5 and 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a beginner friendly kata especially for UFC/MMA fans. 

It's a fight between the two legends: Conor McGregor vs George Saint Pierre in Madison Square Garden. Only one fighter will remain standing, and after the fight in an interview with Joe Rogan the winner will make his legendary statement. It's your job to return the right statement depending on the winner!

If the winner is George Saint Pierre he will obviously say:
- "I am not impressed by your performance."

If the winner is Conor McGregor he will most undoubtedly say:
- "I'd like to take this chance to apologize.. To absolutely NOBODY!"

Good Luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Luka is slacking again during chemistry class, while the teacher is explaining Avogadro’s law.

Luka first drew a table consisting of $3$ rows and $N$ columns. Then he wrote the numbers $1$ to $N$ into the first row in arbitrary order, each number appearing exactly once. In the other two rows he also wrote integers between $1$ and $N$, but didn’t care how many times a number appeared.

Luka can now delete any set of columns from the table. After doing so, he sorts the numbers in each row in ascending order.

He wants to obtain a table in which all three rows are identical after sorting. Write a program that determines the smallest number of columns he must delete.

For instance, in the first sample input below, Luka can delete the second, fourth, sixth and seventh columns. After deleting these and sorting each row, all three rows contain the numbers 1, 3 and 5.

-----Input-----
The first line of input contains the integer $N$ ($1 \le N \le 100000$), the number of columns in the table. The following three lines contain $N$ integers each, separated by single spaces. The numbers will be between $1$ and $N$, and there will be no duplicates in the first row.

-----Output-----
Output the smallest number of columns Luka must delete.

-----Examples-----
Sample Input:
7
5 4 3 2 1 6 7
5 5 1 1 3 4 7
3 7 1 4 5 6 2
Sample Output:
4

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

Everybody has probably heard of the animal heads and legs problem from the earlier years at school. It goes:

```“A farm contains chickens and cows. There are x heads and y legs. How many chickens and cows are there?” ```

Where x <= 1000 and y <=1000

#Task

Assuming there are no other types of animals, work out how many of each animal are there. 

```Return a tuple in Python - (chickens, cows) and an array list - [chickens, cows]/{chickens, cows} in all other languages```

If either the heads & legs is negative, the result of your calculation is negative or the calculation is a float return "No solutions" (no valid cases).

In the form:
```python
(Heads, Legs) = (72, 200)

VALID - (72, 200) =>             (44 , 28) 
                             (Chickens, Cows)

INVALID - (72, 201) => "No solutions"
```

However, ```if 0 heads and 0 legs are given always return [0, 0]``` since zero heads must give zero animals.

There are many different ways to solve this, but they all give the same answer.

You will only be given integers types - however negative values (edge cases) will be given. 

Happy coding!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string and number of rows ‘n’. Print the string formed by concatenating n rows when the input string is written in row-wise Zig-Zag fashion.
Example 1:
Input: 
str = "ABCDEFGH"
n = 2
Output: "ACEGBDFH"
Explanation: 
Let us write input string in 
Zig-Zag fashion in 2 rows.
A   C   E   G  
  B   D   F   H
Now concatenate the two rows and ignore 
spaces in every row. We get "ACEGBDFH"
Example 2:
Input: 
str = "GEEKSFORGEEKS"
n = 3
Output: GSGSEKFREKEOE
Explanation: 
Let us write input string in 
Zig-Zag fashion in 3 rows.
G       S       G       S
  E   K   F   R   E   K
    E       O       E
Now concatenate the two rows and ignore spaces
in every row. We get "GSGSEKFREKEOE"
Your Task:
You need not read input or print anything. Your task is to complete the function convert() which takes 2 arguments(string str, integer n) and returns the resultant string.
Expected Time Complexity: O(|str|).
Expected Auxiliary Space: O(|str|).
Constraints:
1 ≤ N ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is a number of elements in the array.

You are given an array a consisting of n integers. The value of the i-th element of the array is a_i.

You are also given a set of m segments. The j-th segment is [l_j; r_j], where 1 ≤ l_j ≤ r_j ≤ n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a = [0, 0, 0, 0, 0] and the given segments are [1; 3] and [2; 4] then you can choose both of them and the array will become b = [-1, -2, -2, -1, 0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array a and obtain the array b then the value max_{i=1}^{n}b_i - min_{i=1}^{n}b_i will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 300, 0 ≤ m ≤ 300) — the length of the array a and the number of segments, respectively.

The second line of the input contains n integers a_1, a_2, ..., a_n (-10^6 ≤ a_i ≤ 10^6), where a_i is the value of the i-th element of the array a.

The next m lines are contain two integers each. The j-th of them contains two integers l_j and r_j (1 ≤ l_j ≤ r_j ≤ n), where l_j and r_j are the ends of the j-th segment.

Output

In the first line of the output print one integer d — the maximum possible value max_{i=1}^{n}b_i - min_{i=1}^{n}b_i if b is the array obtained by applying some subset of the given segments to the array a.

In the second line of the output print one integer q (0 ≤ q ≤ m) — the number of segments you apply.

In the third line print q distinct integers c_1, c_2, ..., c_q in any order (1 ≤ c_k ≤ m) — indices of segments you apply to the array a in such a way that the value max_{i=1}^{n}b_i - min_{i=1}^{n}b_i of the obtained array b is maximum possible.

If there are multiple answers, you can print any.

Examples

Input


5 4
2 -2 3 1 2
1 3
4 5
2 5
1 3


Output


6
2
1 4 


Input


5 4
2 -2 3 1 4
3 5
3 4
2 4
2 5


Output


7
2
3 2 


Input


1 0
1000000


Output


0
0

Note

In the first example the obtained array b will be [0, -4, 1, 1, 2] so the answer is 6.

In the second example the obtained array b will be [2, -3, 1, -1, 4] so the answer is 7.

In the third example you cannot do anything so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Susie loves strings. Today she calculates distances between them. As Susie is a small girl after all, her strings contain only digits zero and one. She uses the definition of Hamming distance:

We will define the distance between two strings s and t of the same length consisting of digits zero and one as the number of positions i, such that si isn't equal to ti. 

As besides everything else Susie loves symmetry, she wants to find for two strings s and t of length n such string p of length n, that the distance from p to s was equal to the distance from p to t.

It's time for Susie to go to bed, help her find such string p or state that it is impossible.

Input

The first line contains string s of length n. 

The second line contains string t of length n.

The length of string n is within range from 1 to 105. It is guaranteed that both strings contain only digits zero and one.

Output

Print a string of length n, consisting of digits zero and one, that meets the problem statement. If no such string exist, print on a single line "impossible" (without the quotes).

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

Examples

Input

0001
1011


Output

0011


Input

000
111


Output

impossible

Note

In the first sample different answers are possible, namely — 0010, 0011, 0110, 0111, 1000, 1001, 1100, 1101.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Disclaimer: there are lots of untranslateable puns in the Russian version of the statement, so there is one more reason for you to learn Russian :)

Rick and Morty like to go to the ridge High Cry for crying loudly — there is an extraordinary echo. Recently they discovered an interesting acoustic characteristic of this ridge: if Rick and Morty begin crying simultaneously from different mountains, their cry would be heard between these mountains up to the height equal the bitwise OR of mountains they've climbed and all the mountains between them. 

Bitwise OR is a binary operation which is determined the following way. Consider representation of numbers x and y in binary numeric system (probably with leading zeroes) x = x_{k}... x_1x_0 and y = y_{k}... y_1y_0. Then z = x | y is defined following way: z = z_{k}... z_1z_0, where z_{i} = 1, if x_{i} = 1 or y_{i} = 1, and z_{i} = 0 otherwise. In the other words, digit of bitwise OR of two numbers equals zero if and only if digits at corresponding positions is both numbers equals zero. For example bitwise OR of numbers 10 = 1010_2 and 9 = 1001_2 equals 11 = 1011_2. In programming languages C/C++/Java/Python this operation is defined as «|», and in Pascal as «or».

Help Rick and Morty calculate the number of ways they can select two mountains in such a way that if they start crying from these mountains their cry will be heard above these mountains and all mountains between them. More formally you should find number of pairs l and r (1 ≤ l < r ≤ n) such that bitwise OR of heights of all mountains between l and r (inclusive) is larger than the height of any mountain at this interval.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 200 000), the number of mountains in the ridge.

Second line contains n integers a_{i} (0 ≤ a_{i} ≤ 10^9), the heights of mountains in order they are located in the ridge.


-----Output-----

Print the only integer, the number of ways to choose two different mountains.


-----Examples-----
Input
5
3 2 1 6 5

Output
8

Input
4
3 3 3 3

Output
0



-----Note-----

In the first test case all the ways are pairs of mountains with the numbers (numbering from one):(1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)

In the second test case there are no such pairs because for any pair of mountains the height of cry from them is 3, and this height is equal to the height of any mountain.

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