vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
For $n$ dynamic arrays $A_i$ ($i = 0, 1, ..., n-1$), perform a sequence of the following operations:

* pushBack($t$, $x$): Add element $x$ at the end of $A_t$.
* dump($t$): Print all elements in $A_t$.
* clear($t$): Clear $A_t$. If $A_t$ is empty, do nothing.



$A_i$ is a 0-origin array and it is empty in the initial state.

Constraints

* $1 \leq n \leq 1,000$
* $1 \leq q \leq 500,000$
* $-1,000,000,000 \leq x \leq 1,000,000,000$
* The total number of elements printed by dump operations do not exceed 500,000

Input

The input is given in the following format.


$n$ $q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $t$ $x$


or


1 $t$


or


2 $t$


where the first digits 0, 1 and 2 represent pushBack, dump and clear operations respectively.

Output

For each dump operation, print elements of $A_t$ a line. Separete adjacency elements by a space character (do not print the space after the last element). Note that, if the array is empty, an empty line should be printed.

Example

Input

3 13
0 0 1
0 0 2
0 0 3
0 1 -1
0 2 4
0 2 5
1 0
1 1
1 2
2 1
1 0
1 1
1 2


Output

1 2 3
-1
4 5
1 2 3

4 5

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

John has an important number, and he doesn't want others to see it.

He decided to encrypt the number, using the following steps:
```
His number is always a non strict increasing sequence
ie. "123"

He converted each digit into English words.
ie. "123"--> "ONETWOTHREE"

And then, rearrange the letters randomly.
ie. "ONETWOTHREE" --> "TTONWOHREEE"
```

John felt that his number were safe in doing so. In fact, such encryption can be easily decrypted :(

Given the encrypted string `s`, your task is to decrypt it, return the original number in string format.

Note, You can assume that the input string `s` is always valid; It contains only uppercase Letters; The decrypted numbers are arranged in ascending order; The leading zeros are allowed.


# Example

For `s = "ONE"`, the output should be `1`.

For `s = "EON"`, the output should be `1` too.

For `s = "ONETWO"`, the output should be `12`.

For `s = "OONETW"`, the output should be `12` too.

For `s = "ONETWOTHREE"`, the output should be `123`.

For `s = "TTONWOHREEE"`, the output should be `123` too.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The determinant of a matrix 2 × 2 is defined as follows:

<image>

A matrix is called degenerate if its determinant is equal to zero. 

The norm ||A|| of a matrix A is defined as a maximum of absolute values of its elements.

You are given a matrix <image>. Consider any degenerate matrix B such that norm ||A - B|| is minimum possible. Determine ||A - B||.

Input

The first line contains two integers a and b (|a|, |b| ≤ 109), the elements of the first row of matrix A. 

The second line contains two integers c and d (|c|, |d| ≤ 109) the elements of the second row of matrix A.

Output

Output a single real number, the minimum possible value of ||A - B||. Your answer is considered to be correct if its absolute or relative error does not exceed 10 - 9.

Examples

Input

1 2
3 4


Output

0.2000000000


Input

1 0
0 1


Output

0.5000000000

Note

In the first sample matrix B is <image>

In the second sample matrix B is <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
### Task
You've just moved into a perfectly straight street with exactly ```n``` identical houses on either side of the road. Naturally, you would like to find out the house number of the people on the other side of the street. The street looks something like this:

--------------------
### Street
```
1|   |6
3|   |4
5|   |2
```

Evens increase on the right; odds decrease on the left. House numbers start at ```1``` and increase without gaps.
When ```n = 3```, ```1``` is opposite ```6```, ```3``` opposite ```4```, and ```5``` opposite ```2```. 

-----------------
### Example
Given your house number ```address``` and length of street ```n```, give the house number on the opposite side of the street.

```CoffeeScript
overTheRoad(address, n)
overTheRoad(1, 3) = 6
overTheRoad(3, 3) = 4
overTheRoad(2, 3) = 5
overTheRoad(3, 5) = 8
```

```python
over_the_road(address, n)
over_the_road(1, 3) = 6
over_the_road(3, 3) = 4
over_the_road(2, 3) = 5
over_the_road(3, 5) = 8
```


Both n and address could get upto 500 billion with over 200 random tests.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Charlie and Johnny play a game. For every integer X Charlie gives, Johnny has to find the smallest positive integer Y, such that X * Y contains only 4's and 0's and starts with one or more 4's followed by zero or more 0's. (i.e.), 404 is an invalid number but 400 is a valid number. 

If a is the number of 4's and b is the number of 0's, can you print the value of 2 * a + b.

Input Format

The first line contains an integer T. T lines follow, each line containing the integer X as stated above.

Output Format

For every X, print the output 2 * a + b in a newline as stated in the problem statement. 

Constraints

1<=T<=10^{3} 

1<=X<=10^{5}

Sample Input #00

3
4
5
80

Sample Output #00

2
3
4

Explanation 

For the 1^{st} test-case, the smallest such multiple of 4 is 4 itself. Hence value of a will be 1 and and value of b will be 0. The required value of 2 * a+b is 2.     

For the 2^{nd} test-case, Y = 8 and 40 is the minimum such multiple of 5. Hence value of a,b and 2 * a+b will be 1, 1 and 3 respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kana was just an ordinary high school girl before a talent scout discovered her. Then, she became an idol. But different from the stereotype, she is also a gameholic. 

One day Kana gets interested in a new adventure game called Dragon Quest. In this game, her quest is to beat a dragon.[Image] 

The dragon has a hit point of $x$ initially. When its hit point goes to $0$ or under $0$, it will be defeated. In order to defeat the dragon, Kana can cast the two following types of spells.  Void Absorption 

Assume that the dragon's current hit point is $h$, after casting this spell its hit point will become $\left\lfloor \frac{h}{2} \right\rfloor + 10$. Here $\left\lfloor \frac{h}{2} \right\rfloor$ denotes $h$ divided by two, rounded down. Lightning Strike 

This spell will decrease the dragon's hit point by $10$. Assume that the dragon's current hit point is $h$, after casting this spell its hit point will be lowered to $h-10$.

Due to some reasons Kana can only cast no more than $n$ Void Absorptions and $m$ Lightning Strikes. She can cast the spells in any order and doesn't have to cast all the spells. Kana isn't good at math, so you are going to help her to find out whether it is possible to defeat the dragon.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 1000$)  — the number of test cases.

