vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
This is an interactive task.

We have 2N balls arranged in a row, numbered 1, 2, 3, ..., 2N from left to right, where N is an odd number. Among them, there are N red balls and N blue balls.

While blindfolded, you are challenged to guess the color of every ball correctly, by asking at most 210 questions of the following form:

* You choose any N of the 2N balls and ask whether there are more red balls than blue balls or not among those N balls.



Now, let us begin.

Constraints

* 1 \leq N \leq 99
* N is an odd number.



* * *



Example

Input




Output

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alyona has recently bought a miniature fridge that can be represented as a matrix with $h$ rows and $2$ columns. Initially there is only one shelf at the bottom of the fridge, but Alyona can install arbitrary number of shelves inside the fridge between any two rows. A shelf is two cells wide, does not occupy any space but separates the inside of the fridge to the lower and upper part.

 [Image] An example of a fridge with $h = 7$ and two shelves. The shelves are shown in black. The picture corresponds to the first example. 

Alyona has $n$ bottles of milk that she wants to put in the fridge. The $i$-th bottle is $a_i$ cells tall and $1$ cell wide. She can put a bottle on some shelf if the corresponding space above the shelf is at least as tall as the bottle. She can not put a bottle on top of another bottle (if there is no shelf between them). Two bottles can not share a cell.

Alyona is interested in the largest integer $k$ such that she can put bottles $1$, $2$, ..., $k$ in the fridge at the same time. Find this largest $k$.


-----Input-----

The first line contains two integers $n$ and $h$ ($1 \le n \le 10^3$, $1 \le h \le 10^9$) — the number of bottles and the height of the fridge.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le h$) — the heights of the bottles.


-----Output-----

Print the single integer $k$ — the maximum integer such that Alyona can put the bottles $1$, $2$, ..., $k$ in the fridge at the same time. If Alyona can put all bottles in the fridge, print $n$. It is easy to see that Alyona can always put at least one bottle in the fridge.


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

Output
3

Input
10 10
9 1 1 1 1 1 1 1 1 1

Output
4

Input
5 10
3 1 4 2 4

Output
5



-----Note-----

One of optimal locations in the first example is shown on the picture in the statement.

One of optimal locations in the second example is shown on the picture below.

 [Image] 

One of optimal locations in the third example is shown on the picture below.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a[0 \ldots n-1]$ of length $n$ which consists of non-negative integers. Note that array indices start from zero.

An array is called good if the parity of each index matches the parity of the element at that index. More formally, an array is good if for all $i$ ($0 \le i \le n - 1$) the equality $i \bmod 2 = a[i] \bmod 2$ holds, where $x \bmod 2$ is the remainder of dividing $x$ by 2.

For example, the arrays [$0, 5, 2, 1$] and [$0, 17, 0, 3$] are good, and the array [$2, 4, 6, 7$] is bad, because for $i=1$, the parities of $i$ and $a[i]$ are different: $i \bmod 2 = 1 \bmod 2 = 1$, but $a[i] \bmod 2 = 4 \bmod 2 = 0$.

In one move, you can take any two elements of the array and swap them (these elements are not necessarily adjacent).

Find the minimum number of moves in which you can make the array $a$ good, or say that this is not possible.


-----Input-----

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

Each test case starts with a line containing an integer $n$ ($1 \le n \le 40$) — the length of the array $a$.

The next line contains $n$ integers $a_0, a_1, \ldots, a_{n-1}$ ($0 \le a_i \le 1000$) — the initial array.


-----Output-----

For each test case, output a single integer — the minimum number of moves to make the given array $a$ good, or -1 if this is not possible.


-----Example-----
Input
4
4
3 2 7 6
3
3 2 6
1
7
7
4 9 2 1 18 3 0

Output
2
1
-1
0



-----Note-----

In the first test case, in the first move, you can swap the elements with indices $0$ and $1$, and in the second move, you can swap the elements with indices $2$ and $3$.

In the second test case, in the first move, you need to swap the elements with indices $0$ and $1$.

