vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Mittens

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A Christmas party in city S. had *n* children. All children came in mittens. The mittens can be of different colors, but each child had the left and the right mitten of the same color. Let's say that the colors of the mittens are numbered with integers from 1 to *m*, and the children are numbered from 1 to *n*. Then the *i*-th child has both mittens of color *c**i*.

The Party had Santa Claus ('Father Frost' in Russian), his granddaughter Snow Girl, the children danced around the richly decorated Christmas tree. In fact, everything was so bright and diverse that the children wanted to wear mittens of distinct colors. The children decided to swap the mittens so that each of them got one left and one right mitten in the end, and these two mittens were of distinct colors. All mittens are of the same size and fit all the children.

The children started exchanging the mittens haphazardly, but they couldn't reach the situation when each child has a pair of mittens of distinct colors. Vasily Petrov, the dad of one of the children, noted that in the general case the children's idea may turn out impossible. Besides, he is a mathematician and he came up with such scheme of distributing mittens that the number of children that have distinct-colored mittens was maximum. You task is to repeat his discovery. Note that the left and right mittens are different: each child must end up with one left and one right mitten.

Input Specification:
The first line contains two integers *n* and *m* — the number of the children and the number of possible mitten colors (1<=≤<=*n*<=≤<=5000, 1<=≤<=*m*<=≤<=100). The second line contains *n* integers *c*1,<=*c*2,<=... *c**n*, where *c**i* is the color of the mittens of the *i*-th child (1<=≤<=*c**i*<=≤<=*m*).

Output Specification:
In the first line, print the maximum number of children who can end up with a distinct-colored pair of mittens. In the next *n* lines print the way the mittens can be distributed in this case. On the *i*-th of these lines print two space-separated integers: the color of the left and the color of the right mitten the *i*-th child will get. If there are multiple solutions, you can print any of them.

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