The next $t$ lines describe test cases. For each test case the only line contains three integers $x$, $n$, $m$ ($1\le x \le 10^5$, $0\le n,m\le30$)  — the dragon's intitial hit point, the maximum number of Void Absorptions and Lightning Strikes Kana can cast respectively.


-----Output-----

If it is possible to defeat the dragon, print "YES" (without quotes). Otherwise, print "NO" (without quotes).

You can print each letter in any case (upper or lower).


-----Example-----
Input
7
100 3 4
189 3 4
64 2 3
63 2 3
30 27 7
10 9 1
69117 21 2

Output
YES
NO
NO
YES
YES
YES
YES



-----Note-----

One possible casting sequence of the first test case is shown below: Void Absorption $\left\lfloor \frac{100}{2} \right\rfloor + 10=60$. Lightning Strike $60-10=50$. Void Absorption $\left\lfloor \frac{50}{2} \right\rfloor + 10=35$. Void Absorption $\left\lfloor \frac{35}{2} \right\rfloor + 10=27$. Lightning Strike $27-10=17$. Lightning Strike $17-10=7$. Lightning Strike $7-10=-3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a pyramid with N steps, built with blocks. The steps are numbered 1 through N from top to bottom. For each 1≤i≤N, step i consists of 2i-1 blocks aligned horizontally. The pyramid is built so that the blocks at the centers of the steps are aligned vertically.

<image>

A pyramid with N=4 steps

Snuke wrote a permutation of (1, 2, ..., 2N-1) into the blocks of step N. Then, he wrote integers into all remaining blocks, under the following rule:

* The integer written into a block b must be equal to the median of the three integers written into the three blocks directly under b, or to the lower left or lower right of b.



<image>

Writing integers into the blocks

Afterwards, he erased all integers written into the blocks. Now, he only remembers that the integer written into the block of step 1 was x.

Construct a permutation of (1, 2, ..., 2N-1) that could have been written into the blocks of step N, or declare that Snuke's memory is incorrect and such a permutation does not exist.

Constraints

* 2≤N≤10^5
* 1≤x≤2N-1

Input

The input is given from Standard Input in the following format:


N x


Output

