vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given an integer array. The task is to find the maximum of the minimum of every window size in the array.
Note: Window size varies from 1 to the size of the Array.
Example 1:
Input:
N = 7
arr[] = {10,20,30,50,10,70,30}
Output: 70 30 20 10 10 10 10 
Explanation: 
1.First element in output
indicates maximum of minimums of all
windows of size 1.
2.Minimums of windows of size 1 are {10},
 {20}, {30}, {50},{10}, {70} and {30}. 
 Maximum of these minimums is 70. 
3. Second element in output indicates
maximum of minimums of all windows of
size 2. 
4. Minimums of windows of size 2
are {10}, {20}, {30}, {10}, {10}, and
{30}.
5. Maximum of these minimums is 30 
Third element in output indicates
maximum of minimums of all windows of
size 3. 
6. Minimums of windows of size 3
are {10}, {20}, {10}, {10} and {10}.
7.Maximum of these minimums is 20. 
Similarly other elements of output are
computed.
Example 2:
Input:
N = 3
arr[] = {10,20,30}
Output: 30 20 10
Explanation: First element in output
indicates maximum of minimums of all
windows of size 1.Minimums of windows
of size 1 are {10} , {20} , {30}.
Maximum of these minimums are 30 and
similarly other outputs can be computed
Your Task:
The task is to complete the function maxOfMin() which takes the array arr[] and its size N as inputs and finds the maximum of minimum of every window size and returns an array containing the result. 
Expected Time Complxity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kirill plays a new computer game. He came to the potion store where he can buy any potion. Each potion is characterized by two integers — amount of experience and cost. The efficiency of a potion is the ratio of the amount of experience to the cost. Efficiency may be a non-integer number.

For each two integer numbers a and b such that l ≤ a ≤ r and x ≤ b ≤ y there is a potion with experience a and cost b in the store (that is, there are (r - l + 1)·(y - x + 1) potions).

Kirill wants to buy a potion which has efficiency k. Will he be able to do this?


-----Input-----

First string contains five integer numbers l, r, x, y, k (1 ≤ l ≤ r ≤ 10^7, 1 ≤ x ≤ y ≤ 10^7, 1 ≤ k ≤ 10^7).


-----Output-----

Print "YES" without quotes if a potion with efficiency exactly k can be bought in the store and "NO" without quotes otherwise.

You can output each of the letters in any register.


-----Examples-----
Input
1 10 1 10 1

Output
YES
Input
1 5 6 10 1

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The capital of Berland has n multifloor buildings. The architect who built up the capital was very creative, so all the houses were built in one row.

Let's enumerate all the houses from left to right, starting with one. A house is considered to be luxurious if the number of floors in it is strictly greater than in all the houses with larger numbers. In other words, a house is luxurious if the number of floors in it is strictly greater than in all the houses, which are located to the right from it. In this task it is assumed that the heights of floors in the houses are the same.

The new architect is interested in n questions, i-th of them is about the following: "how many floors should be added to the i-th house to make it luxurious?" (for all i from 1 to n, inclusive). You need to help him cope with this task.

Note that all these questions are independent from each other — the answer to the question for house i does not affect other answers (i.e., the floors to the houses are not actually added).


-----Input-----

The first line of the input contains a single number n (1 ≤ n ≤ 10^5) — the number of houses in the capital of Berland.

The second line contains n space-separated positive integers h_{i} (1 ≤ h_{i} ≤ 10^9), where h_{i} equals the number of floors in the i-th house. 


-----Output-----

Print n integers a_1, a_2, ..., a_{n}, where number a_{i} is the number of floors that need to be added to the house number i to make it luxurious. If the house is already luxurious and nothing needs to be added to it, then a_{i} should be equal to zero.

All houses are numbered from left to right, starting from one.


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

Output
3 2 0 2 0 
Input
4
3 2 1 4

Output
2 3 4 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem, you will be given a polynomial, you have to print what it becomes after differentiation.

Following are the rules for differentiation:
- For a polynomial f(x), its differentiation is defined as f'(x).
- If a is a constant, then differentiation of af(x) is af'(x).
- If f(x) = h(x) + g(x) , then f'(x) = h'(x) + g'(x) 
- If f(x) = x n, then f'(x) = nxn-1. This is true for all  n ≠ 0 .
- If f(x) = c, where c is a constant, f'(x) = 0.

