vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
One of Timofey's birthday presents is a colourbook in a shape of an infinite plane. On the plane n rectangles with sides parallel to coordinate axes are situated. All sides of the rectangles have odd length. Rectangles cannot intersect, but they can touch each other.

Help Timofey to color his rectangles in 4 different colors in such a way that every two rectangles touching each other by side would have different color, or determine that it is impossible.

Two rectangles intersect if their intersection has positive area. Two rectangles touch by sides if there is a pair of sides such that their intersection has non-zero length [Image] The picture corresponds to the first example 


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 5·10^5) — the number of rectangles.

n lines follow. The i-th of these lines contains four integers x_1, y_1, x_2 and y_2 ( - 10^9 ≤ x_1 < x_2 ≤ 10^9,  - 10^9 ≤ y_1 < y_2 ≤ 10^9), that means that points (x_1, y_1) and (x_2, y_2) are the coordinates of two opposite corners of the i-th rectangle.

It is guaranteed, that all sides of the rectangles have odd lengths and rectangles don't intersect each other.


-----Output-----

Print "NO" in the only line if it is impossible to color the rectangles in 4 different colors in such a way that every two rectangles touching each other by side would have different color.

Otherwise, print "YES" in the first line. Then print n lines, in the i-th of them print single integer c_{i} (1 ≤ c_{i} ≤ 4) — the color of i-th rectangle.


-----Example-----
Input
8
0 0 5 3
2 -1 5 0
-3 -4 2 -1
-1 -1 2 0
-3 0 0 5
5 2 10 3
7 -3 10 2
4 -2 7 -1

Output
YES
1
2
2
3
2
2
4
1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera conducts experiments with algorithms that search for shortest paths. He has recently studied the Floyd's algorithm, so it's time to work with it.

Valera's already written the code that counts the shortest distance between any pair of vertexes in a non-directed connected graph from *n* vertexes and *m* edges, containing no loops and multiple edges. Besides, Valera's decided to mark part of the vertexes. He's marked exactly *k* vertexes *a*1,<=*a*2,<=...,<=*a**k*.

Valera's code is given below.

Valera has seen that his code is wrong. Help the boy. Given the set of marked vertexes *a*1,<=*a*2,<=...,<=*a**k*, find such non-directed connected graph, consisting of *n* vertexes and *m* edges, for which Valera's code counts the wrong shortest distance for at least one pair of vertexes (*i*,<=*j*). Valera is really keen to get a graph without any loops and multiple edges. If no such graph exists, print -1.

Input Specification:
The first line of the input contains three integers *n*,<=*m*,<=*k* (3<=≤<=*n*<=≤<=300, 2<=≤<=*k*<=≤<=*n* , ) — the number of vertexes, the number of edges and the number of marked vertexes. 

The second line of the input contains *k* space-separated integers *a*1,<=*a*2,<=... *a**k* (1<=≤<=*a**i*<=≤<=*n*) — the numbers of the marked vertexes. It is guaranteed that all numbers *a**i* are distinct.

Output Specification:
If the graph doesn't exist, print -1 on a single line. Otherwise, print *m* lines, each containing two integers *u*,<=*v* — the description of the edges of the graph Valera's been looking for.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a graph with 3 ⋅ n vertices and m edges. You are to find a matching of n edges, or an independent set of n vertices.

A set of edges is called a matching if no two edges share an endpoint.

A set of vertices is called an independent set if no two vertices are connected with an edge.

Input

The first line contains a single integer T ≥ 1 — the number of graphs you need to process. The description of T graphs follows.

The first line of description of a single graph contains two integers n and m, where 3 ⋅ n is the number of vertices, and m is the number of edges in the graph (1 ≤ n ≤ 10^{5}, 0 ≤ m ≤ 5 ⋅ 10^{5}).

Each of the next m lines contains two integers v_i and u_i (1 ≤ v_i, u_i ≤ 3 ⋅ n), meaning that there is an edge between vertices v_i and u_i.

It is guaranteed that there are no self-loops and no multiple edges in the graph.

It is guaranteed that the sum of all n over all graphs in a single test does not exceed 10^{5}, and the sum of all m over all graphs in a single test does not exceed 5 ⋅ 10^{5}.

Output

Print your answer for each of the T graphs. Output your answer for a single graph in the following format.

