vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Arkadiy has lots square photos with size a × a. He wants to put some of them on a rectangular wall with size h × w. 

The photos which Arkadiy will put on the wall must form a rectangular grid and the distances between neighboring vertically and horizontally photos and also the distances between outside rows and columns of photos to the nearest bound of the wall must be equal to x, where x is some non-negative real number. Look on the picture below for better understanding of the statement.

<image>

Arkadiy haven't chosen yet how many photos he would put on the wall, however, he want to put at least one photo. Your task is to determine the minimum value of x which can be obtained after putting photos, or report that there is no way to put positive number of photos and satisfy all the constraints. Suppose that Arkadiy has enough photos to make any valid arrangement according to the constraints.

Note that Arkadiy wants to put at least one photo on the wall. The photos should not overlap, should completely lie inside the wall bounds and should have sides parallel to the wall sides.

Input

The first line contains three integers a, h and w (1 ≤ a, h, w ≤ 109) — the size of photos and the height and the width of the wall.

Output

Print one non-negative real number — the minimum value of x which can be obtained after putting the photos on the wall. The absolute or the relative error of the answer must not exceed 10 - 6.

Print -1 if there is no way to put positive number of photos and satisfy the constraints.

Examples

Input

2 18 13


Output

0.5


Input

4 4 4


Output

0


Input

3 4 3


Output

-1

Note

In the first example Arkadiy can put 7 rows of photos with 5 photos in each row, so the minimum value of x equals to 0.5.

In the second example Arkadiy can put only 1 photo which will take the whole wall, so the minimum value of x equals to 0.

In the third example there is no way to put positive number of photos and satisfy the constraints described in the statement, so the answer is -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A number is called quasibinary if its decimal representation contains only digits 0 or 1. For example, numbers 0, 1, 101, 110011 — are quasibinary and numbers 2, 12, 900 are not.

You are given a positive integer n. Represent it as a sum of minimum number of quasibinary numbers.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^6).


-----Output-----

In the first line print a single integer k — the minimum number of numbers in the representation of number n as a sum of quasibinary numbers.

In the second line print k numbers — the elements of the sum. All these numbers should be quasibinary according to the definition above, their sum should equal n. Do not have to print the leading zeroes in the numbers. The order of numbers doesn't matter. If there are multiple possible representations, you are allowed to print any of them.


-----Examples-----
Input
9

Output
9
1 1 1 1 1 1 1 1 1 

Input
32

Output
3
10 11 11

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a coach at your local university. There are $n$ students under your supervision, the programming skill of the $i$-th student is $a_i$.

You have to form $k$ teams for yet another new programming competition. As you know, the more students are involved in competition the more probable the victory of your university is! So you have to form no more than $k$ (and at least one) non-empty teams so that the total number of students in them is maximized. But you also know that each team should be balanced. It means that the programming skill of each pair of students in each team should differ by no more than $5$. Teams are independent from one another (it means that the difference between programming skills of two students from two different teams does not matter).

It is possible that some students not be included in any team at all.

Your task is to report the maximum possible total number of students in no more than $k$ (and at least one) non-empty balanced teams.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 5000$) — the number of students and the maximum number of teams, correspondingly.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is a programming skill of the $i$-th student.


-----Output-----

Print one integer — the maximum possible total number of students in no more than $k$ (and at least one) non-empty balanced teams.


-----Examples-----
Input
5 2
1 2 15 15 15

Output
5

Input
6 1
36 4 1 25 9 16

Output
2

Input
4 4
1 10 100 1000

Output
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that outputs the transpose of a matrix - a new matrix
where the columns and rows of the original are swapped.

For example, the transpose of:
  
    | 1 2 3 |
    | 4 5 6 |

is

    | 1 4 |
    | 2 5 |
    | 3 6 |

The input to your function will be an array of matrix rows. You can
assume that each row has the same length, and that the height and
width of the matrix are both positive.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya is a big fish lover, and his parents gave him an aquarium for the New Year. Vasya does not have a degree in ichthyology, so he thinks that filling a new aquarium with eels is a good idea. Unfortunately, eels are predators, so Vasya decided to find out how dangerous this idea was.

