vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Chef wants to make a feast. In order to do that, he needs a lot of different ingredients. Each ingredient has a certain tastiness; the tastiness of each ingredient may be any positive integer. Initially, for each tastiness between $K$ and $K+N-1$ (inclusive), Chef has an infinite supply of ingredients with this tastiness.
The ingredients have a special property: any two of them can be mixed to create a new ingredient. If the original ingredients had tastiness $x$ and $y$ (possibly $x = y$), the new ingredient has tastiness $x+y$. The ingredients created this way may be used to mix other ingredients as well. Chef is free to mix ingredients in any way he chooses any number of times.
Let's call a tastiness $v$ ($v > 0$) unreachable if there is no way to obtain an ingredient with tastiness $v$; otherwise, tastiness $v$ is reachable. Chef wants to make ingredients with all reachable values of tastiness and he would like to know the number of unreachable values. Help him solve this problem. Since the answer may be large, compute it modulo $1,000,000,007$ ($10^9+7$).
Note that there is an infinite number of reachable values of tastiness, but it can be proven that the number of unreachable values is always finite for $N \ge 2$.

-----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 and only line of each test case contains two space-separated integers $N$ and $K$.

-----Output-----
For each test case, print a single line containing one integer — the number of unreachable values of tastiness, modulo $1,000,000,007$.

-----Constraints-----
- $1 \le T \le 10^5$
- $2 \le N \le 10^{18}$
- $1 \le K \le 10^{18}$

-----Subtasks-----
Subtask #1 (20 points): $N = 2$
Subtask #2 (80 points): original constraints

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

-----Example Output-----
0
2

-----Explanation-----
Example case 1: It is possible to obtain ingredients with all values of tastiness.
Example case 2: Ingredients with tastiness $1$ and $2$ cannot be made.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given string s consists of opening and closing brackets of four kinds <>, {}, [], (). There are two types of brackets: opening and closing. You can replace any bracket by another of the same type. For example, you can replace < by the bracket {, but you can't replace it by ) or >.

The following definition of a regular bracket sequence is well-known, so you can be familiar with it.

Let's define a regular bracket sequence (RBS). Empty string is RBS. Let s1 and s2 be a RBS then the strings <s1>s2, {s1}s2, [s1]s2, (s1)s2 are also RBS.

For example the string "[[(){}]<>]" is RBS, but the strings "[)()" and "][()()" are not.

Determine the least number of replaces to make the string s RBS.

Input

The only line contains a non empty string s, consisting of only opening and closing brackets of four kinds. The length of s does not exceed 106.

Output

If it's impossible to get RBS from s print Impossible.

Otherwise print the least number of replaces needed to get RBS from s.

Examples

Input

[&lt;}){}


Output

2

Input

{()}[]


Output

0

Input

]]


Output

Impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Help Far Away Kingdom

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
In a far away kingdom lived the King, the Prince, the Shoemaker, the Dressmaker and many other citizens. They lived happily until great trouble came into the Kingdom. The ACMers settled there.

Most damage those strange creatures inflicted upon the kingdom was that they loved high precision numbers. As a result, the Kingdom healers had already had three appointments with the merchants who were asked to sell, say, exactly 0.273549107 beer barrels. To deal with the problem somehow, the King issued an order obliging rounding up all numbers to the closest integer to simplify calculations. Specifically, the order went like this:
-  If a number's integer part does not end with digit 9 and its fractional part is strictly less than 0.5, then the rounded up number coincides with the number’s integer part. -  If a number's integer part does not end with digit 9 and its fractional part is not less than 0.5, the rounded up number is obtained if we add 1 to the last digit of the number’s integer part.-  If the number’s integer part ends with digit 9, to round up the numbers one should go to Vasilisa the Wise. In the whole Kingdom she is the only one who can perform the tricky operation of carrying into the next position. 
Merchants found the algorithm very sophisticated and they asked you (the ACMers) to help them. Can you write a program that would perform the rounding according to the King’s order?