Demo Output:
['6\n2 1\n1 2\n2 1\n1 3\n1 2\n3 1\n', '2\n1 2\n1 1\n2 1\n1 1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Vasya heard a story: "In the city of High Bertown a bus number 62 left from the bus station. It had n grown-ups and m kids..."

The latter events happen to be of no importance to us. Vasya is an accountant and he loves counting money. So he wondered what maximum and minimum sum of money these passengers could have paid for the ride.

The bus fare equals one berland ruble in High Bertown. However, not everything is that easy — no more than one child can ride for free with each grown-up passenger. That means that a grown-up passenger who rides with his k (k > 0) children, pays overall k rubles: a ticket for himself and (k - 1) tickets for his children. Also, a grown-up can ride without children, in this case he only pays one ruble.

We know that in High Bertown children can't ride in a bus unaccompanied by grown-ups.

Help Vasya count the minimum and the maximum sum in Berland rubles, that all passengers of this bus could have paid in total.

Input

The input file consists of a single line containing two space-separated numbers n and m (0 ≤ n, m ≤ 105) — the number of the grown-ups and the number of the children in the bus, correspondingly.

Output

If n grown-ups and m children could have ridden in the bus, then print on a single line two space-separated integers — the minimum and the maximum possible total bus fare, correspondingly. 

Otherwise, print "Impossible" (without the quotes).

Examples

Input

1 2


Output

2 2

Input

0 5


Output

Impossible

Input

2 2


Output

2 3

Note

In the first sample a grown-up rides with two children and pays two rubles.

In the second sample there are only children in the bus, so the situation is impossible.

In the third sample there are two cases: 
  * Each of the two grown-ups rides with one children and pays one ruble for the tickets. In this case the passengers pay two rubles in total. 
  * One of the grown-ups ride with two children's and pays two rubles, the another one rides alone and pays one ruble for himself. So, they pay three rubles in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a linked list of N nodes. The task is to check if the linked list has a loop. Linked list can contain self loop.
Example 1:
Input:
N = 3
value[] = {1,3,4}
x(position at which tail is connected) = 2
Output: True
Explanation: In above test case N = 3.
The linked list with nodes N = 3 is
given. Then value of x=2 is given which
means last node is connected with xth
node of linked list. Therefore, there
exists a loop.
Example 2:
Input:
N = 4
value[] = {1,8,3,4}
x = 0
Output: False
Explanation: For N = 4 ,x = 0 means
then lastNode->next = NULL, then
the Linked list does not contains
any loop.
Your Task:
The task is to complete the function detectloop() which contains reference to the head as only argument.  This function should return true if linked list contains loop, else return false.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ Data on Node ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rohan is out for shopping and he has instruction to  bring maximum things(in weight) as much as he can bring. He is given list of things and corresponding weights  to buy. Since he had just studied strictly increasing function in mathematics he thought to buy things in order such that next thing he buys is greater that previous one irrespective of what he was suppose to bring back home. Can you tell how many things of given weight rohan can change to get incresing weights ( or maximum sum)

INPUT

First line contains N no of things Rohan need to buy

Next line contains weights of N things

OUTPUT

Print  minimum number of weights needed to change to make it strictly increasing weights to bring back home

CONSTRAINTS

0 < N ≤ 10^6

0 < weights ≤ 10^9

EXAMPLE 1

INPUT

4

10 20 30 40

OUTPUT

0

EXAMPLE 2

INPUT

7

2 9 12 3 29 35 41

OUTPUT

1

EXPLANATION

In example 1, no need to change anything as weights are in increasing order. So Output is 0.

In example 2, only number 3 needs to be changed or increased to number between 13 and 28 to make weights in increasing order. So Output is 1

SAMPLE INPUT
6
9 10 10 11 11 12

SAMPLE OUTPUT
4

Explanation

Last 4 numbers can be changed to make it strictly increasing that is 9 10 11 12 13 14. So Output is 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The working hours of Chef’s kitchen are from X pm to Y pm (1 ≤ X < Y ≤ 12). 

Find the number of hours Chef works.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two space-separated integers X and Y — the starting and ending time of working hours respectively.

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

For each test case, output on a new line, the number of hours Chef works.

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

$1 ≤ T ≤ 100$
$1 ≤ X < Y ≤ 12$

----- Sample Input 1 ------ 
4
1 2
3 7
9 11
2 10

----- Sample Output 1 ------ 
1
4
2
8

----- explanation 1 ------ 
Test case $1$: Chef starts working at $1$ pm and works till $2$ pm. Thus, he works for $1$ hour.

Test case $2$: Chef starts working at $3$ pm and works till $7$ pm. Thus, he works for $4$ hours.

Test case $3$: Chef starts working at $9$ pm and works till $11$ pm. Thus, he works for $2$ hours.

Test case $4$: Chef starts working at $2$ pm and works till $10$ pm. Thus, he works for $8$ hours.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a linked list consisting of L nodes and given a number N. The task is to find the N^{th} node from the end of the linked list.
Example 1:
Input:
N = 2
LinkedList: 1->2->3->4->5->6->7->8->9
Output: 8
Explanation: In the first example, there
are 9 nodes in linked list and we need
to find 2nd node from end. 2nd node
from end is 8.  
Example 2:
Input:
N = 5
LinkedList: 10->5->100->5
Output: -1
Explanation: In the second example, there
are 4 nodes in the linked list and we
need to find 5th from the end. Since 'n'
is more than the number of nodes in the
linked list, the output is -1.
Your Task:
The task is to complete the function getNthFromLast() which takes two arguments: reference to head and N and you need to return N^{th} from the end or -1 in case node doesn't exist.
Note:
Try to solve in a single traversal.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= L <= 10^{6}
1 <= N <= 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n points on a line with their coordinates x_{i}. Find the point x so the sum of distances to the given points is minimal.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5) — the number of points on the line.

The second line contains n integers x_{i} ( - 10^9 ≤ x_{i} ≤ 10^9) — the coordinates of the given n points.


-----Output-----

Print the only integer x — the position of the optimal point on the line. If there are several optimal points print the position of the leftmost one. It is guaranteed that the answer is always the integer.


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

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a positive integer m and a non-negative integer s. Your task is to find the smallest and the largest of the numbers that have length m and sum of digits s. The required numbers should be non-negative integers written in the decimal base without leading zeroes.