Getting into one aquarium, eels fight each other until exactly one fish remains. When two eels fight, the big one eats the smaller one (if their weights are equal, then one of them will still eat the other). Namely, let n eels be initially in an aquarium, and the i-th of them have a weight of x_i. Then n-1 battles will occur between them, as a result of which, only one eel will survive. In a battle of two eels with weights a and b, where a ≤ b, eel of weight a will be eaten and disappear from the aquarium, and eel of weight b will increase its weight to a+b.

A battle between two eels with weights a and b, where a ≤ b, is considered dangerous if b ≤ 2 a. For a given set of eels, danger is defined as the maximum number of dangerous battles that can occur among these eels if they are placed in one aquarium.

Now Vasya is planning, which eels he wants to put into an aquarium. He has some set of eels (initially empty). He makes a series of operations with this set. With each operation, he either adds one eel in the set, or removes one eel from the set. Vasya asks you to calculate the danger of the current set of eels after each operation.

Input

The first line of input contains a single integer q (1 ≤ q ≤ 500 000), the number of operations that Vasya makes. The next q lines describe operations. Each operation has one of two types :

  * + x describes the addition of one eel of weight x to the set (1 ≤ x ≤ 10^9). Note that in the set there can be several eels of the same weight. 
  * - x describes the removal of one eel of weight x from a set, and it is guaranteed that there is a eel of such weight in the set. 

Output

For each operation, output single integer, the danger of the set of eels after this operation.

Examples

Input


2
+ 1
- 1


Output


0
0


Input


4
+ 1
+ 3
+ 7
- 3


Output


0
0
1
0


Input


9
+ 2
+ 2
+ 12
- 2
- 2
+ 4
+ 1
+ 1
- 12


Output


0
1
1
0
0
0
0
3
2

Note

In the third example, after performing all the operations, the set of eels looks like \{1, 1, 4\}. For this set of eels, there are several possible scenarios, if all of them are placed in one aquarium:

  * The eel of weight 4 eats the eel of weight 1, and then the second eel of weight 1. In this case, none of the battles are dangerous. 
  * The eel of weight 1 eats the eel of weight 1, and this battle is dangerous. Now there are two eels in the aquarium, their weights are 4 and 2. The big one eats the small one, and this battle is also dangerous. In this case, the total number of dangerous battles will be 2. 



Thus, the danger of this set of eels is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of size N and you have to tell whether the array is perfect or not. An array is said to be perfect if its reverse array matches the original array. If the array is perfect then return True else return False.
Example 1:
Input : Arr[] = {1, 2, 3, 2, 1}
Output : PERFECT
Explanation:
Here we can see we have [1, 2, 3, 2, 1] 
if we reverse it we can find [1, 2, 3, 2, 1]
which is the same as before.
So, the answer is PERFECT.
Example 2:
Input : Arr[] = {1, 2, 3, 4, 5}
Output : NOT PERFECT
User Task:
The task is to complete the function IsPerfect(), which takes an array (a), size of the array (n), and returns the boolean value true if it is Perfect else false. The driver will print itself "PERFECT" or "NOT PERFECT" accordingly.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 2 * 10^{5}
1 ≤ a_{i} ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Crunching Numbers Just for You

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are developing a new feature for the website which sells airline tickets: being able to sort tickets by price! You have already extracted the tickets' prices, so there's just the last step to be done...

You are given an array of integers. Sort it in non-descending order.

Input Specification:
The input consists of a single line of space-separated integers. The first number is *n* (1<=≤<=*n*<=≤<=10) — the size of the array. The following *n* numbers are the elements of the array (1<=≤<=*a**i*<=≤<=100).

Output Specification:
Output space-separated elements of the sorted array.

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

Demo Output:
['1 2 3 \n']