Input Specification:
The first line contains a single number to round up — the integer part (a non-empty set of decimal digits that do not start with 0 — with the exception of a case when the set consists of a single digit — in this case 0 can go first), then follows character «.» (a dot), and then follows the fractional part (any non-empty set of decimal digits). The number's length does not exceed 1000 characters, including the dot. There are no other characters in the input data.

Output Specification:
If the last number of the integer part is not equal to 9, print the rounded-up number without leading zeroes. Otherwise, print the message "GOTO Vasilisa." (without the quotes).

Demo Input:
['0.0\n', '1.49\n', '1.50\n', '2.71828182845904523536\n', '3.14159265358979323846\n', '12345678901234567890.1\n', '123456789123456789.999\n']

Demo Output:
['0', '1', '2', '3', '3', '12345678901234567890', 'GOTO Vasilisa.']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Simon and Antisimon play a game. Initially each player receives one fixed positive integer that doesn't change throughout the game. Simon receives number *a* and Antisimon receives number *b*. They also have a heap of *n* stones. The players take turns to make a move and Simon starts. During a move a player should take from the heap the number of stones equal to the greatest common divisor of the fixed number he has received and the number of stones left in the heap. A player loses when he cannot take the required number of stones (i. e. the heap has strictly less stones left than one needs to take). 

Your task is to determine by the given *a*, *b* and *n* who wins the game.

Input Specification:
The only string contains space-separated integers *a*, *b* and *n* (1<=≤<=*a*,<=*b*,<=*n*<=≤<=100) — the fixed numbers Simon and Antisimon have received correspondingly and the initial number of stones in the pile.

Output Specification:
If Simon wins, print "0" (without the quotes), otherwise print "1" (without the quotes).

Demo Input:
['3 5 9\n', '1 1 100\n']

Demo Output:
['0', '1']

Note:
The greatest common divisor of two non-negative integers *a* and *b* is such maximum positive integer *k*, that *a* is divisible by *k* without remainder and similarly, *b* is divisible by *k* without remainder. Let *gcd*(*a*, *b*) represent the operation of calculating the greatest common divisor of numbers *a* and *b*. Specifically, *gcd*(*x*, 0) = *gcd*(0, *x*) = *x*.

In the first sample the game will go like that:
-  Simon should take *gcd*(3, 9) = 3 stones from the heap. After his move the heap has 6 stones left.-  Antisimon should take *gcd*(5, 6) = 1 stone from the heap. After his move the heap has 5 stones left.-  Simon should take *gcd*(3, 5) = 1 stone from the heap. After his move the heap has 4 stones left.-  Antisimon should take *gcd*(5, 4) = 1 stone from the heap. After his move the heap has 3 stones left.-  Simon should take *gcd*(3, 3) = 3 stones from the heap. After his move the heap has 0 stones left.-  Antisimon should take *gcd*(5, 0) = 5 stones from the heap. As 0 &lt; 5, it is impossible and Antisimon loses.
In the second sample each player during each move takes one stone from the heap. As *n* is even, Antisimon takes the last stone and Simon can't make a move after that.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Points, Lines and Ready-made Titles

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given *n* distinct points on a plane with integral coordinates. For each point you can either draw a vertical line through it, draw a horizontal line through it, or do nothing.

You consider several coinciding straight lines as a single one. How many distinct pictures you can get? Print the answer modulo 109<=+<=7.

Input Specification:
The first line contains single integer *n* (1<=≤<=*n*<=≤<=105) — the number of points.

*n* lines follow. The (*i*<=+<=1)-th of these lines contains two integers *x**i*, *y**i* (<=-<=109<=≤<=*x**i*,<=*y**i*<=≤<=109) — coordinates of the *i*-th point.

It is guaranteed that all points are distinct.

Output Specification:
Print the number of possible distinct pictures modulo 109<=+<=7.

Demo Input:
['4\n1 1\n1 2\n2 1\n2 2\n', '2\n-1 -1\n0 1\n']

Demo Output:
['16\n', '9\n']

Note:
In the first example there are two vertical and two horizontal lines passing through the points. You can get pictures with any subset of these lines. For example, you can get the picture containing all four lines in two ways (each segment represents a line containing it).

