vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The purpose of this kata is to work out just how many bottles of duty free whiskey you would have to buy such that the saving over the normal high street price would effectively cover the cost of your holiday. 

You will be given the high street price (normPrice), the duty free discount (discount) and the cost of the holiday. 

For example, if a bottle cost £10 normally and the discount in duty free was 10%, you would save £1 per bottle. If your holiday cost £500, the answer you should return would be 500.

All inputs will be integers. Please return an integer. Round down.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An element in an array is dominant if it is greater than all elements to its right. You will be given an array and your task will be to return a list of all dominant elements. For example:
```Haskell
solve([1,21,4,7,5]) = [21,7,5] because 21, 7 and 5 are greater than elments to their right. 
solve([5,4,3,2,1]) = [5,4,3,2,1]

Notice that the last element is always included.
```

More examples in the test cases.

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ZS the Coder is coding on a crazy computer. If you don't type in a word for a c consecutive seconds, everything you typed disappear! 

More formally, if you typed a word at second a and then the next word at second b, then if b - a ≤ c, just the new word is appended to other words on the screen. If b - a > c, then everything on the screen disappears and after that the word you have typed appears on the screen.

For example, if c = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.

You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.


-----Input-----

The first line contains two integers n and c (1 ≤ n ≤ 100 000, 1 ≤ c ≤ 10^9) — the number of words ZS the Coder typed and the crazy computer delay respectively.

The next line contains n integers t_1, t_2, ..., t_{n} (1 ≤ t_1 < t_2 < ... < t_{n} ≤ 10^9), where t_{i} denotes the second when ZS the Coder typed the i-th word.


-----Output-----

Print a single positive integer, the number of words that remain on the screen after all n words was typed, in other words, at the second t_{n}.


-----Examples-----
Input
6 5
1 3 8 14 19 20

Output
3
Input
6 1
1 3 5 7 9 10

Output
2


-----Note-----

The first sample is already explained in the problem statement.

For the second sample, after typing the first word at the second 1, it disappears because the next word is typed at the second 3 and 3 - 1 > 1. Similarly, only 1 word will remain at the second 9. Then, a word is typed at the second 10, so there will be two words on the screen, as the old word won't disappear because 10 - 9 ≤ 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya decided to go to the grocery store. He found in his wallet $a$ coins of $1$ burle and $b$ coins of $2$ burles. He does not yet know the total cost of all goods, so help him find out $s$ ($s > 0$): the minimum positive integer amount of money he cannot pay without change or pay at all using only his coins.

For example, if $a=1$ and $b=1$ (he has one $1$-burle coin and one $2$-burle coin), then:

he can pay $1$ burle without change, paying with one $1$-burle coin,

he can pay $2$ burle without change, paying with one $2$-burle coin,

he can pay $3$ burle without change by paying with one $1$-burle coin and one $2$-burle coin,

he cannot pay $4$ burle without change (moreover, he cannot pay this amount at all).

So for $a=1$ and $b=1$ the answer is $s=4$.


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The description of each test case consists of one line containing two integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 10^8$) — the number of $1$-burle coins and $2$-burles coins Vasya has respectively.


-----Output-----

For each test case, on a separate line print one integer $s$ ($s > 0$): the minimum positive integer amount of money that Vasya cannot pay without change or pay at all.


-----Examples-----

Input
5
1 1
4 0
0 2
0 0
2314 2374
Output
4
5
1
1
7063


-----Note-----

The first test case of the example is clarified into the main part of the statement.

In the second test case, Vasya has only $1$ burle coins, and he can collect either any amount from $1$ to $4$, but $5$ can't.

In the second test case, Vasya has only $2$ burle coins, and he cannot pay $1$ burle without change.

In the fourth test case you don't have any coins, and he can't even pay $1$ burle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tonio has a keyboard with only two letters, "V" and "K".

One day, he has typed out a string s with only these two letters. He really likes it when the string "VK" appears, so he wishes to change at most one letter in the string (or do no changes) to maximize the number of occurrences of that string. Compute the maximum number of times "VK" can appear as a substring (i. e. a letter "K" right after a letter "V") in the resulting string.