If no permutation of (1, 2, ..., 2N-1) could have been written into the blocks of step N, print `No`.

Otherwise, print `Yes` in the first line, then print 2N-1 lines in addition.

The i-th of these 2N-1 lines should contain the i-th element of a possible permutation.

Examples

Input

4 4


Output

Yes
1
6
3
7
4
5
2


Input

2 1


Output

No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Check if given chord is minor or major.

_____________________________________________________________
Rules:

1. Basic minor/major chord have three elements.

2. Chord is minor when interval between first and second element equals 3 and between second and third -> 4.

3. Chord is major when interval between first and second element equals 4 and between second and third -> 3.

4. In minor/major chord interval between first and third element equals... 7.

_______________________________________________________________
There is a preloaded list of the 12 notes of a chromatic scale built on C. This means that there are (almost) all allowed note' s names in music.

notes = 
['C', ['C#', 'Db'], 'D', ['D#', 'Eb'], 'E', 'F', ['F#', 'Gb'], 'G', ['G#', 'Ab'], 'A', ['A#', 'Bb'], 'B']

Note that e. g. 'C#' - 'C' = 1, 'C' - 'C#' = 1, 'Db' - 'C' = 1 and 'B' - 'C' = 1. 

Input:
String of notes separated by whitespace, e. g. 'A C# E'

Output:
String message: 'Minor', 'Major' or 'Not a chord'.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You found a mysterious function *f*. The function takes two strings *s*1 and *s*2. These strings must consist only of lowercase English letters, and must be the same length.

The output of the function *f* is another string of the same length. The *i*-th character of the output is equal to the minimum of the *i*-th character of *s*1 and the *i*-th character of *s*2.

For example, *f*("ab", "ba") = "aa", and *f*("nzwzl", "zizez") = "niwel".

You found two strings *x* and *y* of the same length and consisting of only lowercase English letters. Find any string *z* such that *f*(*x*,<=*z*)<==<=*y*, or print -1 if no such string *z* exists.

Input Specification:
The first line of input contains the string *x*.

The second line of input contains the string *y*.

Both *x* and *y* consist only of lowercase English letters, *x* and *y* have same length and this length is between 1 and 100.

Output Specification:
If there is no string *z* such that *f*(*x*,<=*z*)<==<=*y*, print -1.

Otherwise, print a string *z* such that *f*(*x*,<=*z*)<==<=*y*. If there are multiple possible answers, print any of them. The string *z* should be the same length as *x* and *y* and consist only of lowercase English letters.

Demo Input:
['ab\naa\n', 'nzwzl\nniwel\n', 'ab\nba\n']

Demo Output:
['ba\n', 'xiyez\n', '-1\n']

Note:
The first case is from the statement.

Another solution for the second case is "zizez"

There is no solution for the third case. That is, there is no *z* such that *f*("ab", *z*) =  "ba".

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
There is a given sequence of integers *a*1,<=*a*2,<=...,<=*a**n*, where every number is from 1 to 3 inclusively. You have to replace the minimum number of numbers in it so that all the numbers in the sequence are equal to each other.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=106). The second line contains a sequence of integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=3).

Output Specification:
Print the minimum number of replacements needed to be performed to make all the numbers in the sequence equal.

Demo Input:
['9\n1 3 2 2 2 1 1 2 3\n']

Demo Output:
['5\n']

Note:
In the example all the numbers equal to 1 and 3 should be replaced by 2.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alice is a beginner composer and now she is ready to create another masterpiece. And not even the single one but two at the same time! 

Alice has a sheet with *n* notes written on it. She wants to take two such non-empty non-intersecting subsequences that both of them form a melody and sum of their lengths is maximal.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Subsequence forms a melody when each two adjacent notes either differs by 1 or are congruent modulo 7.

You should write a program which will calculate maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.

Input Specification:
The first line contains one integer number *n* (2<=≤<=*n*<=≤<=5000).

The second line contains *n* integer numbers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=105) — notes written on a sheet.

Output Specification:
Print maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.

Demo Input:
['4\n1 2 4 5\n', '6\n62 22 60 61 48 49\n']

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

Note:
In the first example subsequences [1, 2] and [4, 5] give length 4 in total.