In the third test case, you cannot make the array good.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Tattah is asleep if and only if Tattah is attending a lecture. This is a well-known formula among Tattah's colleagues.

On a Wednesday afternoon, Tattah was attending Professor HH's lecture. At 12:21, right before falling asleep, he was staring at the digital watch around Saher's wrist. He noticed that the digits on the clock were the same when read from both directions i.e. a palindrome.

In his sleep, he started dreaming about such rare moments of the day when the time displayed on a digital clock is a palindrome. As soon as he woke up, he felt destined to write a program that finds the next such moment.

However, he still hasn't mastered the skill of programming while sleeping, so your task is to help him.

Input Specification:
The first and only line of the input starts with a string with the format "HH:MM" where "HH" is from "00" to "23" and "MM" is from "00" to "59". Both "HH" and "MM" have exactly two digits.

Output Specification:
Print the palindromic time of day that comes soonest after the time given in the input. If the input time is palindromic, output the soonest palindromic time after the input time.

Demo Input:
['12:21\n', '23:59\n']

Demo Output:
['13:31\n', '00:00\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Onogawa Expedition is planning to conduct a survey of the Aizu nature reserve. The expedition planner wants to take the shortest possible route from the start to end point of the survey, while the expedition has to go around the coast of the Lake of Onogawa en route. The expedition walks along the coast of the lake, but can not wade across the lake.

Based on the base information including the start and end point of the survey and the area of Lake Onogawa as convex polygon data, make a program to find the shortest possible route for the expedition and calculate its distance. Note that the expedition can move along the polygonal lines passing through the nodes, but never enter within the area enclosed by the polygon.



Input

The input is given in the following format.


x_s y_s
x_g y_g
N
x_1 y_1
x_2 y_2
:
x_N y_N


The first line provides the start point of the survey x_s,y_s (0≤x_s,y_s≤104), and the second line provides the end point x_g,y_g (0 ≤ x_g,y_g ≤ 104) all in integers. The third line provides the number of apexes N (3 ≤ N ≤ 100) of the polygon that represents the lake, and each of the subsequent N lines provides the coordinate of the i-th apex x_i,y_i (0 ≤ x_i,y_i ≤ 104) in counter-clockwise order. These data satisfy the following criteria:

* Start and end points of the expedition are not within the area enclosed by the polygon nor on boundaries.
* Start and end points of the expedition are not identical, i.e., x_s ≠ x_g or y_s ≠ y_g.
* No duplicate coordinates are given, i.e., if i ≠ j then x_i ≠ x_r or y_i ≠ y_j.
* The area enclosed by the polygon has a positive value.
* Any three coordinates that define an area are not aligned on a line.

Output

Output the distance of the shortest possible expedition route. Any number of decimal places can be selected as long as the error does not exceed ± 10-3.

Examples

Input

0 0
4 0
4
1 1
2 1
3 3
1 2


Output

4.472136


Input

4 4
0 0
4
1 1
3 1
3 3
1 3


Output

6.32455

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who has an id greater than the psycho to his right (if exists) kills his right neighbor in the line. Note that a psycho might kill and get killed at the same step. 

You're given the initial arrangement of the psychos in the line. Calculate how many steps are needed to the moment of time such, that nobody kills his neighbor after that moment. Look notes to understand the statement more precise.


-----Input-----

The first line of input contains integer n denoting the number of psychos, (1 ≤ n ≤ 10^5). In the second line there will be a list of n space separated distinct integers each in range 1 to n, inclusive — ids of the psychos in the line from left to right.


-----Output-----

Print the number of steps, so that the line remains the same afterward.


-----Examples-----
Input
10
10 9 7 8 6 5 3 4 2 1

Output
2

Input
6
1 2 3 4 5 6

Output
0



-----Note-----

In the first sample line of the psychos transforms as follows: [10 9 7 8 6 5 3 4 2 1]  →  [10 8 4]  →  [10]. So, there are two steps.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Taro loves chocolate and when he returns from school he eats his favorite chocolate bar with a heart symbol on it. A recent pleasure is to eat all the heart symbol blocks to the end. Taro , Try to eat as many heartless blocks as possible, with all heartmark blocks connected.

<image>

However, Taro is still young, and even if he tries to eat as above, useless blocks will remain. Therefore, Taro seeks the maximum number of blocks that can be eaten when all the heart-shaped blocks are left connected. I asked you to create a program.

Taro can eat whatever way he wants, as long as all the heart-shaped blocks are connected. If one side of one block does not touch the other block, it will be separated.



Input

The input consists of multiple datasets, each dataset given in the following format:


H W
H x W numbers


H and W are integers indicating the vertical size and horizontal size of the chocolate bar, respectively. H x W numbers represent block information, '0' representing blocks without a heart mark, and blocks with a heart mark. Consists of '1'.

The end of the input is indicated by the dataset where H = W = 0. Do not output for this case.

You can assume that 1 ≤ H, W ≤ 12 and the number of heart-shaped blocks is 6 or less.

Output

For each dataset, output the maximum number of blocks that Taro can eat.

Example

Input

4 4
1 0 0 0
0 0 1 0
0 1 0 0
1 0 0 1
1 1
1
2 3
1 0 0
0 0 1
0 0


Output

7
0
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A team of students from the city S is sent to the All-Berland Olympiad in Informatics. Traditionally, they go on the train. All students have bought tickets in one carriage, consisting of n compartments (each compartment has exactly four people). We know that if one compartment contain one or two students, then they get bored, and if one compartment contain three or four students, then the compartment has fun throughout the entire trip.

The students want to swap with other people, so that no compartment with students had bored students. To swap places with another person, you need to convince him that it is really necessary. The students can not independently find the necessary arguments, so they asked a sympathetic conductor for help. The conductor can use her life experience to persuade any passenger to switch places with some student.

However, the conductor does not want to waste time persuading the wrong people, so she wants to know what is the minimum number of people necessary to persuade her to change places with the students. Your task is to find the number. 

After all the swaps each compartment should either have no student left, or have a company of three or four students. 


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^6) — the number of compartments in the carriage. The second line contains n integers a_1, a_2, ..., a_{n} showing how many students ride in each compartment (0 ≤ a_{i} ≤ 4). It is guaranteed that at least one student is riding in the train.