-----Input-----

The first line will contain a string s consisting only of uppercase English letters "V" and "K" with length not less than 1 and not greater than 100.


-----Output-----

Output a single integer, the maximum number of times "VK" can appear as a substring of the given string after changing at most one character.


-----Examples-----
Input
VK

Output
1

Input
VV

Output
1

Input
V

Output
0

Input
VKKKKKKKKKVVVVVVVVVK

Output
3

Input
KVKV

Output
1



-----Note-----

For the first case, we do not change any letters. "VK" appears once, which is the maximum number of times it could appear.

For the second case, we can change the second character from a "V" to a "K". This will give us the string "VK". This has one occurrence of the string "VK" as a substring.

For the fourth case, we can change the fourth character from a "K" to a "V". This will give us the string "VKKVKKKKKKVVVVVVVVVK". This has three occurrences of the string "VK" as a substring. We can check no other moves can give us strictly more occurrences.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your friend Rick is trying to send you a message, but he is concerned that it would get intercepted by his partner. He came up with a solution:

1) Add digits in random places within the message.

2) Split the resulting message in two. He wrote down every second character on one page, and the remaining ones on another. He then dispatched the two messages separately.

Write a function interweave(s1, s2) that reverses this operation to decode his message!

Example 1: interweave("hlo", "el") -> "hello"
Example 2: interweave("h3lo", "el4") -> "hello"

Rick's a bit peculiar about his formats. He would feel ashamed if he found out his message led to extra white spaces hanging around the edges of his message...

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tyrion, son of Tywin was released from the dungeons of vale after his champion Bronn defeated Ser Vardis in the trial by combat.

As a Lannister always pays his debts, he invited Bronn to play a game of mastermind with him.

The game is played as follows:

Tyrion has rocks of 7 colours. (As he is rich, he has infinitely many of each colour)
He makes a sequence of length 10 from these rocks.
The colours are: VIBGYOR (Each letter is associated to corresponding colour)

Now Bronn chooses the number of times he wants to play. (No. of test cases)
Then each time he has to guess a sequence of 10 rocks.
Based on each guess Tyrion rewards Bronn 1 gold coin for a rock which is correct in colour and position both and 1 silver coin for a rock which is correct in colour only.

Input:
The first line contains the secret sequence of Tyrion
The next line contains an integer t, no. of times bronn choses to play.
The next t lines each contain a sequence.

Output:
For each t lines you have to print the number of golds followed by number of silvers.

Eg:

Input:

ROYGBIVVOG

3

VIBGYORROY

RRRRRVVVVV

ROYGBIVVGO

Output:

2 6

3 0

8 2

Input:

IBVIGBVVRV

5

GGVRIOYGRO

YROGVBIOBG

ORYVYBYOOI

BBIRRVVIVV

VRRVOGGGGO

Output:

2 2

1 5

1 3

3 6

0 4

SAMPLE INPUT
ROYGBIVVOG
3
VIBGYORROY
RRRRRVVVVV
ROYGBIVVGO

SAMPLE OUTPUT
2 6
3 0
8 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing a computer game. In this game, you have to fight $n$ monsters.

To defend from monsters, you need a shield. Each shield has two parameters: its current durability $a$ and its defence rating $b$. Each monster has only one parameter: its strength $d$.

When you fight a monster with strength $d$ while having a shield with current durability $a$ and defence $b$, there are three possible outcomes:  if $a = 0$, then you receive $d$ damage;  if $a > 0$ and $d \ge b$, you receive no damage, but the current durability of the shield decreases by $1$;  if $a > 0$ and $d < b$, nothing happens. 

The $i$-th monster has strength $d_i$, and you will fight each of the monsters exactly once, in some random order (all $n!$ orders are equiprobable). You have to consider $m$ different shields, the $i$-th shield has initial durability $a_i$ and defence rating $b_i$. For each shield, calculate the expected amount of damage you will receive if you take this shield and fight the given $n$ monsters in random order.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of monsters and the number of shields, respectively.