-----Input-----

The single line of the input contains a pair of integers m, s (1 ≤ m ≤ 100, 0 ≤ s ≤ 900) — the length and the sum of the digits of the required numbers.


-----Output-----

In the output print the pair of the required non-negative integer numbers — first the minimum possible number, then — the maximum possible number. If no numbers satisfying conditions required exist, print the pair of numbers "-1 -1" (without the quotes).


-----Examples-----
Input
2 15

Output
69 96

Input
3 0

Output
-1 -1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is sad — New Year is coming in few days but there is still no snow in his city. To bring himself New Year mood, he decided to decorate his house with some garlands.

The local store introduced a new service this year, called "Build your own garland". So you can buy some red, green and blue lamps, provide them and the store workers will solder a single garland of them. The resulting garland will have all the lamps you provided put in a line. Moreover, no pair of lamps of the same color will be adjacent to each other in this garland!

For example, if you provide 3 red, 3 green and 3 blue lamps, the resulting garland can look like this: "RGBRBGBGR" ("RGB" being the red, green and blue color, respectively). Note that it's ok to have lamps of the same color on the ends of the garland.

However, if you provide, say, 1 red, 10 green and 2 blue lamps then the store workers won't be able to build any garland of them. Any garland consisting of these lamps will have at least one pair of lamps of the same color adjacent to each other. Note that the store workers should use all the lamps you provided.

So Polycarp has bought some sets of lamps and now he wants to know if the store workers can build a garland from each of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of sets of lamps Polycarp has bought.

Each of the next t lines contains three integers r, g and b (1 ≤ r, g, b ≤ 10^9) — the number of red, green and blue lamps in the set, respectively.

Output

Print t lines — for each set of lamps print "Yes" if the store workers can build a garland from them and "No" otherwise.

Example

Input


3
3 3 3
1 10 2
2 1 1


Output


Yes
No
Yes

Note

The first two sets are desribed in the statement.

The third set produces garland "RBRG", for example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a sequence, which is formed by the following rule: next term is taken as the smallest possible non-negative integer, which is not yet in the sequence, so that `no 3` terms of sequence form an arithmetic progression.

## Example

`f(0) = 0` -- smallest non-negative  
`f(1) = 1` -- smallest non-negative, which is not yet in the sequence  
`f(2) = 3` -- since `0, 1, 2` form an arithmetic progression  
`f(3) = 4` -- neither of `0, 1, 4`, `0, 3, 4`, `1, 3, 4` form an arithmetic progression, so we can take smallest non-negative, which is larger than `3`  
`f(4) = 9` --  `5, 6, 7, 8` are not good, since `1, 3, 5`, `0, 3, 6`, `1, 4, 7`, `0, 4, 8` are all valid arithmetic progressions.  

etc...

## The task

Write a function `f(n)`, which returns the `n-th` member of sequence.

## Limitations

There are `1000` random tests with `0 <= n <= 10^9`, so you should consider algorithmic complexity of your solution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Having just moved to Transylvania, one of the first orders of business is to get a transit card for the public transportation. The transit card can be charged with intervals of dates. For each such interval, the first few days come at a pretty high price per day, the next few days come at a slightly lower price per day, and so on. 

Since you miss your friends back home, you will frequently be going home for a few days. On the one hand, it seems wasteful to pay for keeping the transit card charged during the days you are away. But on the other hand, if you do not keep it charged then you have to start a new date interval when you get back and will be forced to pay the higher price for a few days again.

Given the pricing scheme and the schedule of which days you are going to be away, you decide to write a program to help you determine the cheapest option.

-----Input-----
The first line of input contains an integer $1 \le l \le 100$, the number of price levels for the transit card. Then follows a line containing $l$ integers $p_1, p_2, \ldots , p_{l}$, where $1 \le p_ i \le 1000$ is the price per day at the $i^\textrm {th}$ price level. The next line contains $l-1$ integers $d_1, d_2, \ldots , d_{l-1}$, where $1 \le d_ i \le 10^6$ indicates how many days the $i^\textrm {th}$ price level is active. Thus for example the third price level $p_3$ becomes active after $d_1 + d_2$ days. The last price level is active indefinitely. You may assume that the prices are monotonically decreasing, i.e., $p_1 > p_2 > \ldots > p_ l$.

