vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Working out

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Summer is coming! It's time for Iahub and Iahubina to work out, as they both want to look hot at the beach. The gym where they go is a matrix *a* with *n* lines and *m* columns. Let number *a*[*i*][*j*] represents the calories burned by performing workout at the cell of gym in the *i*-th line and the *j*-th column.

Iahub starts with workout located at line 1 and column 1. He needs to finish with workout *a*[*n*][*m*]. After finishing workout *a*[*i*][*j*], he can go to workout *a*[*i*<=+<=1][*j*] or *a*[*i*][*j*<=+<=1]. Similarly, Iahubina starts with workout *a*[*n*][1] and she needs to finish with workout *a*[1][*m*]. After finishing workout from cell *a*[*i*][*j*], she goes to either *a*[*i*][*j*<=+<=1] or *a*[*i*<=-<=1][*j*]. 

There is one additional condition for their training. They have to meet in exactly one cell of gym. At that cell, none of them will work out. They will talk about fast exponentiation (pretty odd small talk) and then both of them will move to the next workout.

If a workout was done by either Iahub or Iahubina, it counts as total gain. Please plan a workout for Iahub and Iahubina such as total gain to be as big as possible. Note, that Iahub and Iahubina can perform workouts with different speed, so the number of cells that they use to reach meet cell may differs.

Input Specification:
The first line of the input contains two integers *n* and *m* (3<=≤<=*n*,<=*m*<=≤<=1000). Each of the next *n* lines contains *m* integers: *j*-th number from *i*-th line denotes element *a*[*i*][*j*] (0<=≤<=*a*[*i*][*j*]<=≤<=105).

Output Specification:
The output contains a single number — the maximum total gain possible.

Demo Input:
['3 3\n100 100 100\n100 1 100\n100 100 100\n']

Demo Output:
['800']

Note:
Iahub will choose exercises *a*[1][1] → *a*[1][2] → *a*[2][2] → *a*[3][2] → *a*[3][3]. Iahubina will choose exercises *a*[3][1] → *a*[2][1] → *a*[2][2] → *a*[2][3] → *a*[1][3].

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Vasya is a born Berland film director, he is currently working on a new blockbuster, "The Unexpected". Vasya knows from his own experience how important it is to choose the main characters' names and surnames wisely. He made up a list of *n* names and *n* surnames that he wants to use. Vasya haven't decided yet how to call characters, so he is free to match any name to any surname. Now he has to make the list of all the main characters in the following format: "*Name*1 *Surname*1, *Name*2 *Surname*2, ..., *Name**n* *Surname**n*", i.e. all the name-surname pairs should be separated by exactly one comma and exactly one space, and the name should be separated from the surname by exactly one space. First of all Vasya wants to maximize the number of the pairs, in which the name and the surname start from one letter. If there are several such variants, Vasya wants to get the lexicographically minimal one. Help him.

An answer will be verified a line in the format as is shown above, including the needed commas and spaces. It's the lexicographical minimality of such a line that needs to be ensured. The output line shouldn't end with a space or with a comma.

Input Specification:
The first input line contains number *n* (1<=≤<=*n*<=≤<=100) — the number of names and surnames. Then follow *n* lines — the list of names. Then follow *n* lines — the list of surnames. No two from those 2*n* strings match. Every name and surname is a non-empty string consisting of no more than 10 Latin letters. It is guaranteed that the first letter is uppercase and the rest are lowercase.

Output Specification:
The output data consist of a single line — the needed list. Note that one should follow closely the output data format!

Demo Input:
['4\nAnn\nAnna\nSabrina\nJohn\nPetrov\nIvanova\nStoltz\nAbacaba\n', '4\nAa\nAb\nAc\nBa\nAd\nAe\nBb\nBc\n']

Demo Output:
['Ann Abacaba, Anna Ivanova, John Petrov, Sabrina Stoltz', 'Aa Ad, Ab Ae, Ac Bb, Ba Bc']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A system is transmitting messages in binary, however it is not a perfect transmission, and sometimes errors will occur which result in a single bit flipping from 0 to 1, or from 1 to 0.