The second line contains $n$ integers $d_1$, $d_2$, ..., $d_n$ ($1 \le d_i \le 10^9$), where $d_i$ is the strength of the $i$-th monster.

Then $m$ lines follow, the $i$-th of them contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n$; $1 \le b_i \le 10^9$) — the description of the $i$-th shield.


-----Output-----

Print $m$ integers, where the $i$-th integer represents the expected damage you receive with the $i$-th shield as follows: it can be proven that, for each shield, the expected damage is an irreducible fraction $\dfrac{x}{y}$, where $y$ is coprime with $998244353$. You have to print the value of $x \cdot y^{-1} \bmod 998244353$, where $y^{-1}$ is the inverse element for $y$ ($y \cdot y^{-1} \bmod 998244353 = 1$).


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

Output
665496237
1

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

Output
0
8
665496236

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Chilly Willy loves playing with numbers. He only knows prime numbers that are digits yet. These numbers are 2, 3, 5 and 7. But Willy grew rather bored of such numbers, so he came up with a few games that were connected with them.

Chilly Willy wants to find the minimum number of length *n*, such that it is simultaneously divisible by all numbers Willy already knows (2, 3, 5 and 7). Help him with that.

A number's length is the number of digits in its decimal representation without leading zeros.

Input Specification:
A single input line contains a single integer *n* (1<=≤<=*n*<=≤<=105).

Output Specification:
Print a single integer — the answer to the problem without leading zeroes, or "-1" (without the quotes), if the number that meet the problem condition does not exist.

Demo Input:
['1\n', '5\n']

Demo Output:
['-1\n', '10080']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an $n$-by-$n$ grid where each square is colored either black or white. A grid is correct if all of the following conditions are satisfied:
 - Every row has the same number of black squares as it has white squares.
 - Every column has the same number of black squares as it has white squares.
 - No row or column has $3$ or more consecutive squares of the same color.

Given a grid, determine whether it is correct.

-----Input-----
The first line contains an integer $n$ ($2\le n\le 24$; $n$ is even). Each of the next $n$ lines contains a string of length $n$ consisting solely of the characters ‘B’ and ‘W’, representing the colors of the grid squares.

-----Output-----
If the grid is correct, print the number $1$ on a single line. Otherwise, print the number $0$ on a single line.

-----Examples-----
Sample Input 1:
4
WBBW
WBWB
BWWB
BWBW
Sample Output 1:
1

Sample Input 2:
4
BWWB
BWBB
WBBW
WBWW
Sample Output 2:
0

Sample Input 3:
6
BWBWWB
WBWBWB
WBBWBW
BBWBWW
BWWBBW
WWBWBB
Sample Output 3:
0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
John has just bought a new car and is planning a journey around the country. Country has *N* cities, some of which are connected by bidirectional roads. There are *N*<=-<=1 roads and every city is reachable from any other city. Cities are labeled from 1 to *N*.

John first has to select from which city he will start his journey. After that, he spends one day in a city and then travels to a randomly choosen city which is directly connected to his current one and which he has not yet visited. He does this until he can't continue obeying these rules.

To select the starting city, he calls his friend Jack for advice. Jack is also starting a big casino business and wants to open casinos in some of the cities (max 1 per city, maybe nowhere). Jack knows John well and he knows that if he visits a city with a casino, he will gamble exactly once before continuing his journey.

He also knows that if John enters a casino in a good mood, he will leave it in a bad mood and vice versa. Since he is John's friend, he wants him to be in a good mood at the moment when he finishes his journey. John is in a good mood before starting the journey.

In how many ways can Jack select a starting city for John and cities where he will build casinos such that no matter how John travels, he will be in a good mood at the end? Print answer modulo 109<=+<=7.

Input Specification:
In the first line, a positive integer *N* (1<=≤<=*N*<=≤<=100000), the number of cities. 

In the next *N*<=-<=1 lines, two numbers *a*,<= *b* (1<=≤<=*a*,<=*b*<=≤<=*N*) separated by a single space meaning that cities *a* and *b* are connected by a bidirectional road.