If you are still uncomfortable with differentiation, please read the following:
-  Link to Wikihow page
- Link to Wikipedia entry.

-----Input-----

First line contains T, the number of test cases to follow. 

Each test case contains the follows, the first line contains N, the number of non zero terms in the polynomial. Then N lines follow, each line contains a pair of integer which denotes a term in the polynomial, where the first element denotes the coefficient (a) and the second denotes the exponent (p) of the term.

-----Output-----
Print the polynomial after differentiation in the desired format as described below.
-  If the coefficient of a term in the output polynomial is 3, and the corresponding exponent is 2, print it as 3x^2
- Print " + " (with single space on both side) between each output term.
-  Print the terms in decreasing value of exponent.
-  For the constant term (if any), you have to just print the coefficient. You should not print x^0.

-----Constraints-----
- 1 ≤ T ≤ 10
-   Subtask 1 (20 points)

- 1 ≤ N ≤ 3
- 1 ≤ a ≤ 10
- 0 ≤ p ≤ 10
- Subtask 2 (80 points)

- 1 ≤ N ≤ 10000
- 1 ≤ a ≤ 100000000
- 0 ≤ p ≤ 100000000
-  No two inputs in a test case will have the same exponent.

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

Output:
2x^1
3x^2 + 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a collection of $N$ non-empty strings, denoted by $S_1, S_2, \ldots , S_ n$. Then you are given $N$-$1$ operations which you execute in the order they are given. The $i^{th}$ operation is has the following format: ‘$a$$b$’ ($1$-based indexing, without the quotes), which means that you have to make the following changes:
 - $S_ a = S_ a + S_ b$, i.e. concatenate $a^{th}$ string and $b^{th}$ string and store the result in $a^{th}$ string,
 - $S_ b$ = "", i.e. make the $b^{th}$ string empty, after doing the previous step.

You are ensured that after the $i^{th}$ operation, there will be no future operation that will be accessing $S_ b$. Given these operations to join strings, print the last string that will remain at the end of this process.

-----Input-----
The first line contains an integer $N$ ($1 \le N \le 10^5$) denoting the number of strings given. Each of the next $N$ lines contains a string denoting the $S_ i$. All the characters in the string $S_ i$ are lowercase alphabets from ‘a’ to ‘z’. The total number of characters over all the strings is at most $10^6$, i.e $\sum _{i = 1}^{N}|S_ i| \leq 10^6$, where $|S_ i|$ denotes the length of the $i^{th}$ string. After these $N$ strings, each of the next $N$-$1$ lines contain two integers $a$ and $b$, such that $a \neq b$ and $1 \le a, b \le N$ denoting the $i^{th}$ operation.

-----Output-----
Print the last string which remains at the end of the $N$-$1$ operations.

-----Warning-----
The I/O files are large. Please use fast I/O methods.

-----Examples-----
Sample Input:
4
cute
cat
kattis
is
3 2
4 1
3 4
Sample Output:
kattiscatiscute

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Maxim has opened his own restaurant! The restaurant has got a huge table, the table's length is p meters.

Maxim has got a dinner party tonight, n guests will come to him. Let's index the guests of Maxim's restaurant from 1 to n. Maxim knows the sizes of all guests that are going to come to him. The i-th guest's size (a_{i}) represents the number of meters the guest is going to take up if he sits at the restaurant table.

Long before the dinner, the guests line up in a queue in front of the restaurant in some order. Then Maxim lets the guests in, one by one. Maxim stops letting the guests in when there is no place at the restaurant table for another guest in the queue. There is no place at the restaurant table for another guest in the queue, if the sum of sizes of all guests in the restaurant plus the size of this guest from the queue is larger than p. In this case, not to offend the guest who has no place at the table, Maxim doesn't let any other guest in the restaurant, even if one of the following guests in the queue would have fit in at the table.