To resolve this, A 2-dimensional Parity Bit Code is used: https://en.wikipedia.org/wiki/Multidimensional_parity-check_code

In this system, a message is arrayed out on a M x N grid. A 24-bit message could be put on a 4x6 grid like so:


>1 0 1 0 0 1
>1 0 0 1 0 0
>0 1 1 1 0 1
>1 0 0 0 0 1

Then, Parity bits are computed for each row and for each column, equal to 1 if there is an odd number of 1s in the row of column, and 0 if it is an even number. The result for the above message looks like:


>1 0 1 0 0 1 1
>1 0 0 1 0 0 0
>0 1 1 1 0 1 0
>1 0 0 0 0 1 0
>1 1 0 0 0 1

Since the 1st row, and 1st, 2nd and 6th column each have an odd number of 1s in them, and the others all do not.

Then the whole message is sent, including the parity bits. This is arranged as:

> message + row_parities + column_parities
> 101001100100011101100001 + 1000 + 110001
> 1010011001000111011000011000110001

If an error occurs in transmission, the parity bit for a column and row will be incorrect, which can be used to identify and correct the error. If a row parity bit is incorrect, but all column bits are correct, then we can assume the row parity bit was the one flipped, and likewise if a column is wrong but all rows are correct.

 Your Task: 

Create a function correct, which takes in integers M and N, and a string of bits where the first M\*N represent the content of the message, the next M represent the parity bits for the rows, and the final N represent the parity bits for the columns. A single-bit error may or may not have appeared in the bit array.

The function should check to see if there is a single-bit error in the coded message, correct it if it exists, and return the corrected string of bits.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation of n numbers p1, p2, ..., pn. We perform k operations of the following type: choose uniformly at random two indices l and r (l ≤ r) and reverse the order of the elements pl, pl + 1, ..., pr. Your task is to find the expected value of the number of inversions in the resulting permutation.

Input

The first line of input contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 109). The next line contains n integers p1, p2, ..., pn — the given permutation. All pi are different and in range from 1 to n.

The problem consists of three subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

  * In subproblem G1 (3 points), the constraints 1 ≤ n ≤ 6, 1 ≤ k ≤ 4 will hold. 
  * In subproblem G2 (5 points), the constraints 1 ≤ n ≤ 30, 1 ≤ k ≤ 200 will hold. 
  * In subproblem G3 (16 points), the constraints 1 ≤ n ≤ 100, 1 ≤ k ≤ 109 will hold. 

Output

Output the answer with absolute or relative error no more than 1e - 9.

Examples

Input

3 1
1 2 3


Output

0.833333333333333


Input

3 4
1 3 2


Output

1.458333333333334

Note

Consider the first sample test. We will randomly pick an interval of the permutation (1, 2, 3) (which has no inversions) and reverse the order of its elements. With probability <image>, the interval will consist of a single element and the permutation will not be altered. With probability <image> we will inverse the first two elements' order and obtain the permutation (2, 1, 3) which has one inversion. With the same probability we might pick the interval consisting of the last two elements which will lead to the permutation (1, 3, 2) with one inversion. Finally, with probability <image> the randomly picked interval will contain all elements, leading to the permutation (3, 2, 1) with 3 inversions. Hence, the expected number of inversions is equal to <image>.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Innocentius has a problem — his computer monitor has broken. Now some of the pixels are "dead", that is, they are always black. As consequence, Innocentius can't play the usual computer games. He is recently playing the following game with his younger brother Polycarpus.

Innocentius is touch-typing a program that paints a white square one-pixel wide frame on the black screen. As the monitor is broken, some pixels that should be white remain black. Polycarpus should look at what the program displayed on the screen and guess the position and size of the frame Innocentius has painted. Polycarpus doesn't like the game but Innocentius persuaded brother to play as "the game is good for the imagination and attention".