Output Specification:
Output one number, the answer to the problem modulo 109<=+<=7.

Demo Input:
['2\n1 2\n', '3\n1 2\n2 3\n']

Demo Output:
['4\n', '10\n']

Note:
Example 1: If Jack selects city 1 as John's starting city, he can either build 0 casinos, so John will be happy all the time, or build a casino in both cities, so John would visit a casino in city 1, become unhappy, then go to city 2, visit a casino there and become happy and his journey ends there because he can't go back to city 1. If Jack selects city 2 for start, everything is symmetrical, so the answer is 4.

Example 2: If Jack tells John to start from city 1, he can either build casinos in 0 or 2 cities (total 4 possibilities). If he tells him to start from city 2, then John's journey will either contain cities 2 and 1 or 2 and 3. Therefore, Jack will either have to build no casinos, or build them in all three cities. With other options, he risks John ending his journey unhappy. Starting from 3 is symmetric to starting from 1, so in total we have 4 + 2 + 4 = 10 options.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
J: Horizontal-Vertical Permutation

Problem Statement

You are given a positive integer N. Your task is to determine if there exists a square matrix A whose dimension is N that satisfies the following conditions and provide an example of such matrices if it exists. A_{i, j} denotes the element of matrix A at the i-th row and j-th column.

* For all i, j (1 \leq i, j \leq N), A_{i, j} is an integer that satisfies 1 \leq A_{i, j} \leq 2N - 1.
* For all k = 1, 2, ..., N, a set consists of 2N - 1 elements from the k-th row or k-th column is \\{1, 2, ..., 2N - 1\\}.



If there are more than one possible matrices, output any of them.

Input


N

Input consists of one line, which contains the integer N that is the size of a square matrix to construct.

Constraint

* N is an integer that satisfies 1 \leq N \leq 500.



Output

Output `No` in a single line if such a square matrix does not exist.

If such a square matrix A exists, output `Yes` on the first line and A after that. More specifically, follow the following format.


Yes
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
:
A_{N, 1} A_{N, 2} ... A_{N, N}


Sample Input 1


4

Output for Sample Input 1


Yes
2 6 3 7
4 5 2 1
1 7 5 6
5 3 4 2


Sample Input 2


3

Output for Sample Input 2


No





Example

Input

4


Output

Yes
2 6 3 7
4 5 2 1
1 7 5 6
5 3 4 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
— Hey folks, how do you like this problem?

— That'll do it. 

BThero is a powerful magician. He has got $n$ piles of candies, the $i$-th pile initially contains $a_i$ candies. BThero can cast a copy-paste spell as follows:   He chooses two piles $(i, j)$ such that $1 \le i, j \le n$ and $i \ne j$.  All candies from pile $i$ are copied into pile $j$. Formally, the operation $a_j := a_j + a_i$ is performed. 

BThero can cast this spell any number of times he wants to — but unfortunately, if some pile contains strictly more than $k$ candies, he loses his magic power. What is the maximum number of times BThero can cast the spell without losing his power?


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 500$) — the number of test cases.

Each test case consists of two lines:   the first line contains two integers $n$ and $k$ ($2 \le n \le 1000$, $2 \le k \le 10^4$);  the second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le k$). 

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$, and the sum of $k$ over all test cases does not exceed $10^4$.


-----Output-----

For each test case, print one integer — the maximum number of times BThero can cast the spell without losing his magic power.


-----Example-----
Input
3
2 2
1 1
3 5
1 2 3
3 7
3 2 2

Output
1
5
4



-----Note-----

In the first test case we get either $a = [1, 2]$ or $a = [2, 1]$ after casting the spell for the first time, and it is impossible to cast it again.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently a new building with a new layout was constructed in Monocarp's hometown. According to this new layout, the building consists of three types of apartments: three-room, five-room, and seven-room apartments. It's also known that each room of each apartment has exactly one window. In other words, a three-room apartment has three windows, a five-room — five windows, and a seven-room — seven windows.

Monocarp went around the building and counted $n$ windows. Now he is wondering, how many apartments of each type the building may have.