In the second example subsequences [62, 48, 49] and [60, 61] give length 5 in total. If you choose subsequence [62, 61] in the first place then the second melody will have maximum length 2, that gives the result of 4, which is not maximal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The country of Magicland has N cities (numbered 1 through N) and N-1 bidirectional roads.
Each road connects two different cities.
There is a unique path between each pair of cities.
All roads in the country have the same length, equal to 1.

Magicland also has the bus service.
It allows citizens to ride between any pair of cities at the cost of dist^K where K is a fixed integer, and dist denotes the distance between the two cities.

Kevin lives in Magicland and is going on an adventure.
He wants to travel between every pair of cities exactly once by riding on buses.
Note that there are exactly N(N-1)/2 pairs of cities.
He is wondering how much it will cost him in total.
Find the total cost and print it modulo 10^9+7.

Input format
The first line contains two integers N and K.

The next N-1 lines contain 2 integers each, denoting two cities connected by a road.

Output format
In a single line print the answer modulo 10^9+7.

Constraints
2 ≤ N ≤ 10^5
1 ≤ K ≤ 10^9

SAMPLE INPUT
5 3
1 2
3 2
4 3
3 5

SAMPLE OUTPUT
90

Explanation

Magicland has 5 cities and 4 roads: (1, 2), (3, 2), (4, 3), (3, 5).

There are 10 pairs of cities.
4 of them are directly connected by a road and thus Kevin will pay 4 * 1^3 = 4 for them in total.
For the other 4 pairs of cities the distance is equal to 2 and Kevin will pay 2^3 = 8 for each of them, 4*8 = 32 in total.
And the last 2 pairs have the distance equal to 3 and Kevin must pay 2 * 3^3 = 54 for them.

The total cost is 4 + 32 + 54 = 90.

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

The input is given from Standard Input in the following format:


> $N \ K$

Output

* Please output the $K$-th triangle area.
* Print a floating number denoting the answer. The relative or absolute error of your answer should not be higher than $10^{−9}$.



Constraints

* $3 \le N \le 200,000$
* $1 \le K \le \frac{N(N-1)(N-2)}{6}$



Subtasks

Subtask 1 [ $160$ points ]


* $N \le 100$

Subtask 2 [ $240$ points ]


* $N \le 1000$

Subtask 3 [ $450$ points ]


* $N \le 200,000$

Output

* Please output the $K$-th triangle area.
* Print a floating number denoting the answer. The relative or absolute error of your answer should not be higher than $10^{−9}$.



Constraints

* $3 \le N \le 200,000$
* $1 \le K \le \frac{N(N-1)(N-2)}{6}$



Subtasks

Subtask 1 [ $160$ points ]


* $N \le 100$

Subtask 2 [ $240$ points ]


* $N \le 1000$

Subtask 3 [ $450$ points ]


* $N \le 200,000$

Input

The input is given from Standard Input in the following format:


> $N \ K$

Examples

Input

4 3


Output

1.0000000000000


Input

6 9


Output

0.86602540378


Input

12 220


Output

1.29903810568

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are two popular keyboard layouts in Berland, they differ only in letters positions. All the other keys are the same. In Berland they use alphabet with 26 letters which coincides with English alphabet.

You are given two strings consisting of 26 distinct letters each: all keys of the first and the second layouts in the same order. 

You are also given some text consisting of small and capital English letters and digits. It is known that it was typed in the first layout, but the writer intended to type it in the second layout. Print the text if the same keys were pressed in the second layout.

Since all keys but letters are the same in both layouts, the capitalization of the letters should remain the same, as well as all other characters.


-----Input-----

The first line contains a string of length 26 consisting of distinct lowercase English letters. This is the first layout.

The second line contains a string of length 26 consisting of distinct lowercase English letters. This is the second layout.

The third line contains a non-empty string s consisting of lowercase and uppercase English letters and digits. This is the text typed in the first layout. The length of s does not exceed 1000.


-----Output-----

Print the text if the same keys were pressed in the second layout.


-----Examples-----
Input
qwertyuiopasdfghjklzxcvbnm
veamhjsgqocnrbfxdtwkylupzi
TwccpQZAvb2017

Output
HelloVKCup2017

Input
mnbvcxzlkjhgfdsapoiuytrewq
asdfghjklqwertyuiopzxcvbnm
7abaCABAABAcaba7

Output
7uduGUDUUDUgudu7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Asif loves chocolates. He eats a lot of chocolates  every day and has become very fat. So his father has decided to make him walk. 