In the second example you can work with two points independently. The number of pictures is 3<sup class="upper-index">2</sup> = 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation of length $n$ is an array $p=[p_1,p_2,\dots,p_n]$, which contains every integer from $1$ to $n$ (inclusive) and, moreover, each number appears exactly once. For example, $p=[3,1,4,2,5]$ is a permutation of length $5$.

For a given number $n$ ($n \ge 2$), find a permutation $p$ in which absolute difference (that is, the absolute value of difference) of any two neighboring (adjacent) elements is between $2$ and $4$, inclusive. Formally, find such permutation $p$ that $2 \le |p_i - p_{i+1}| \le 4$ for each $i$ ($1 \le i < n$).

Print any such permutation for the given integer $n$ or determine that it does not exist.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases in the input. Then $t$ test cases follow.

Each test case is described by a single line containing an integer $n$ ($2 \le n \le 1000$).


-----Output-----

Print $t$ lines. Print a permutation that meets the given requirements. If there are several such permutations, then print any of them. If no such permutation exists, print -1.


-----Example-----
Input
6
10
2
4
6
7
13

Output
9 6 10 8 4 7 3 1 5 2 
-1
3 1 4 2 
5 3 6 2 4 1 
5 1 3 6 2 4 7 
13 9 7 11 8 4 1 3 5 2 6 10 12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ayush, Ashish and Vivek are busy preparing a new problem for the next Codeforces round and need help checking if their test cases are valid.

Each test case consists of an integer $n$ and two arrays $a$ and $b$, of size $n$. If after some (possibly zero) operations described below, array $a$ can be transformed into array $b$, the input is said to be valid. Otherwise, it is invalid.

An operation on array $a$ is:   select an integer $k$ $(1 \le k \le \lfloor\frac{n}{2}\rfloor)$  swap the prefix of length $k$ with the suffix of length $k$ 

For example, if array $a$ initially is $\{1, 2, 3, 4, 5, 6\}$, after performing an operation with $k = 2$, it is transformed into $\{5, 6, 3, 4, 1, 2\}$.

Given the set of test cases, help them determine if each one is valid or invalid.


-----Input-----

The first line contains one integer $t$ $(1 \le t \le 500)$ — the number of test cases. The description of each test case is as follows.

The first line of each test case contains a single integer $n$ $(1 \le n \le 500)$ — the size of the arrays.

The second line of each test case contains $n$ integers $a_1$, $a_2$, ..., $a_n$ $(1 \le a_i \le 10^9)$ — elements of array $a$.

The third line of each test case contains $n$ integers $b_1$, $b_2$, ..., $b_n$ $(1 \le b_i \le 10^9)$ — elements of array $b$.


-----Output-----

For each test case, print "Yes" if the given input is valid. Otherwise print "No".

You may print the answer in any case.


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

Output
yes
yes
No
yes
No



-----Note-----

For the first test case, we can swap prefix $a[1:1]$ with suffix $a[2:2]$ to get $a=[2, 1]$.

For the second test case, $a$ is already equal to $b$.

For the third test case, it is impossible since we cannot obtain $3$ in $a$.

For the fourth test case, we can first swap prefix $a[1:1]$ with suffix $a[4:4]$ to obtain $a=[2, 2, 3, 1]$. Now we can swap prefix $a[1:2]$ with suffix $a[3:4]$ to obtain $a=[3, 1, 2, 2]$.

For the fifth test case, it is impossible to convert $a$ to $b$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's say take 2 strings, A and B, and define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings `abc` and `abd` is 2, while the similarity of strings `aaa` and `aaab` is 3.

write a function that calculates the sum of similarities of a string S with each of it's **suffixes**.

```python
string_suffix('ababaa') => returns 11
string_suffix('abc') => returns 3
```

Explanation:

In the first case, the suffixes of the string are `ababaa`, `babaa`, `abaa`, `baa`, `aa` and `a`. The similarities of each of these strings with the string `ababaa` are 6,0,3,0,1,1 respectively. Thus the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.