Maxim is now wondering, what is the average number of visitors who have come to the restaurant for all possible n! orders of guests in the queue. Help Maxim, calculate this number.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 50) — the number of guests in the restaurant. The next line contains integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 50) — the guests' sizes in meters. The third line contains integer p (1 ≤ p ≤ 50) — the table's length in meters. 

The numbers in the lines are separated by single spaces.


-----Output-----

In a single line print a real number — the answer to the problem. The answer will be considered correct, if the absolute or relative error doesn't exceed 10^{ - 4}.


-----Examples-----
Input
3
1 2 3
3

Output
1.3333333333



-----Note-----

In the first sample the people will come in the following orders:   (1, 2, 3) — there will be two people in the restaurant;  (1, 3, 2) — there will be one person in the restaurant;  (2, 1, 3) — there will be two people in the restaurant;  (2, 3, 1) — there will be one person in the restaurant;  (3, 1, 2) — there will be one person in the restaurant;  (3, 2, 1) — there will be one person in the restaurant. 

In total we get (2 + 1 + 2 + 1 + 1 + 1) / 6 = 8 / 6 = 1.(3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an encoded string S of length N. The encoded string is mixed with some number of substring "LIE" and some secret message. You have to extract secret message from it by removing all the "LIE" substrings.
For example - "I AM COOL" is given as "LIEILIEAMLIELIECOOL".
Example 1:
Input: S = "LIEILIEAMLIELIECOOL"
Output: "I AM COOL"
Example 2:
Input: S = "LIELIEALIEBCLIE"
Output: "A BC"
Your Task:  
You don't need to read input or print anything. Your task is to complete the function ExtractMessage() which accepts a string as input parameter and returns a string containing secret message.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}
String contains only Upper Case Letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jon Snow now has to fight with White Walkers. He has n rangers, each of which has his own strength. Also Jon Snow has his favourite number x. Each ranger can fight with a white walker only if the strength of the white walker equals his strength. He however thinks that his rangers are weak and need to improve. Jon now thinks that if he takes the bitwise XOR of strengths of some of rangers with his favourite number x, he might get soldiers of high strength. So, he decided to do the following operation k times: 

 Arrange all the rangers in a straight line in the order of increasing strengths.

 Take the bitwise XOR (is written as $\oplus$) of the strength of each alternate ranger with x and update it's strength.

 Suppose, Jon has 5 rangers with strengths [9, 7, 11, 15, 5] and he performs the operation 1 time with x = 2. He first arranges them in the order of their strengths, [5, 7, 9, 11, 15]. Then he does the following: 

 The strength of first ranger is updated to $5 \oplus 2$, i.e. 7.

 The strength of second ranger remains the same, i.e. 7.

 The strength of third ranger is updated to $9 \oplus 2$, i.e. 11.

 The strength of fourth ranger remains the same, i.e. 11.

 The strength of fifth ranger is updated to $15 \oplus 2$, i.e. 13.

 The new strengths of the 5 rangers are [7, 7, 11, 11, 13]

Now, Jon wants to know the maximum and minimum strength of the rangers after performing the above operations k times. He wants your help for this task. Can you help him?


-----Input-----

First line consists of three integers n, k, x (1 ≤ n ≤ 10^5, 0 ≤ k ≤ 10^5, 0 ≤ x ≤ 10^3) — number of rangers Jon has, the number of times Jon will carry out the operation and Jon's favourite number respectively.

Second line consists of n integers representing the strengths of the rangers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^3).


-----Output-----

Output two integers, the maximum and the minimum strength of the rangers after performing the operation k times.


-----Examples-----
Input
5 1 2
9 7 11 15 5

Output
13 7
Input
2 100000 569
605 986

Output
986 605

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Emuskald is a well-known illusionist. One of his trademark tricks involves a set of magical boxes. The essence of the trick is in packing the boxes inside other boxes.

From the top view each magical box looks like a square with side length equal to 2*k* (*k* is an integer, *k*<=≥<=0) units. A magical box *v* can be put inside a magical box *u*, if side length of *v* is strictly less than the side length of *u*. In particular, Emuskald can put 4 boxes of side length 2*k*<=-<=1 into one box of side length 2*k*, or as in the following figure:

Emuskald is about to go on tour performing around the world, and needs to pack his magical boxes for the trip. He has decided that the best way to pack them would be inside another magical box, but magical boxes are quite expensive to make. Help him find the smallest magical box that can fit all his boxes.

Input Specification:
The first line of input contains an integer *n* (1<=≤<=*n*<=≤<=105), the number of different sizes of boxes Emuskald has. Each of following *n* lines contains two integers *k**i* and *a**i* (0<=≤<=*k**i*<=≤<=109, 1<=≤<=*a**i*<=≤<=109), which means that Emuskald has *a**i* boxes with side length 2*k**i*. It is guaranteed that all of *k**i* are distinct.

Output Specification:
Output a single integer *p*, such that the smallest magical box that can contain all of Emuskald’s boxes has side length 2*p*.

Demo Input:
['2\n0 3\n1 5\n', '1\n0 4\n', '2\n1 10\n2 2\n']

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

Note:
Picture explanation. If we have 3 boxes with side length 2 and 5 boxes with side length 1, then we can put all these boxes inside a box with side length 4, for example, as shown in the picture.

In the second test case, we can put all four small boxes into a box with side length 2.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a rectangular table 3<=×<=*n*. Each cell contains an integer. You can move from one cell to another if they share a side.

Find such path from the upper left cell to the bottom right cell of the table that doesn't visit any of the cells twice, and the sum of numbers written in the cells of this path is maximum possible.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=105)  — the number of columns in the table.

Next three lines contain *n* integers each  — the description of the table. The *j*-th number in the *i*-th line corresponds to the cell *a**ij* (<=-<=109<=≤<=*a**ij*<=≤<=109) of the table.

Output Specification:
Output the maximum sum of numbers on a path from the upper left cell to the bottom right cell of the table, that doesn't visit any of the cells twice.

Demo Input:
['3\n1 1 1\n1 -1 1\n1 1 1\n', '5\n10 10 10 -1 -1\n-1 10 10 10 10\n-1 10 10 10 10\n']

Demo Output:
['7\n', '110\n']

Note:
The path for the first example:

The path for the second example:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob is a farmer. He has a large pasture with many sheep. Recently, he has lost some of them due to wolf attacks. He thus decided to place some shepherd dogs in such a way that all his sheep are protected.

The pasture is a rectangle consisting of R × C cells. Each cell is either empty, contains a sheep, a wolf or a dog. Sheep and dogs always stay in place, but wolves can roam freely around the pasture, by repeatedly moving to the left, right, up or down to a neighboring cell. When a wolf enters a cell with a sheep, it consumes it. However, no wolf can enter a cell with a dog.

Initially there are no dogs. Place dogs onto the pasture in such a way that no wolf can reach any sheep, or determine that it is impossible. Note that since you have many dogs, you do not need to minimize their number. 

Input

First line contains two integers R (1 ≤ R ≤ 500) and C (1 ≤ C ≤ 500), denoting the number of rows and the numbers of columns respectively.

Each of the following R lines is a string consisting of exactly C characters, representing one row of the pasture. Here, 'S' means a sheep, 'W' a wolf and '.' an empty cell.

Output

If it is impossible to protect all sheep, output a single line with the word "No".

Otherwise, output a line with the word "Yes". Then print R lines, representing the pasture after placing dogs. Again, 'S' means a sheep, 'W' a wolf, 'D' is a dog and '.' an empty space. You are not allowed to move, remove or add a sheep or a wolf.

If there are multiple solutions, you may print any of them. You don't have to minimize the number of dogs.

Examples

Input

6 6
..S...
..S.W.
.S....
..W...
...W..
......


Output

Yes
..SD..
..SDW.
.SD...
.DW...
DD.W..
......


Input

1 2
SW


Output

No


Input

5 5
.S...
...S.
S....
...S.
.S...


Output

Yes
.S...
...S.
S.D..
...S.
.S...

Note

In the first example, we can split the pasture into two halves, one containing wolves and one containing sheep. Note that the sheep at (2,1) is safe, as wolves cannot move diagonally.

In the second example, there are no empty spots to put dogs that would guard the lone sheep.

In the third example, there are no wolves, so the task is very easy. We put a dog in the center to observe the peacefulness of the meadow, but the solution would be correct even without him.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Real stupidity beats artificial intelligence every time.