Asif's  father has given him a binary tree of N nodes. Some of these nodes would contain chocolates(A node can contain maximum one chocolate). Now Asif's father asks him to start from a node numbered M. Asif is allowed to eat chocolate only while standing on this node. Also he can carry only one chocolate at a time. So Asif will start from M, collect any one chocolate and bring it back to M, and eat it. He continues this process until no chocolates are left.

Initially there will be no chocolates on any nodes
You task is to process queries of 2 types.

  Type 0: For the given M, find out the distance that Asif should walk to collect all the chocolates.

  Type 1: Place a chocolate on node M(if it doesn't already contain a chocolate).

Note : After processing a query of type 0, you should not remove the             chocolates from the nodes.

Root of the tree will be numbered 1, and a node numbered x will have children numbered 2x and 2x+1. Distance between any two connected nodes is 1.

Input:
First line will contain N(1 ≤ N ≤ 100000), no of nodes.
Next line will contain Q(1 ≤ Q ≤ 100000), number of queries you need to process
Each of the next Q lines will contain two integers, Type(0 or 1) and M(1 ≤ M ≤ N).

Output:
For each query of Type 0, print the distance that Asif should walk.

SAMPLE INPUT
6
9
0 1
1 4
0 2
1 5
0 1
1 4
0 1
1 1
0 6

SAMPLE OUTPUT
0
2
8
8
20

Explanation

0 1: There are no chocolate initially, so output 0
1 4: Chocolate added to node 4
0 2: Path traversed is 2->4->2 so output 2
1 5: Chocolate added to node 5
0 1: Path traversed, 1->2->4->2->1->2>5>2>1 output 8
1 4: Node 4 already had a chocolate. So do nothing
0 1: Path traversed, 1->2->4->2->1->2>5>2>1 output 8
1 1: Chocolate added to node 1
0 6: Path traversed 6->3->1>2->4->2->1->3->6->3->1->2->5->2->1->3->6 ->3->1->3->6   output 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Žofka invented a new word puzzle. She gives you two strings $s_1$ and $s_2$ of the same length. You need to modify $s_1$ into $s_2$ as quickly as possible. The trick is that you are allowed to modify the strings only using the following types of moves: (1) shift forward where you choose a substring of one of the strings and shift each of its letters by 1 forward in the alphabet, or (2) shift backward where you shift each letter in a substring backward in the alphabet. The first move is not allowed if the substring contains the letter z while the second move is not allowed if the subtring contains a. What is the smallest number of moves you need to modify $s_1$ into $s_2$?

-----Input-----
Each word puzzle is described on a single line that contains the strings $s_1$ and $s_2$ separated by space. The strings contain only lower case letters. You may also assume that the length of each string is at most $10000000$.

-----Output-----
Output one line with the smallest number of moves needed to modify $s_1$ into $s_2$.

-----Note-----
The first sample input can be modified in the following way. First shift lo forward, getting helmp. Then shift h forward 12 times, getting telmp. Then shift l 11 times backward to get teamp and then shift p forward three times to get teams. Total number of moves is $1+12+11+3=27$.

The second sample input can be modified as follows. First shift the entire string forward, getting bbdddbbbb. Then shift ddd backward twice to get bbbbbbbbb. This requires 1+2=3 moves.

-----Examples-----
Sample Input:
hello teams
Sample Output:
27

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
zscoder wants to generate an input file for some programming competition problem.

His input is a string consisting of *n* letters 'a'. He is too lazy to write a generator so he will manually generate the input in a text editor.

Initially, the text editor is empty. It takes him *x* seconds to insert or delete a letter 'a' from the text file and *y* seconds to copy the contents of the entire text file, and duplicate it.

zscoder wants to find the minimum amount of time needed for him to create the input file of exactly *n* letters 'a'. Help him to determine the amount of time needed to generate the input.

Input Specification:
The only line contains three integers *n*, *x* and *y* (1<=≤<=*n*<=≤<=107, 1<=≤<=*x*,<=*y*<=≤<=109) — the number of letters 'a' in the input file and the parameters from the problem statement.

Output Specification:
Print the only integer *t* — the minimum amount of time needed to generate the input file.

Demo Input:
['8 1 1\n', '8 1 10\n']

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

Note:
none

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