-----Output-----

If no sequence of swapping seats with other people leads to the desired result, print number "-1" (without the quotes). In another case, print the smallest number of people you need to persuade to swap places.


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

Output
2

Input
3
4 1 1

Output
2

Input
4
0 3 0 4

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An architect, Devunky, who lives in Water Deven, has been asked to renovate an old large hospital.

In some countries, people don't want to use numbers that are disliked as numerophobia (4 and 9 are famous in Japan). However, the room numbers in this hospital were numbered from 1 regardless of the number of numerophobia.

Mr. Devunky, who was worried about it, renumbered the room with the numbers excluding "4" and "6", which are the numerophobia of Water Devon, before all the equipment and beds were replaced. However, since the replacement work was planned with the old room number, it is necessary to convert the old room number to the new room number to ensure that the rest of the work is done. Mr. Devunky, who is not good at calculations, is surprised to notice this.

For such Mr. Devunky, please create a program that inputs the old room number and outputs the corresponding new room number.

The correspondence table of room numbers up to the 15th is as follows.

Old room number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |- -| --- | --- | ---
New room number | 1 | 2 | 3 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 15 | 17 | 18 | 19




Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. For each dataset, the integer n (1 ≤ n ≤ 1,000,000,000) representing the old room number is given on one line.

The number of datasets does not exceed 30000.

Output

Outputs the new room number on one line for each input dataset.

Example

Input

15
100
1000000000
3
0


Output

19
155
9358757000
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
According to the legends the king of Berland Berl I was noted for his love of beauty and order. One day he ordered to tile the palace hall's floor where balls and receptions used to take place with black and white tiles according to a regular geometrical pattern invented by him. However, as is after the case, due to low financing there were only a black and b white tiles delivered to the palace. The other c tiles were black and white (see the picture).