Help Polycarpus, automatize his part in the gaming process. Write the code that finds such possible square frame that:
 -  the frame's width is 1 pixel, -  the frame doesn't go beyond the borders of the screen, -  all white pixels of the monitor are located on the frame, -  of all frames that satisfy the previous three conditions, the required frame must have the smallest size. 
Formally, a square frame is represented by such pixels of the solid square, that are on the square's border, that is, are not fully surrounded by the other pixels of the square. For example, if the frame's size is *d*<==<=3, then it consists of 8 pixels, if its size is *d*<==<=2, then it contains 4 pixels and if *d*<==<=1, then the frame is reduced to a single pixel.

Input Specification:
The first line contains the resolution of the monitor as a pair of integers *n*, *m* (1<=≤<=*n*,<=*m*<=≤<=2000). The next *n* lines contain exactly *m* characters each — the state of the monitor pixels at the moment of the game. Character "." (period, ASCII code 46) corresponds to the black pixel, and character "w" (lowercase English letter w) corresponds to the white pixel. It is guaranteed that at least one pixel of the monitor is white.

Output Specification:
Print the monitor screen. Represent the sought frame by characters "+" (the "plus" character). The pixels that has become white during the game mustn't be changed. Print them as "w". If there are multiple possible ways to position the frame of the minimum size, print any of them.

If the required frame doesn't exist, then print a single line containing number -1.

Demo Input:
['4 8\n..w..w..\n........\n........\n..w..w..\n', '5 6\n......\n.w....\n......\n..w...\n......\n', '2 4\n....\n.w..\n', '2 6\nw..w.w\n...w..\n']

Demo Output:
['..w++w..\n..+..+..\n..+..+..\n..w++w..\n', '......\n+w+...\n+.+...\n++w...\n......\n', '....\n.w..\n', '-1\n']

Note:
In the first sample the required size of the optimal frame equals 4. In the second sample the size of the optimal frame equals 3. In the third sample, the size of the optimal frame is 1. In the fourth sample, the required frame doesn't exist.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a string S of length N consisting of lowercase English letters.
Snuke can do this operation any number of times: remove fox occurring as a substring from s and concatenate the remaining parts of s.
What is the minimum possible length of s after some number of operations by Snuke?

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^{5}
 - s is a string of length N consisting of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
N
s

-----Print-----
Print the minimum possible length of s after some number of operations by Snuke.

-----Sample Input-----
6
icefox

-----Sample Output-----
3

 - By removing the fox at the end of icefox, we can turn s into ice.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The name of one small but proud corporation consists of n lowercase English letters. The Corporation has decided to try rebranding — an active marketing strategy, that includes a set of measures to change either the brand (both for the company and the goods it produces) or its components: the name, the logo, the slogan. They decided to start with the name.

For this purpose the corporation has consecutively hired m designers. Once a company hires the i-th designer, he immediately contributes to the creation of a new corporation name as follows: he takes the newest version of the name and replaces all the letters x_{i} by y_{i}, and all the letters y_{i} by x_{i}. This results in the new version. It is possible that some of these letters do no occur in the string. It may also happen that x_{i} coincides with y_{i}. The version of the name received after the work of the last designer becomes the new name of the corporation.

Manager Arkady has recently got a job in this company, but is already soaked in the spirit of teamwork and is very worried about the success of the rebranding. Naturally, he can't wait to find out what is the new name the Corporation will receive.

Satisfy Arkady's curiosity and tell him the final version of the name.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the length of the initial name and the number of designers hired, respectively.

The second line consists of n lowercase English letters and represents the original name of the corporation.

Next m lines contain the descriptions of the designers' actions: the i-th of them contains two space-separated lowercase English letters x_{i} and y_{i}.


-----Output-----

Print the new name of the corporation.


-----Examples-----
Input
6 1
police
p m

Output
molice

Input
11 6
abacabadaba
a b
b c
a d
e g
f a
b b