The fourth line of input contains two integers $t$ and $n$, where $1 \le t \le 10^6$ is the total number of days for which you want to buy a transit pass, and $0 \le n \le 5000$ is the number of trips home you make during this period. After this follow $n$ lines, each containing two integers $a$ and $b$ ($1 \le a \le b \le t$), indicating that you will be away on all days from day $a$ to day $b$ (inclusive). The days are numbered from $1$ to $t$. You may assume that the trips home are listed in chronological order and that they do not overlap.

-----Output-----
Output the smallest total cost of your transit card for the $t$ days.

-----Examples-----
Sample Input:
3
20 15 10
7 7
30 0
Sample Output:
405

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a huge integer $a$ consisting of $n$ digits ($n$ is between $1$ and $3 \cdot 10^5$, inclusive). It may contain leading zeros.

You can swap two digits on adjacent (neighboring) positions if the swapping digits are of different parity (that is, they have different remainders when divided by $2$). 

For example, if $a = 032867235$ you can get the following integers in a single operation:   $302867235$ if you swap the first and the second digits;  $023867235$ if you swap the second and the third digits;  $032876235$ if you swap the fifth and the sixth digits;  $032862735$ if you swap the sixth and the seventh digits;  $032867325$ if you swap the seventh and the eighth digits. 

Note, that you can't swap digits on positions $2$ and $4$ because the positions are not adjacent. Also, you can't swap digits on positions $3$ and $4$ because the digits have the same parity.

You can perform any number (possibly, zero) of such operations.

Find the minimum integer you can obtain.

Note that the resulting integer also may contain leading zeros.


-----Input-----

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

The only line of each test case contains the integer $a$, its length $n$ is between $1$ and $3 \cdot 10^5$, inclusive.

It is guaranteed that the sum of all values $n$ does not exceed $3 \cdot 10^5$.


-----Output-----

For each test case print line — the minimum integer you can obtain.


-----Example-----
Input
3
0709
1337
246432

Output
0079
1337
234642



-----Note-----

In the first test case, you can perform the following sequence of operations (the pair of swapped digits is highlighted): $0 \underline{\textbf{70}} 9 \rightarrow 0079$.

In the second test case, the initial integer is optimal. 

In the third test case you can perform the following sequence of operations: $246 \underline{\textbf{43}} 2 \rightarrow 24 \underline{\textbf{63}}42 \rightarrow 2 \underline{\textbf{43}} 642 \rightarrow 234642$.

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

JAG land is a country, which is represented as an $M \times M$ grid. Its top-left cell is $(1, 1)$ and its bottom-right cell is $(M, M)$.

Suddenly, a bomber invaded JAG land and dropped bombs to the country. Its bombing pattern is always fixed and represented by an $N \times N$ grid. Each symbol in the bombing pattern is either `X` or `.`. The meaning of each symbol is as follows.

* `X`: Bomb
* `.`: Empty



Here, suppose that a bomber is in $(br, bc)$ in the land and drops a bomb. The cell $(br + i - 1, bc + j - 1)$ will be damaged if the symbol in the $i$-th row and the $j$-th column of the bombing pattern is `X` ($1 \le i, j \le N$).

Initially, the bomber reached $(1, 1)$ in JAG land. The bomber repeated to move to either of $4$-directions and then dropped a bomb just $L$ times. During this attack, the values of the coordinates of the bomber were between $1$ and $M - N + 1$, inclusive, while it dropped bombs. Finally, the bomber left the country.

The moving pattern of the bomber is described as $L$ characters. The $i$-th character corresponds to the $i$-th move and the meaning of each character is as follows.

* `U`: Up
* `D`: Down
* `L`: Left
* `R`: Right