If you found a matching of size n, on the first line print "Matching" (without quotes), and on the second line print n integers — the indices of the edges in the matching. The edges are numbered from 1 to m in the input order.

If you found an independent set of size n, on the first line print "IndSet" (without quotes), and on the second line print n integers — the indices of the vertices in the independent set.

If there is no matching and no independent set of the specified size, print "Impossible" (without quotes).

You can print edges and vertices in any order.

If there are several solutions, print any. In particular, if there are both a matching of size n, and an independent set of size n, then you should print exactly one of such matchings or exactly one of such independent sets.

Example

Input


4
1 2
1 3
1 2
1 2
1 3
1 2
2 5
1 2
3 1
1 4
5 1
1 6
2 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6


Output


Matching
2
IndSet
1
IndSet
2 4
Matching
1 15

Note

The first two graphs are same, and there are both a matching of size 1 and an independent set of size 1. Any of these matchings and independent sets is a correct answer.

The third graph does not have a matching of size 2, however, there is an independent set of size 2. Moreover, there is an independent set of size 5: 2 3 4 5 6. However such answer is not correct, because you are asked to find an independent set (or matching) of size exactly n.

The fourth graph does not have an independent set of size 2, but there is a matching of size 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an string of binary number n. The task is to convert binary fractional n into its decimal equivalent.
 
Example 1:
Input:
n = 110.101
Output:
6.625
Explanation:
The given binary String is equivalent
to (6.625)_{10}
Example 2:
Input:
n = 101.1101
Output:
5.8125
Explanation:
The given binary String is equivalent
to (5.8125)_{10}
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function convertToDecimal() which takes an String n as input and returns the answer.
 
Expected Time Complexity: O(|n|)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= |n| <= 50

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The central dogma of molecular biology is that DNA is transcribed into RNA, which is then tranlsated into protein. RNA, like DNA, is a long strand of nucleic acids held together by a sugar backbone (ribose in this case). Each segment of three bases is called a codon. Molecular machines called ribosomes translate the RNA codons into amino acid chains, called polypeptides which are then folded into a protein. 

Protein sequences are easily visualized in much the same way that DNA and RNA are, as large strings of letters. An important thing to note is that the 'Stop' codons do not encode for a specific amino acid. Their only function is to stop translation of the protein, as such they are not incorporated into the polypeptide chain. 'Stop' codons should not be in the final protein sequence. To save a you a lot of unnecessary (and boring) typing the keys and values for your amino acid dictionary are provided.
                         
Given a string of RNA, create a funciton which translates the RNA into its protein sequence. Note: the test cases will always produce a valid string.

```python
protein('UGCGAUGAAUGGGCUCGCUCC') returns 'CDEWARS'
```

Included as test cases is a real world example! The last example test case encodes for a protein called green fluorescent protein; once spliced into the genome of another organism, proteins like GFP allow biologists to visualize cellular processes!

Amino Acid Dictionary
----------------------