<image>

The initial plan failed! Having learned of that, the king gave a new command: tile the floor with the available tiles so that no black side of a tile touched a white one. The tiles are squares of one size 1 × 1, every black and white tile can be rotated in one of the four ways. 

The court programmer was given the task to work out the plan of tiling and he coped with the task and didn't suffer the consequences of disobedience. And can you cope with it?

Input

The first line contains given integers n and m (1 ≤ n, m ≤ 100) which represent the sizes of the rectangle that needs to be tiled. The next line contains non-negative numbers a, b and c, a + b + c = nm, c ≥ m. 

Output

Print 2n lines containing 2m characters each — the tiling scheme. Every tile is represented by a square 2 × 2 in the following manner (the order corresponds to the order of the picture above): 

<image> If multiple solutions exist, output any.

Examples

Input

2 2
0 0 4


Output

<span class="tex-span">\</span>../
#<span class="tex-span">\</span>/#
<span class="tex-span">\</span>##/
.<span class="tex-span">\</span>/.


Input

2 3
1 2 3


Output

###/<span class="tex-span">\</span>#
##/..<span class="tex-span">\</span>
#/....
/.....

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We will create an artwork by painting black some squares in a white square grid with 10^9 rows and N columns.

The current plan is as follows: for the i-th column from the left, we will paint the H_i bottommost squares and will not paint the other squares in that column.

Before starting to work, you can choose at most K columns (possibly zero) and change the values of H_i for these columns to any integers of your choice between 0 and 10^9 (inclusive).

Different values can be chosen for different columns.

Then, you will create the modified artwork by repeating the following operation:

 - Choose one or more consecutive squares in one row and paint them black. (Squares already painted black can be painted again, but squares not to be painted according to the modified plan should not be painted.)
Find the minimum number of times you need to perform this operation.

-----Constraints-----
 - 1 \leq N \leq 300
 - 0 \leq K \leq N
 - 0 \leq H_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
H_1 H_2 ... H_N

-----Output-----
Print the minimum number of operations required.

-----Sample Input-----
4 1
2 3 4 1

-----Sample Output-----
3

For example, by changing the value of H_3 to 2, you can create the modified artwork by the following three operations:
 - Paint black the 1-st through 4-th squares from the left in the 1-st row from the bottom.
 - Paint black the 1-st through 3-rd squares from the left in the 2-nd row from the bottom.
 - Paint black the 2-nd square from the left in the 3-rd row from the bottom.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice has a lovely piece of cloth. It has the shape of a square with a side of length $a$ centimeters. Bob also wants such piece of cloth. He would prefer a square with a side of length $b$ centimeters (where $b < a$). Alice wanted to make Bob happy, so she cut the needed square out of the corner of her piece and gave it to Bob. Now she is left with an ugly L shaped cloth (see pictures below).

Alice would like to know whether the area of her cloth expressed in square centimeters is prime. Could you help her to determine it?


-----Input-----

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

Each of the next $t$ lines describes the $i$-th test case. It contains two integers $a$ and $b~(1 \leq b < a \leq 10^{11})$ — the side length of Alice's square and the side length of the square that Bob wants.


-----Output-----

Print $t$ lines, where the $i$-th line is the answer to the $i$-th test case. Print "YES" (without quotes) if the area of the remaining piece of cloth is prime, otherwise print "NO".

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


-----Example-----
Input
4
6 5
16 13
61690850361 24777622630
34 33

Output
YES
NO
NO
YES



-----Note-----

The figure below depicts the first test case. The blue part corresponds to the piece which belongs to Bob, and the red part is the piece that Alice keeps for herself. The area of the red part is $6^2 - 5^2 = 36 - 25 = 11$, which is prime, so the answer is "YES". [Image] 

In the second case, the area is $16^2 - 13^2 = 87$, which is divisible by $3$. [Image] 