Unfortunately, Monocarp only recently has learned to count, so he is asking you to help him to calculate the possible quantities of three-room, five-room, and seven-room apartments in the building that has $n$ windows. If there are multiple answers, you can print any of them.

Here are some examples:

  if Monocarp has counted $30$ windows, there could have been $2$ three-room apartments, $2$ five-room apartments and $2$ seven-room apartments, since $2 \cdot 3 + 2 \cdot 5 + 2 \cdot 7 = 30$;  if Monocarp has counted $67$ windows, there could have been $7$ three-room apartments, $5$ five-room apartments and $3$ seven-room apartments, since $7 \cdot 3 + 5 \cdot 5 + 3 \cdot 7 = 67$;  if Monocarp has counted $4$ windows, he should have mistaken since no building with the aforementioned layout can have $4$ windows. 


-----Input-----

Th first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The only line of each test case contains one integer $n$ ($1 \le n \le 1000$) — the number of windows in the building.


-----Output-----

For each test case, if a building with the new layout and the given number of windows just can't exist, print $-1$.

Otherwise, print three non-negative integers — the possible number of three-room, five-room, and seven-room apartments. If there are multiple answers, print any of them.


-----Example-----
Input
4
30
67
4
14

Output
2 2 2
7 5 3
-1
0 0 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Vasya loves orange juice very much. That's why any food and drink in his kitchen necessarily contains orange juice. There are n drinks in his fridge, the volume fraction of orange juice in the i-th drink equals pi percent.

One day Vasya decided to make himself an orange cocktail. He took equal proportions of each of the n drinks and mixed them. Then he wondered, how much orange juice the cocktail has.

Find the volume fraction of orange juice in the final drink.

Input

The first input line contains a single integer n (1 ≤ n ≤ 100) — the number of orange-containing drinks in Vasya's fridge. The second line contains n integers pi (0 ≤ pi ≤ 100) — the volume fraction of orange juice in the i-th drink, in percent. The numbers are separated by a space.

Output

Print the volume fraction in percent of orange juice in Vasya's cocktail. The answer will be considered correct if the absolute or relative error does not exceed 10  - 4.

Examples

Input

3
50 50 100


Output

66.666666666667


Input

4
0 25 50 75


Output

37.500000000000

Note

Note to the first sample: let's assume that Vasya takes x milliliters of each drink from the fridge. Then the volume of pure juice in the cocktail will equal <image> milliliters. The total cocktail's volume equals 3·x milliliters, so the volume fraction of the juice in the cocktail equals <image>, that is, 66.(6) percent.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Similar setting of the [previous](https://www.codewars.com/kata/progressive-spiral-number-position/), this time you are called to identify in which "branch" of the spiral a given number will end up.

Considering a square of numbers disposed as the 25 items in [the previous kata](https://www.codewars.com/kata/progressive-spiral-number-position/), the branch are numbered as it follows:

```
17 16 15 14 13    1 1 1 1 0
18 05 04 03 12    2 1 1 0 0
19 06 01 02 11 => 2 2 0 0 0
20 07 08 09 10    2 2 3 3 0
21 22 23 24 25    2 3 3 3 3
```

Meaning that, for example, numbers in the `10-13` range will be in branch `0`, numbers in the range `14-17` are inside branch `1`, all those nice numbers in the `18-21` can call branch `2` their house and finally the `21-25` team all falls under the `3` branch.

Your function must return the number of the index of each number [`1` being a special case you might consider equivalent to being in the first branch, `0`], as per examples:

```python
branch(1) == 0 #kind of special case here
branch(5) == 1
branch(25) == 3
branch(30) == 0
branch(50) == 0
```

It might help A LOT to both solve the [previous kata](https://www.codewars.com/kata/progressive-spiral-number-position/) and to visualize the diagonals of the square. Be ready for big numbers and, as usual, inspired by [AoC](http://adventofcode.com/2017/day/3). Finally, when ready, go to compute [the distance](https://www.codewars.com/kata/progressive-spiral-number-distance/) of the series.

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