```python
    # Phenylalanine
    'UUC':'F', 'UUU':'F',
    # Leucine
    'UUA':'L', 'UUG':'L', 'CUU':'L', 'CUC':'L','CUA':'L','CUG':'L', 
    # Isoleucine
    'AUU':'I', 'AUC':'I', 'AUA':'I', 
    # Methionine
    'AUG':'M', 
    # Valine
    'GUU':'V', 'GUC':'V', 'GUA':'V', 'GUG':'V', 
    # Serine
    'UCU':'S', 'UCC':'S', 'UCA':'S', 'UCG':'S', 'AGU':'S', 'AGC':'S', 
    # Proline
    'CCU':'P', 'CCC':'P', 'CCA':'P', 'CCG':'P', 
    # Threonine
    'ACU':'T', 'ACC':'T', 'ACA':'T', 'ACG':'T',
    # Alanine
    'GCU':'A', 'GCC':'A', 'GCA':'A', 'GCG':'A', 
    # Tyrosine
    'UAU':'Y', 'UAC':'Y', 
    # Histidine
    'CAU':'H', 'CAC':'H',
    # Glutamine
    'CAA':'Q', 'CAG':'Q', 
    # Asparagine
    'AAU':'N', 'AAC':'N', 
    # Lysine
    'AAA':'K', 'AAG':'K',
    # Aspartic Acid
    'GAU':'D', 'GAC':'D', 
    # Glutamic Acid
    'GAA':'E', 'GAG':'E',
    # Cystine
    'UGU':'C', 'UGC':'C',
    # Tryptophan
    'UGG':'W', 
    # Arginine
    'CGU':'R', 'CGC':'R', 'CGA':'R', 'CGG':'R', 'AGA':'R', 'AGG':'R', 
    # Glycine
    'GGU':'G',  'GGC':'G', 'GGA':'G', 'GGG':'G', 
    # Stop codon
    'UAA':'Stop', 'UGA':'Stop', 'UAG':'Stop'
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary array nums, you should delete one element from it.
Return the size of the longest non-empty subarray containing only 1's in the resulting array.
Return 0 if there is no such subarray.
 
Example 1:
Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.
Example 2:
Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].
Example 3:
Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.
Example 4:
Input: nums = [1,1,0,0,1,1,1,0,1]
Output: 4

Example 5:
Input: nums = [0,0,0]
Output: 0

 
Constraints:

1 <= nums.length <= 10^5
nums[i] is either 0 or 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Три брата договорились о встрече. Пронумеруем братьев следующим образом: пусть старший брат имеет номер 1, средний брат имеет номер 2, а младший брат — номер 3. 

Когда пришло время встречи, один из братьев опоздал. По заданным номерам двух братьев, которые пришли вовремя, вам предстоит определить номер опоздавшего брата.


-----Входные данные-----

В первой строке входных данных следуют два различных целых числа a и b (1 ≤ a, b ≤ 3, a ≠ b) — номера братьев, которые пришли на встречу вовремя. Номера даны в произвольном порядке.


-----Выходные данные-----

Выведите единственное целое число — номер брата, который опоздал на встречу.


-----Пример-----
Входные данные
3 1

Выходные данные
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a recipe book. He wishes to read it completely as soon as possible so that he could try to cook the dishes mentioned in the book.
The pages of the book are numbered $1$ through $N$. Over a series of days, Chef wants to read each page. On each day, Chef can choose to read any set of pages such that there is no prime that divides the numbers of two or more of these pages, i.e. the numbers of pages he reads on the same day must be pairwise coprime. For example, Chef can read pages $1$, $3$ and $10$ on one day, since $(1, 3)$, $(3, 10)$ and $(1, 10)$ are pairs of coprime integers; however, he cannot read pages $1$, $3$ and $6$ on one day, as $3$ and $6$ are both divisible by $3$. Since chef might get bored by reading the same recipe again and again, Chef will read every page exactly once.
Given $N$, determine the minimum number of days Chef needs to read the entire book and the pages Chef should read on each of these days.

-----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 a single integer $N$.

-----Output-----
For each test case:
- First, print a line containing a single integer $D$ ― the minimum number of days required to read the book. Let's number these days $1$ through $D$.
- Then, print $D$ lines describing the pages Chef should read. For each valid $i$, the $i$-th of these lines should contain an integer $C_i$ followed by a space and $C_i$ space-separated integers ― the numbers of pages Chef should read on the $i$-th day.
If there are multiple solutions with the minimum number of days, you may print any one.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 10^6$

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

-----Example Input-----
1
5

-----Example Output-----
2
3 1 2 5
2 3 4

-----Explanation-----
Example case 1:
- On the first day, Chef should read three pages: $1$, $2$ and $5$.
- On the second day, Chef should read the remaining two pages: $3$ and $4$.
There are other valid solutions as well.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has N dishes of different types arranged in a row: A_{1}, A_{2}, \ldots, A_{N}, where A_{i} denotes the type of the i^{th} dish. He wants to choose as many dishes as possible from the given list but while satisfying two conditions: 

1.  He can choose only one type of dish.   
2.  No two chosen dishes should be adjacent to each other. 

Chef wants to know which type of dish he should choose from, so that he can pick the maximum number of dishes.

Example:      
Given N=9 and A=[1, 2, 2, 1, 2, 1, 1, 1, 1].   
For type 1, Chef can choose at most four dishes. One of the ways to choose four dishes of type 1 is A_{1}, A_{4}, A_{7} and A_{9}.   
For type 2, Chef can choose at most two dishes. One way is to choose A_{3} and A_{5}.  
So in this case, Chef should go for type 1, in which he can pick more dishes.

------ Input Format ------ 

- The first line contains T, the number of test cases. Then the test cases follow.
- For each test case, the first line contains a single integer N.
- The second line contains N integers A_{1}, A_{2}, \ldots, A_{N}. 

------ Output Format ------ 

For each test case, print a single line containing one integer ― the type of the dish that Chef should choose from. If there are multiple answers, print the smallest one.

------ Constraints ------ 

$1 ≤T ≤10^{3}$
$1 ≤N ≤10^{3}$
$1 ≤A_{i} ≤10^{3}$
- Sum of $N$ over all test cases doesn't exceed $10^{4}$

----- Sample Input 1 ------ 
3
5
1 2 2 1 2
6
1 1 1 1 1 1
8
1 2 2 2 3 4 2 1
----- Sample Output 1 ------ 
1
1
2
----- explanation 1 ------ 
Test case 1:   
For both type 1 and type 2, Chef can pick at most two dishes. In the case of multiple answers, we pick the smallest one. Hence the answer will be $1$.

Test case 2:   
There are only dishes of type 1. So the answer is $1$.

Test case 3:   
For type 1, Chef can choose at most two dishes. For type 2, he can choose three dishes. For type 3 and type 4, Chef can choose the only dish available. Hence the maximum is in type 2 and so the answer is $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a convex polygon P with n distinct vertices p_1, p_2, ..., p_{n}. Vertex p_{i} has coordinates (x_{i}, y_{i}) in the 2D plane. These vertices are listed in clockwise order.

You can choose a real number D and move each vertex of the polygon a distance of at most D from their original positions.

Find the maximum value of D such that no matter how you move the vertices, the polygon does not intersect itself and stays convex.


-----Input-----

The first line has one integer n (4 ≤ n ≤ 1 000) — the number of vertices.

The next n lines contain the coordinates of the vertices. Line i contains two integers x_{i} and y_{i} ( - 10^9 ≤ x_{i}, y_{i} ≤ 10^9) — the coordinates of the i-th vertex. These points are guaranteed to be given in clockwise order, and will form a strictly convex polygon (in particular, no three consecutive points lie on the same straight line).


-----Output-----

Print one real number D, which is the maximum real number such that no matter how you move the vertices, the polygon stays convex.

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 $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----Examples-----
Input
4
0 0
0 1
1 1
1 0

Output
0.3535533906

Input
6
5 0
10 0
12 -4
10 -8
5 -8
3 -4

Output
1.0000000000



-----Note-----

Here is a picture of the first sample

[Image]

Here is an example of making the polygon non-convex.

[Image]

This is not an optimal solution, since the maximum distance we moved one point is  ≈ 0.4242640687, whereas we can make it non-convex by only moving each point a distance of at most  ≈ 0.3535533906.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya has found a piece of paper with a coordinate system written on it. There are *n* distinct squares drawn in this coordinate system. Let's number the squares with integers from 1 to *n*. It turned out that points with coordinates (0,<=0) and (*a**i*,<=*a**i*) are the opposite corners of the *i*-th square.

Vasya wants to find such integer point (with integer coordinates) of the plane, that belongs to exactly *k* drawn squares. We'll say that a point belongs to a square, if the point is located either inside the square, or on its boundary. 

Help Vasya find a point that would meet the described limits.

Input Specification:
The first line contains two space-separated integers *n*, *k* (1<=≤<=*n*,<=*k*<=≤<=50). The second line contains space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109).

It is guaranteed that all given squares are distinct.

Output Specification:
In a single line print two space-separated integers *x* and *y* (0<=≤<=*x*,<=*y*<=≤<=109) — the coordinates of the point that belongs to exactly *k* squares. If there are multiple answers, you are allowed to print any of them. 

If there is no answer, print "-1" (without the quotes).

Demo Input:
['4 3\n5 1 3 4\n', '3 1\n2 4 1\n', '4 50\n5 1 10 2\n']

Demo Output:
['2 1\n', '4 0\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata, you've to count lowercase letters in a given string and return the letter count in a hash with 'letter' as key and count as 'value'. The key must be 'symbol' instead of string in Ruby and 'char' instead of string in Crystal.

Example: 

```python
letter_count('arithmetics') #=> {"a": 1, "c": 1, "e": 1, "h": 1, "i": 2, "m": 1, "r": 1, "s": 1, "t": 2}
```

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

Given a list of integers, find and display all even numbers from the end of the list.

Input Format

Each line of input begins with an integer N indicating the number of integer n that follow which comprises a list. 

Output Format

All even numbers from the end of the list, each separated by a single space. Separate output for each test case with the newline character. Otherwise, display the words None to display

Constraints

2 ≤ N ≤ 100

-1000 ≤ n ≤ 1000

SAMPLE INPUT
5 10 25 12 4 1 
3 16 28 100

SAMPLE OUTPUT
4 12 10 
100 28 16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given sequence $A = \\{a_0, a_1, ..., a_{n-1}\\}$ which is sorted by ascending order, find the lower bound for a specific value $k$ given as a query.

* lower bound: the place pointing to the first element greater than or equal to a specific value, or $n$ if there is no such element.

Constraints

* $1 \leq n \leq 100,000$
* $1 \leq q \leq 200,000$
* $0 \leq a_0 \leq a_1 \leq ... \leq a_{n-1} \leq 1,000,000,000$
* $0 \leq k_i \leq 1,000,000,000$

Input

The input is given in the following format.


$n$
$a_0 \; a_1 \; ,..., \; a_{n-1}$
$q$
$k_1$
$k_2$
:
$k_q$


The number of elements $n$ and each element $a_i$ are given in the first line and the second line respectively. In the third line, the number of queries $q$ is given and the following $q$ lines, $q$ integers $k_i$ are given as queries.

Output

For each query, print the position $i$ ($i = 0, 1, ..., n$) of the lower bound in a line.

Example

Input

4
1 2 2 4
3
2
3
5


Output

1
3
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya the carpenter has an estate that is separated from the wood by a fence. The fence consists of n planks put in a line. The fence is not closed in a circle. The planks are numbered from left to right from 1 to n, the i-th plank is of height ai. All planks have the same width, the lower edge of each plank is located at the ground level.

Recently a local newspaper "Malevich and Life" wrote that the most fashionable way to decorate a fence in the summer is to draw a fuchsia-colored rectangle on it, the lower side of the rectangle must be located at the lower edge of the fence.

Vasya is delighted with this idea! He immediately bought some fuchsia-colored paint and began to decide what kind of the rectangle he should paint. Vasya is sure that the rectangle should cover k consecutive planks. In other words, he will paint planks number x, x + 1, ..., x + k - 1 for some x (1 ≤ x ≤ n - k + 1). He wants to paint the rectangle of maximal area, so the rectangle height equals min ai for x ≤ i ≤ x + k - 1, x is the number of the first colored plank.

Vasya has already made up his mind that the rectangle width can be equal to one of numbers of the sequence k1, k2, ..., km. For each ki he wants to know the expected height of the painted rectangle, provided that he selects x for such fence uniformly among all n - ki + 1 possible values. Help him to find the expected heights.

Input

The first line contains a single integer n (1 ≤ n ≤ 106) — the number of planks in the fence. The second line contains a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109) where ai is the height of the i-th plank of the fence.

The third line contains an integer m (1 ≤ m ≤ 106) and the next line contains m space-separated integers k1, k2, ..., km (1 ≤ ki ≤ n) where ki is the width of the desired fuchsia-colored rectangle in planks.

Output

Print m whitespace-separated real numbers, the i-th number equals the expected value of the rectangle height, if its width in planks equals ki. The value will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

Examples

Input

3
3 2 1
3
1 2 3


Output

2.000000000000000
1.500000000000000
1.000000000000000


Input

2
1 1
3
1 2 1


Output

1.000000000000000
1.000000000000000
1.000000000000000

Note

Let's consider the first sample test. 

  * There are three possible positions of the fence for k1 = 1. For the first position (x = 1) the height is 3, for the second one (x = 2) the height is 2, for the third one (x = 3) the height is 1. As the fence position is chosen uniformly, the expected height of the fence equals <image>; 
  * There are two possible positions of the fence for k2 = 2. For the first position (x = 1) the height is 2, for the second one (x = 2) the height is 1. The expected height of the fence equals <image>; 
  * There is the only possible position of the fence for k3 = 3. The expected height of the fence equals 1. 

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