For the second case, the answer is simply 3 + 0 + 0 = 3.

Note : Each string will have at least one character - no need to check for empty strings :)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Being educated in Computer Science and Mathematics is not always easy. Especially not if you have “friends” who repeatedly insist on showing you their new “proofs” that P equals NP, that the Riemann Hypothesis is true, and so on.

One of your friends recently claims to have found a fantastic new compression algorithm. As an example of its amazing performance, your friend has told you that every file in your precious collection of random bit strings after compression would be at most $b$ bits long! Naturally, you find this a bit hard to believe, so you want to determine whether it is even theoretically possible for this to be true.

Your collection of random bit strings consists of $N$ files, no two of which are identical, and each of which is exactly $1000$ bits long.

-----Input-----
The input consists of two integers $N$ ($1 \le N \le 10^{15}$) and $b$ ($0 \le b \le 50$), giving the number of files in your collection and the maximum number of bits a compressed file is allowed to have.

-----Output-----
Output a line containing either “yes” if it is possible to compress all the $N$ files in your collection into files of size at most $b$ bits, or “no” otherwise.

-----Examples-----
Sample Input 1:
13 3
Sample Output 1:
yes

Sample Input 2:
1 0
Sample Output 2:
yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An e-commerce startup pitches to the investors to get funding. They have been functional for n weeks now and also have a website!

For each week they know the number of unique visitors during this week vi and the revenue ci. To evaluate the potential of the startup at some range of weeks from l to r inclusive investors use the minimum among the maximum number of visitors multiplied by 100 and the minimum revenue during this period, that is: 

<image>

The truth is that investors have no idea how to efficiently evaluate the startup, so they are going to pick some k random distinct weeks li and give them to managers of the startup. For each li they should pick some ri ≥ li and report maximum number of visitors and minimum revenue during this period.

Then, investors will calculate the potential of the startup for each of these ranges and take minimum value of p(li, ri) as the total evaluation grade of the startup. Assuming that managers of the startup always report the optimal values of ri for some particular li, i.e., the value such that the resulting grade of the startup is maximized, what is the expected resulting grade of the startup? 

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 1 000 000).

The second line contains n integers vi (1 ≤ vi ≤ 107) — the number of unique visitors during each week.

The third line contains n integers ci (1 ≤ ci ≤ 107) —the revenue for each week.

Output

Print a single real value — the expected grade of the startup. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6. 

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

Examples

Input

3 2
3 2 1
300 200 300


Output

133.3333333

Note

Consider the first sample.

If the investors ask for li = 1 onwards, startup will choose ri = 1, such that max number of visitors is 3 and minimum revenue is 300. Thus, potential in this case is min(3·100, 300) = 300.

If the investors ask for li = 2 onwards, startup will choose ri = 3, such that max number of visitors is 2 and minimum revenue is 200. Thus, potential in this case is min(2·100, 200) = 200.

If the investors ask for li = 3 onwards, startup will choose ri = 3, such that max number of visitors is 1 and minimum revenue is 300. Thus, potential in this case is min(1·100, 300) = 100.