Output
cdcbcdcfcdc



-----Note-----

In the second sample the name of the corporation consecutively changes as follows: $\text{abacabadaba} \rightarrow \text{babcbabdbab}$

$\text{babcbabdbab} \rightarrow \text{cacbcacdcac}$

$\text{cacbcacdcac} \rightarrow \text{cdcbcdcacdc}$

[Image]

[Image]

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the array `[3,6,9,12]`. If we generate all the combinations with repetition that sum to `12`, we get `5` combinations: `[12], [6,6], [3,9], [3,3,6], [3,3,3,3]`. The length of the sub-arrays (such as `[3,3,3,3]` should be less than or equal to the length of the initial array (`[3,6,9,12]`).  

Given an array of positive integers and a number `n`, count all combinations with repetition of integers that sum to `n`. For example: 
```Haskell
find([3,6,9,12],12) = 5.
```

More examples in the test cases. 

Good luck!

If you like this Kata, please try:

[Array combinations](https://www.codewars.com/kata/59e66e48fc3c499ec5000103)

[Sum of prime-indexed elements](https://www.codewars.com/kata/59f38b033640ce9fc700015b)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya is currently at a car rental service, and he wants to reach cinema. The film he has bought a ticket for starts in t minutes. There is a straight road of length s from the service to the cinema. Let's introduce a coordinate system so that the car rental service is at the point 0, and the cinema is at the point s.

There are k gas stations along the road, and at each of them you can fill a car with any amount of fuel for free! Consider that this operation doesn't take any time, i.e. is carried out instantly.

There are n cars in the rental service, i-th of them is characterized with two integers ci and vi — the price of this car rent and the capacity of its fuel tank in liters. It's not allowed to fuel a car with more fuel than its tank capacity vi. All cars are completely fueled at the car rental service.

Each of the cars can be driven in one of two speed modes: normal or accelerated. In the normal mode a car covers 1 kilometer in 2 minutes, and consumes 1 liter of fuel. In the accelerated mode a car covers 1 kilometer in 1 minutes, but consumes 2 liters of fuel. The driving mode can be changed at any moment and any number of times.

Your task is to choose a car with minimum price such that Vasya can reach the cinema before the show starts, i.e. not later than in t minutes. Assume that all cars are completely fueled initially.

Input

The first line contains four positive integers n, k, s and t (1 ≤ n ≤ 2·105, 1 ≤ k ≤ 2·105, 2 ≤ s ≤ 109, 1 ≤ t ≤ 2·109) — the number of cars at the car rental service, the number of gas stations along the road, the length of the road and the time in which the film starts. 

Each of the next n lines contains two positive integers ci and vi (1 ≤ ci, vi ≤ 109) — the price of the i-th car and its fuel tank capacity.

The next line contains k distinct integers g1, g2, ..., gk (1 ≤ gi ≤ s - 1) — the positions of the gas stations on the road in arbitrary order.

Output

Print the minimum rent price of an appropriate car, i.e. such car that Vasya will be able to reach the cinema before the film starts (not later than in t minutes). If there is no appropriate car, print -1.

Examples

Input

3 1 8 10
10 8
5 7
11 9
3


Output

10


Input

2 2 10 18
10 4
20 6
5 3


Output

20

Note

In the first sample, Vasya can reach the cinema in time using the first or the third cars, but it would be cheaper to choose the first one. Its price is equal to 10, and the capacity of its fuel tank is 8. Then Vasya can drive to the first gas station in the accelerated mode in 3 minutes, spending 6 liters of fuel. After that he can full the tank and cover 2 kilometers in the normal mode in 4 minutes, spending 2 liters of fuel. Finally, he drives in the accelerated mode covering the remaining 3 kilometers in 3 minutes and spending 6 liters of fuel.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The grand kingdom of Mancunia is famous for its tourist attractions and visitors flock to it throughout the year. King Mancunian is the benevolent ruler of the prosperous country whose main source of revenue is, of course, tourism.

The country can be represented by a network of unidirectional roads between the cities. But Mancunian, our benign monarch, has a headache. The road network of the country is not tourist-friendly and this is affecting revenue. To increase the GDP of the nation, he wants to redirect some of the roads to make the road network tourist-friendly and hence, ensure happiness and prosperity for his loyal subjects.

Now is the time for some formal definitions. :(

A road network is said to be tourist-friendly if for every city in the country, if a tourist starts his journey there, there is a path she can take to visit each and every city of the nation and traverse each road exactly once before ending up at the city where she started.

Given a description of the road network of Mancunia, can you come up with a scheme to redirect some (possibly none) of the roads to make it tourist-friendly?

-----Input-----
The first line contains two integers N and E denoting the number of cities and roads in the beautiful country of Mancunia respectively.
Each of the next E lines contains two integers a and b implying that there is a unidirectional road from city a to city b.

It is guaranteed that there aren't multiple roads in the exact same direction and that there is no road from a city to itself.

-----Output-----
If there is no solution, print "NO" (without quotes). Else, print "YES" (without quotes), followed by exactly E lines.
The ith line of output should represent the ith road in the input. It should have two integers a and b denoting that the final orientation of that road is from a to b.

-----Constraints-----

- 1 ≤ N ≤ 100000
- 1 ≤ E ≤ 200000
- 1 ≤ a, b ≤ N

Subtask 1: (20 points)
- 1 ≤ N ≤ 20
- 1 ≤ E ≤ 21

Subtask 2: (80 points)
- Same as original constraints

-----Example 1-----
Input:
3 3
1 2
2 3
3 1

Output:
YES
1 2
2 3
3 1

-----Example 2-----
Input:
3 2
1 2
2 3

Output:
NO

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

Output:
YES
1 2
2 3
3 4
4 2
2 5
5 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ashish and Vivek play a game on a matrix consisting of $n$ rows and $m$ columns, where they take turns claiming cells. Unclaimed cells are represented by $0$, while claimed cells are represented by $1$. The initial state of the matrix is given. There can be some claimed cells in the initial state.

In each turn, a player must claim a cell. A cell may be claimed if it is unclaimed and does not share a row or column with any other already claimed cells. When a player is unable to make a move, he loses and the game ends.

If Ashish and Vivek take turns to move and Ashish goes first, determine the winner of the game if both of them are playing optimally.

Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves.


-----Input-----

The first line consists of a single integer $t$ $(1 \le t \le 50)$ — the number of test cases. The description of the test cases follows.

The first line of each test case consists of two space-separated integers $n$, $m$ $(1 \le n, m \le 50)$ — the number of rows and columns in the matrix.

The following $n$ lines consist of $m$ integers each, the $j$-th integer on the $i$-th line denoting $a_{i,j}$ $(a_{i,j} \in \{0, 1\})$.


-----Output-----

For each test case if Ashish wins the game print "Ashish" otherwise print "Vivek" (without quotes).


-----Example-----
Input
4
2 2
0 0
0 0
2 2
0 0
0 1
2 3
1 0 1
1 1 0
3 3
1 0 0
0 0 0
1 0 0

Output
Vivek
Ashish
Vivek
Ashish



-----Note-----

For the first case: One possible scenario could be: Ashish claims cell $(1, 1)$, Vivek then claims cell $(2, 2)$. Ashish can neither claim cell $(1, 2)$, nor cell $(2, 1)$ as cells $(1, 1)$ and $(2, 2)$ are already claimed. Thus Ashish loses. It can be shown that no matter what Ashish plays in this case, Vivek will win. 

For the second case: Ashish claims cell $(1, 1)$, the only cell that can be claimed in the first move. After that Vivek has no moves left.

For the third case: Ashish cannot make a move, so Vivek wins.

For the fourth case: If Ashish claims cell $(2, 3)$, Vivek will have no moves left.

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