In the third case, the area of the remaining piece is $61690850361^2 - 24777622630^2 = 3191830435068605713421$. This number is not prime because $3191830435068605713421 = 36913227731 \cdot 86468472991 $.

In the last case, the area is $34^2 - 33^2 = 67$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dreamoon is standing at the position 0 on a number line. Drazil is sending a list of commands through Wi-Fi to Dreamoon's smartphone and Dreamoon follows them.

Each command is one of the following two types:   Go 1 unit towards the positive direction, denoted as '+'  Go 1 unit towards the negative direction, denoted as '-' 

But the Wi-Fi condition is so poor that Dreamoon's smartphone reports some of the commands can't be recognized and Dreamoon knows that some of them might even be wrong though successfully recognized. Dreamoon decides to follow every recognized command and toss a fair coin to decide those unrecognized ones (that means, he moves to the 1 unit to the negative or positive direction with the same probability 0.5). 

You are given an original list of commands sent by Drazil and list received by Dreamoon. What is the probability that Dreamoon ends in the position originally supposed to be final by Drazil's commands?


-----Input-----

The first line contains a string s_1 — the commands Drazil sends to Dreamoon, this string consists of only the characters in the set {'+', '-'}. 

The second line contains a string s_2 — the commands Dreamoon's smartphone recognizes, this string consists of only the characters in the set {'+', '-', '?'}. '?' denotes an unrecognized command.

Lengths of two strings are equal and do not exceed 10.


-----Output-----

Output a single real number corresponding to the probability. The answer will be considered correct if its relative or absolute error doesn't exceed 10^{ - 9}.


-----Examples-----
Input
++-+-
+-+-+

Output
1.000000000000

Input
+-+-
+-??

Output
0.500000000000

Input
+++
??-

Output
0.000000000000



-----Note-----

For the first sample, both s_1 and s_2 will lead Dreamoon to finish at the same position  + 1. 

For the second sample, s_1 will lead Dreamoon to finish at position 0, while there are four possibilites for s_2: {"+-++", "+-+-", "+--+", "+---"} with ending position {+2, 0, 0, -2} respectively. So there are 2 correct cases out of 4, so the probability of finishing at the correct position is 0.5. 

For the third sample, s_2 could only lead us to finish at positions {+1, -1, -3}, so the probability to finish at the correct position  + 3 is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is good at making pancakes. Generally he gets requests to serve N pancakes at once.
He serves them in the form of a stack.
A pancake can be treated as a circular disk with some radius.
Chef needs to take care that when he places a pancake on the top of the stack the radius of the pancake should not exceed the radius of the largest pancake in the stack by more than 1. 
Additionally all radii should be positive integers, and the bottom most pancake should have its radius as 1.
Chef wants you to find out in how many ways can he create a stack containing N pancakes.
Input
First line of the input contains T (T <= 1000) denoting the number of test cases.
T lines follow each containing a single integer N (1 <= N <= 1000) denoting the size of the required stack.
Output
For each case the output should be a single integer representing the number of ways a stack of size N can be created. As the answer can be large print it modulo 1000000007.
Example
Input
2
1
2

Output
1
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Convexity of a set of points on the plane is the size of the largest subset of points that form a convex polygon. Your task is to build a set of n points with the convexity of exactly m. Your set of points should not contain three points that lie on a straight line.

Input

The single line contains two integers n and m (3 ≤ m ≤ 100, m ≤ n ≤ 2m).

Output

If there is no solution, print "-1". Otherwise, print n pairs of integers — the coordinates of points of any set with the convexity of m. The coordinates shouldn't exceed 108 in their absolute value.

Examples

Input

4 3


Output

0 0
3 0
0 3
1 1


Input

6 3


Output

-1


Input

6 6


Output

10 0
-10 0
10 1
9 1
9 -1
0 -2


Input

7 4


Output

176166 6377
709276 539564
654734 174109
910147 434207
790497 366519
606663 21061
859328 886001

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