We have to choose a set of size 2 equi-probably and take minimum of each. The possible sets here are : {200, 300},{100, 300},{100, 200}, effectively the set of possible values as perceived by investors equi-probably: {200, 100, 100}. Thus, the expected value is (100 + 200 + 100) / 3 = 133.(3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I always thought that my old friend John was rather richer than he looked, but I never knew exactly how much money he actually had. One day (as I was plying him with questions) he said:

* "Imagine I have between `m` and `n` Zloty..." (or did he say Quetzal? I can't remember!)
* "If I were to buy **9** cars costing `c` each, I'd only have 1 Zloty (or was it Meticals?) left."
* "And if I were to buy **7** boats at `b` each, I'd only have 2 Ringglets (or was it Zloty?) left."

Could you tell me in each possible case:

1. how much money `f` he could possibly have ?
2. the cost `c` of a car?
3. the cost `b` of a boat?

So, I will have a better idea about his fortune. Note that if `m-n` is big enough, you might have a lot of possible answers. 

Each answer should be given as `["M: f", "B: b", "C: c"]` and all the answers as `[ ["M: f", "B: b", "C: c"], ... ]`. "M" stands for money, "B" for boats, "C" for cars.

**Note:** `m, n, f, b, c` are positive integers, where `0 <= m <= n` or `m >= n >= 0`. `m` and `n` are inclusive.


## Examples:
```
howmuch(1, 100)      => [["M: 37", "B: 5", "C: 4"], ["M: 100", "B: 14", "C: 11"]]
howmuch(1000, 1100)  => [["M: 1045", "B: 149", "C: 116"]]
howmuch(10000, 9950) => [["M: 9991", "B: 1427", "C: 1110"]]
howmuch(0, 200)      => [["M: 37", "B: 5", "C: 4"], ["M: 100", "B: 14", "C: 11"], ["M: 163", "B: 23", "C: 18"]]
```

Explanation of the results for `howmuch(1, 100)`:

* In the first answer his possible fortune is **37**:
 * so he can buy 7 boats each worth 5: `37 - 7 * 5 = 2`
 * or he can buy 9 cars worth 4 each: `37 - 9 * 4 = 1`
* The second possible answer is **100**:
 * he can buy 7 boats each worth 14: `100 - 7 * 14 = 2`
 * or he can buy 9 cars worth 11: `100 - 9 * 11 = 1`

# Note
See "Sample Tests" to know the format of the return.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ houses along the road where Anya lives, each one is painted in one of $k$ possible colors.

Anya likes walking along this road, but she doesn't like when two adjacent houses at the road have the same color. She wants to select a long segment of the road such that no two adjacent houses have the same color.

Help Anya find the longest segment with this property.


-----Input-----

The first line contains two integers $n$ and $k$ — the number of houses and the number of colors ($1 \le n \le 100\,000$, $1 \le k \le 100\,000$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ — the colors of the houses along the road ($1 \le a_i \le k$).


-----Output-----

Output a single integer — the maximum number of houses on the road segment having no two adjacent houses of the same color.


-----Example-----
Input
8 3
1 2 3 3 2 1 2 2

Output
4



-----Note-----

In the example, the longest segment without neighboring houses of the same color is from the house 4 to the house 7. The colors of the houses are $[3, 2, 1, 2]$ and its length is 4 houses.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yura has been walking for some time already and is planning to return home. He needs to get home as fast as possible. To do this, Yura can use the instant-movement locations around the city.

Let's represent the city as an area of $n \times n$ square blocks. Yura needs to move from the block with coordinates $(s_x,s_y)$ to the block with coordinates $(f_x,f_y)$. In one minute Yura can move to any neighboring by side block; in other words, he can move in four directions. Also, there are $m$ instant-movement locations in the city. Their coordinates are known to you and Yura. Yura can move to an instant-movement location in no time if he is located in a block with the same coordinate $x$ or with the same coordinate $y$ as the location.

Help Yura to find the smallest time needed to get home.


-----Input-----

The first line contains two integers $n$ and $m$ — the size of the city and the number of instant-movement locations ($1 \le n \le 10^9$, $0 \le m \le 10^5$).

The next line contains four integers $s_x$ $s_y$ $f_x$ $f_y$ — the coordinates of Yura's initial position and the coordinates of his home ($ 1 \le s_x, s_y, f_x, f_y \le n$).

Each of the next $m$ lines contains two integers $x_i$ $y_i$ — coordinates of the $i$-th instant-movement location ($1 \le x_i, y_i \le n$).


-----Output-----

In the only line print the minimum time required to get home.


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

Output
5

Input
84 5
67 59 41 2
39 56
7 2
15 3
74 18
22 7

Output
42



-----Note-----

In the first example Yura needs to reach $(5, 5)$ from $(1, 1)$. He can do that in $5$ minutes by first using the second instant-movement location (because its $y$ coordinate is equal to Yura's $y$ coordinate), and then walking $(4, 1) \to (4, 2) \to (4, 3) \to (5, 3) \to (5, 4) \to (5, 5)$.

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