— Terry Pratchett, Hogfather, Discworld

You are given a string $s$ of length $n$ and a number $k$. Let's denote by $rev(s)$ the reversed string $s$ (i.e. $rev(s) = s_n s_{n-1} ... s_1$). You can apply one of the two kinds of operations to the string:

replace the string $s$ with $s + rev(s)$

replace the string $s$ with $rev(s) + s$

How many different strings can you get as a result of performing exactly $k$ operations (possibly of different kinds) on the original string $s$?

In this statement we denoted the concatenation of strings $s$ and $t$ as $s + t$. In other words, $s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m$, where $n$ and $m$ are the lengths of strings $s$ and $t$ respectively.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — number of test cases. Next $2 \cdot t$ lines contain $t$ test cases:

The first line of a test case contains two integers $n$ and $k$ ($1 \le n \le 100$, $0 \le k \le 1000$) — the length of the string and the number of operations respectively.

The second string of a test case contains one string $s$ of length $n$ consisting of lowercase Latin letters.


-----Output-----

For each test case, print the answer (that is, the number of different strings that you can get after exactly $k$ operations) on a separate line.

It can be shown that the answer does not exceed $10^9$ under the given constraints.


-----Examples-----

Input
4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab
Output
2
2
1
1


-----Note-----

In the first test case of the example:

After the first operation the string $s$ can become either aabbaa or baaaab. After the second operation there are 2 possibilities for $s$: aabbaaaabbaa and baaaabbaaaab.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ consisting of $n$ integers. In one move, you can jump from the position $i$ to the position $i - a_i$ (if $1 \le i - a_i$) or to the position $i + a_i$ (if $i + a_i \le n$).

For each position $i$ from $1$ to $n$ you want to know the minimum the number of moves required to reach any position $j$ such that $a_j$ has the opposite parity from $a_i$ (i.e. if $a_i$ is odd then $a_j$ has to be even and vice versa).


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the $i$-th element of $a$.


-----Output-----

Print $n$ integers $d_1, d_2, \dots, d_n$, where $d_i$ is the minimum the number of moves required to reach any position $j$ such that $a_j$ has the opposite parity from $a_i$ (i.e. if $a_i$ is odd then $a_j$ has to be even and vice versa) or -1 if it is impossible to reach such a position.


-----Example-----
Input
10
4 5 7 6 7 5 4 4 6 4

Output
1 1 1 2 -1 1 1 3 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ persons who initially don't know each other. On each morning, two of them, who were not friends before, become friends.

We want to plan a trip for every evening of $m$ days. On each trip, you have to select a group of people that will go on the trip. For every person, one of the following should hold:   Either this person does not go on the trip,  Or at least $k$ of his friends also go on the trip. 

Note that the friendship is not transitive. That is, if $a$ and $b$ are friends and $b$ and $c$ are friends, it does not necessarily imply that $a$ and $c$ are friends.

For each day, find the maximum number of people that can go on the trip on that day.


-----Input-----

The first line contains three integers $n$, $m$, and $k$ ($2 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$, $1 \le k < n$) — the number of people, the number of days and the number of friends each person on the trip should have in the group.

The $i$-th ($1 \leq i \leq m$) of the next $m$ lines contains two integers $x$ and $y$ ($1\leq x, y\leq n$, $x\ne y$), meaning that persons $x$ and $y$ become friends on the morning of day $i$. It is guaranteed that $x$ and $y$ were not friends before.


-----Output-----

Print exactly $m$ lines, where the $i$-th of them ($1\leq i\leq m$) contains the maximum number of people that can go on the trip on the evening of the day $i$.


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

Output
0
0
3
3

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

Output
0
0
0
3
3
4
4
5

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

Output
0
0
0
0
3
4
4



-----Note-----

In the first example,   $1,2,3$ can go on day $3$ and $4$. 

In the second example,   $2,4,5$ can go on day $4$ and $5$.  $1,2,4,5$ can go on day $6$ and $7$.  $1,2,3,4,5$ can go on day $8$. 

In the third example,   $1,2,5$ can go on day $5$.  $1,2,3,5$ can go on day $6$ and $7$.

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