Note:
Remember, this is a very important feature, and you have to make sure the customers appreciate it!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a tree with N vertices. The vertices are numbered 1, 2, ..., N. The i-th (1 ≦ i ≦ N - 1) edge connects the two vertices A_i and B_i.
Takahashi wrote integers into K of the vertices. Specifically, for each 1 ≦ j ≦ K, he wrote the integer P_j into vertex V_j. The remaining vertices are left empty. After that, he got tired and fell asleep.
Then, Aoki appeared. He is trying to surprise Takahashi by writing integers into all empty vertices so that the following condition is satisfied:
 - Condition: For any two vertices directly connected by an edge, the integers written into these vertices differ by exactly 1.
Determine if it is possible to write integers into all empty vertices so that the condition is satisfied. If the answer is positive, find one specific way to satisfy the condition.

-----Constraints-----
 - 1 ≦ N ≦ 10^5
 - 1 ≦ K ≦ N
 - 1 ≦ A_i, B_i ≦ N (1 ≦ i ≦ N - 1)
 - 1 ≦ V_j ≦ N (1 ≦ j ≦ K) (21:18, a mistake in this constraint was corrected)
 - 0 ≦ P_j ≦ 10^5 (1 ≦ j ≦ K)
 - The given graph is a tree.
 - All v_j are distinct.

-----Input-----
The input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}
K
V_1 P_1
V_2 P_2
:
V_K P_K

-----Output-----
If it is possible to write integers into all empty vertices so that the condition is satisfied, print Yes. Otherwise, print No.
If it is possible to satisfy the condition, print N lines in addition. The v-th (1 ≦ v ≦ N) of these N lines should contain the integer that should be written into vertex v. If there are multiple ways to satisfy the condition, any of those is accepted.

-----Sample Input-----
5
1 2
3 1
4 3
3 5
2
2 6
5 7

-----Sample Output-----
Yes
5
6
6
5
7

The figure below shows the tree when Takahashi fell asleep. For each vertex, the integer written beside it represents the index of the vertex, and the integer written into the vertex is the integer written by Takahashi.
Aoki can, for example, satisfy the condition by writing integers into the remaining vertices as follows:
This corresponds to Sample Output 1. Note that other outputs that satisfy the condition will also be accepted, such as:
Yes
7
6
8
7
7


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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Winter is here at the North and the White Walkers are close. John Snow has an army consisting of *n* soldiers. While the rest of the world is fighting for the Iron Throne, he is going to get ready for the attack of the White Walkers.

He has created a method to know how strong his army is. Let the *i*-th soldier’s strength be *a**i*. For some *k* he calls *i*1,<=*i*2,<=...,<=*i**k* a clan if *i*1<=&lt;<=*i*2<=&lt;<=*i*3<=&lt;<=...<=&lt;<=*i**k* and *gcd*(*a**i*1,<=*a**i*2,<=...,<=*a**i**k*)<=&gt;<=1 . He calls the strength of that clan *k*·*gcd*(*a**i*1,<=*a**i*2,<=...,<=*a**i**k*). Then he defines the strength of his army by the sum of strengths of all possible clans.

Your task is to find the strength of his army. As the number may be very large, you have to print it modulo 1000000007 (109<=+<=7).

Greatest common divisor (gcd) of a sequence of integers is the maximum possible integer so that each element of the sequence is divisible by it.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=200000) — the size of the army.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=1000000) — denoting the strengths of his soldiers.

Output Specification:
Print one integer — the strength of John Snow's army modulo 1000000007 (109<=+<=7).

Demo Input:
['3\n3 3 1\n', '4\n2 3 4 6\n']

Demo Output:
['12\n', '39\n']

Note:
In the first sample the clans are {1}, {2}, {1, 2} so the answer will be 1·3 + 1·3 + 2·3 = 12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Salmon received an array $A$ of size $N$ and an array $B$ of size $M$ for Christmas. He would like to move all the elements in $B$ to $A$ using a special method described below.

While $B$ is not empty, Salmon does the following operations in order:

* Remove and store the leftmost element off of B (let's call this element $X$).
* Place $X$ at the start of $A$.
* Keep swapping $X$ and the element to the right of it repeatedly until $X$ is at the rightmost position of $A$ or $X$ is greater or equal to the element to the right of it.

Before performing the operations, Salmon can rearrange both A and B in any order once. He would like to do as little work as possible -- determine the minimum possible amount of swaps.

------ Input: ------
The first line of input will consist of a two space-separated integers, $N$ and $M$ ($1 ≤ N, M ≤ 2*10^{5}$).

The next line will consist of $N$ space-separated integers, with the $i$-th input representing $A[i]$ ($-10^{9} ≤ A[i] ≤ 10^{9}$).

The next line will consist of $M$ space-separated integers, with the $i$-th input representing $B[i]$ ($-10^{9} ≤ B[i] ≤ 10^{9}$).

------ Output: ------
Output a single integer, the minimum number of swaps required.

------ Subtasks: ------
* Subtask 1 [15 points]: $A[i] = 1, B[i] = 1$ for all $i$.
* Subtask 2 [30 points]: $N, M ≤ 10^{3}$.
* Subtask 3 [55 points]: No additional constraints.

------ Note: ------
The answer may be greater than the limit for a 32-bit integer. Use long long instead of int for C++ and long for Java. Please check your language documentation for other languages on how to use 64-bit integers. Note that Python solutions won't encounter a problem as it uses BigIntegers by default.

----- Sample Input 1 ------ 
5 3
10 5 2 5 4
3 1 2
----- Sample Output 1 ------ 
5
----- explanation 1 ------ 
Salmon can reorder $A$ to be $[2, 10, 5, 4, 5]$ and $B$ to be $[1, 2, 3]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima is living in a dormitory, as well as some cockroaches.

At the moment 0 Dima saw a cockroach running on a table and decided to kill it. Dima needs exactly T seconds for aiming, and after that he will precisely strike the cockroach and finish it.

To survive the cockroach has to run into a shadow, cast by round plates standing on the table, in T seconds. Shadow casted by any of the plates has the shape of a circle. Shadow circles may intersect, nest or overlap arbitrarily.

The cockroach uses the following strategy: first he equiprobably picks a direction to run towards and then runs towards it with the constant speed v. If at some moment t ≤ T it reaches any shadow circle, it immediately stops in the shadow and thus will stay alive. Otherwise the cockroach is killed by the Dima's precise strike. Consider that the Dima's precise strike is instant.

Determine the probability of that the cockroach will stay alive.

Input

In the first line of the input the four integers x0, y0, v, T (|x0|, |y0| ≤ 109, 0 ≤ v, T ≤ 109) are given — the cockroach initial position on the table in the Cartesian system at the moment 0, the cockroach's constant speed and the time in seconds Dima needs for aiming respectively.

In the next line the only number n (1 ≤ n ≤ 100 000) is given — the number of shadow circles casted by plates.

In the next n lines shadow circle description is given: the ith of them consists of three integers xi, yi, ri (|xi|, |yi| ≤ 109, 0 ≤ r ≤ 109) — the ith shadow circle on-table position in the Cartesian system and its radius respectively.

Consider that the table is big enough for the cockroach not to run to the table edges and avoid Dima's precise strike.

Output

Print the only real number p — the probability of that the cockroach will stay alive.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.

Examples

Input

0 0 1 1
3
1 1 1
-1 -1 1
-2 2 1


Output

0.50000000000

Input

0 0 1 0
1
1 0 1


Output

1.00000000000

Note

The picture for the first sample is given below. 

<image>

Red color stands for points which being chosen as the cockroach's running direction will cause him being killed, green color for those standing for survival directions. Please note that despite containing a circle centered in ( - 2, 2) a part of zone is colored red because the cockroach is not able to reach it in one second.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vidhi went to a magic show last week where she was astounded by a magic trick performed by the great Mandwarf, the brown. His trick was as follows :



    Ask a volunteer from the audience to write down a list L of N integers. 
    

    Ask another volunteer from the audience to provide three integers A, B, C


    Ask another volunteer from the audience to provide N length string called S where each letter is either 'R', 'A' or 'M'
    

    Close his eyes for a split second and give the output of The Ancient Algorithm on this input. 
    


We all know that The Ancient Algorithm is as follows :


for i from 1 to N do 

    if i^th letter of S is 'R'
        reverse L[i...N]
    else if i^th letter of S is 'A'
        add A to all numbers of L[i..N].
    else if i^th letter of S is 'M'
        multiply B to all numbers of L[i..N].

    for all number in L[i..N], module them by C.

    announce L[i] out loud

end


Vidhi's boyfriend got jealous when he saw her getting impressed by Mandwarf, the brown's wisdom. He wants to learn the trick to gain her undivided admiration. How about you help him?


Constraints:
1 ≤ T ≤ 100 
1 ≤ N ≤ 1000
0 ≤ L[i] ≤ 10^18
0 ≤ A,B ≤ 10^18
2 ≤ C ≤ 10^18

Input
First line contains a single integer T, denoting the number of test cases. Then follow T test case scenarios. Each test case begins with an integer N, the size of the list L. Then in next line, you'd find N space separated integers - the list L itself. In next line, there'd be three space separated integers A, B, C followed by string S in the next line. 


Output
For each test case you've to output N space separated integers - the numbers announced by Mandwarf, the brown. 


Example

Input:
2
3
1 1 1
2 3 1000
ARM
4
1 2 3 4
0 1 1000
AMAM

Output:
3 3 9
1 2 3 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: New Year and Domino

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
They say "years are like dominoes, tumbling one after the other". But would a year fit into a grid? I don't think so.

Limak is a little polar bear who loves to play. He has recently got a rectangular grid with *h* rows and *w* columns. Each cell is a square, either empty (denoted by '.') or forbidden (denoted by '#'). Rows are numbered 1 through *h* from top to bottom. Columns are numbered 1 through *w* from left to right.

Also, Limak has a single domino. He wants to put it somewhere in a grid. A domino will occupy exactly two adjacent cells, located either in one row or in one column. Both adjacent cells must be empty and must be inside a grid.

Limak needs more fun and thus he is going to consider some queries. In each query he chooses some rectangle and wonders, how many way are there to put a single domino inside of the chosen rectangle?

Input Specification:
The first line of the input contains two integers *h* and *w* (1<=≤<=*h*,<=*w*<=≤<=500) – the number of rows and the number of columns, respectively.

The next *h* lines describe a grid. Each line contains a string of the length *w*. Each character is either '.' or '#' — denoting an empty or forbidden cell, respectively.

The next line contains a single integer *q* (1<=≤<=*q*<=≤<=100<=000) — the number of queries.

Each of the next *q* lines contains four integers *r*1*i*, *c*1*i*, *r*2*i*, *c*2*i* (1<=≤<=*r*1*i*<=≤<=*r*2*i*<=≤<=*h*,<=1<=≤<=*c*1*i*<=≤<=*c*2*i*<=≤<=*w*) — the *i*-th query. Numbers *r*1*i* and *c*1*i* denote the row and the column (respectively) of the upper left cell of the rectangle. Numbers *r*2*i* and *c*2*i* denote the row and the column (respectively) of the bottom right cell of the rectangle.

Output Specification:
Print *q* integers, *i*-th should be equal to the number of ways to put a single domino inside the *i*-th rectangle.

Demo Input:
['5 8\n....#..#\n.#......\n##.#....\n##..#.##\n........\n4\n1 1 2 3\n4 1 4 1\n1 2 4 5\n2 5 5 8\n', '7 39\n.......................................\n.###..###..#..###.....###..###..#..###.\n...#..#.#..#..#.........#..#.#..#..#...\n.###..#.#..#..###.....###..#.#..#..###.\n.#....#.#..#....#.....#....#.#..#..#.#.\n.###..###..#..###.....###..###..#..###.\n.......................................\n6\n1 1 3 20\n2 10 6 30\n2 10 7 30\n2 2 7 7\n1 7 7 7\n1 8 7 8\n']

Demo Output:
['4\n0\n10\n15\n', '53\n89\n120\n23\n0\n2\n']

Note:
A red frame below corresponds to the first query of the first sample. A domino can be placed in 4 possible ways.

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