Your task is to write a program to analyze the damage situation in JAG land. To investigate damage overview in the land, calculate the number of cells which were damaged by the bomber at least $K$ times.

* * *

Input

The input consists of a single test case in the format below.

> $N$ $M$ $K$ $L$ $B_{1}$ $\vdots$ $B_{N}$ $S$

The first line contains four integers $N$, $M$, $K$ and $L$($1 \le N < M \le 500$, $1 \le K \le L \le 2 \times 10^{5}$). The following $N$ lines represent the bombing pattern. $B_i$ is a string of length $N$. Each character of $B_i$ is either `X` or `.`. The last line denotes the moving pattern. $S$ is a string of length $L$, which consists of either `U`, `D`, `L` or `R`. It's guaranteed that the values of the coordinates of the bomber are between $1$ and $M - N + 1$, inclusive, while it drops bombs in the country.

Output

Print the number of cells which were damaged by the bomber at least $K$ times.

Examples

Input| Output
---|---


2 3 2 4
XX
X.
RDLU


|


3



7 8 3 5
.XXX.X.
X..X.X.
...XX.X
XX.XXXX
..XXXX.
X.X....
..XXXXX
DRULD


|


26






Example

Input




Output

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It all started with a black-and-white picture, that can be represented as an $n \times m$ matrix such that all its elements are either $0$ or $1$. The rows are numbered from $1$ to $n$, the columns are numbered from $1$ to $m$.

Several operations were performed on the picture (possibly, zero), each of one of the two kinds:

choose a cell such that it's not on the border (neither row $1$ or $n$, nor column $1$ or $m$) and it's surrounded by four cells of the opposite color (four zeros if it's a one and vice versa) and paint it the opposite color itself;

make a copy of the current picture.

Note that the order of operations could be arbitrary, they were not necessarily alternating.

You are presented with the outcome: all $k$ copies that were made. Additionally, you are given the initial picture. However, all $k+1$ pictures are shuffled.

Restore the sequence of the operations. If there are multiple answers, print any of them. The tests are constructed from the real sequence of operations, i. e. at least one answer always exists.


-----Input-----

The first line contains three integers $n, m$ and $k$ ($3 \le n, m \le 30$; $0 \le k \le 100$) — the number of rows and columns of the pictures and the number of copies made, respectively.

Then $k+1$ pictures follow — $k$ copies and the initial picture. Their order is arbitrary.

Each picture consists of $n$ lines, each consisting of $m$ characters, each character is either $0$ or $1$. There is an empty line before each picture.


-----Output-----

In the first line, print a single integer — the index of the initial picture. The pictures are numbered from $1$ to $k+1$ in the order they appear in the input.

In the second line, print a single integer $q$ — the number of operations.

Each of the next $q$ lines should contain an operation. The operations should be listed in order they were applied. Each operation is one of two types:

$1$ $x$ $y$ — recolor a cell $(x, y)$ (the $y$-th cell in the $x$-th row, it should not be on the border and it should be surrounded by four cells of opposite color to itself);

$2$ $i$ — make a copy of the current picture and assign it index $i$ (picture with index the $i$ should be equal to the current picture).

Each index from $1$ to $k+1$ should appear in the output exactly once — one of them is the index of the initial picture, the remaining $k$ are arguments of the operations of the second kind.

If there are multiple answers, print any of them. The tests are constructed from the real sequence of operations, i. e. at least one answer always exists.


-----Examples-----

Input
3 3 1

010
111
010

010
101
010
Output
2
2
1 2 2
2 1
Input
4 5 3

00000
01000
11100
01000

00000
01000
10100
01000

00000
01010
10100
01000

00000
01000
10100
01000
Output
3
5
1 2 4
2 2
2 4
1 3 2
2 1
Input
5 3 0

110
010
001
011
001
Output
1
0


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Print the circumference of a circle of radius R.

Constraints

* 1 \leq R \leq 100
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


R


Output

Print the circumference of the circle. Your output is considered correct if and only if its absolute or relative error from our answer is at most 10^{-2}.

Examples

Input

1


Output

6.28318530717958623200


Input

73


Output

458.67252742410977361942

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