A lot of people in Berland hates rain, but you do not. Rain pacifies, puts your thoughts in order. By these years you have developed a good tradition — when it rains, you go on the street and stay silent for a moment, contemplate all around you, enjoy freshness, think about big deeds you have to do.
Today everything had changed quietly. You went on the street with a cup contained water, your favorite drink. In a moment when you were drinking a water you noticed that the process became quite long: the cup still contained water because of rain. You decided to make a formal model of what was happening and to find if it was possible to drink all water in that situation.
Thus, your cup is a cylinder with diameter equals d centimeters. Initial level of water in cup equals h centimeters from the bottom.
You drink a water with a speed equals v milliliters per second. But rain goes with such speed that if you do not drink a water from the cup, the level of water increases on e centimeters per second. The process of drinking water from the cup and the addition of rain to the cup goes evenly and continuously.
Find the time needed to make the cup empty or find that it will never happen. It is guaranteed that if it is possible to drink all water, it will happen not later than after 104 seconds.
Note one milliliter equals to one cubic centimeter.
The only line of the input contains four integer numbers d, h, v, e (1 ≤ d, h, v, e ≤ 104), where:
- d — the diameter of your cylindrical cup,
- h — the initial level of water in the cup,
- v — the speed of drinking process from the cup in milliliters per second,
- e — the growth of water because of rain if you do not drink from the cup.
If it is impossible to make the cup empty, print "NO" (without quotes).
Otherwise print "YES" (without quotes) in the first line. In the second line print a real number — time in seconds needed the cup will be empty. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4. It is guaranteed that if the answer exists, it doesn't exceed 104.
1 2 3 100
NO
1 1 1 1
YES
3.659792366325
In the first example the water fills the cup faster than you can drink from it.
In the second example area of the cup's bottom equals to 
, thus we can conclude that you decrease the level of water by 
centimeters per second. At the same time water level increases by 1 centimeter per second due to rain. Thus, cup will be empty in 
seconds.
As some of you know, cubism is a trend in art, where the problem of constructing volumetrical shape on a plane with a combination of three-dimensional geometric shapes comes to the fore.
A famous sculptor Cicasso, whose self-portrait you can contemplate, hates cubism. He is more impressed by the idea to transmit two-dimensional objects through three-dimensional objects by using his magnificent sculptures. And his new project is connected with this. Cicasso wants to make a coat for the haters of anticubism. To do this, he wants to create a sculpture depicting a well-known geometric primitive — convex polygon.
Cicasso prepared for this a few blanks, which are rods with integer lengths, and now he wants to bring them together. The i-th rod is a segment of length li.
The sculptor plans to make a convex polygon with a nonzero area, using all rods he has as its sides. Each rod should be used as a side to its full length. It is forbidden to cut, break or bend rods. However, two sides may form a straight angle 
.
Cicasso knows that it is impossible to make a convex polygon with a nonzero area out of the rods with the lengths which he had chosen. Cicasso does not want to leave the unused rods, so the sculptor decides to make another rod-blank with an integer length so that his problem is solvable. Of course, he wants to make it as short as possible, because the materials are expensive, and it is improper deed to spend money for nothing.
Help sculptor!
The first line contains an integer n (3 ≤ n ≤ 105) — a number of rod-blanks.
The second line contains n integers li (1 ≤ li ≤ 109) — lengths of rods, which Cicasso already has. It is guaranteed that it is impossible to make a polygon with n vertices and nonzero area using the rods Cicasso already has.
Print the only integer z — the minimum length of the rod, so that after adding it it can be possible to construct convex polygon with (n + 1) vertices and nonzero area from all of the rods.
3
1 2 1
1
5
20 4 3 2 1
11
In the first example triangle with sides {1 + 1 = 2, 2, 1} can be formed from a set of lengths {1, 1, 1, 2}.
In the second example you can make a triangle with lengths {20, 11, 4 + 3 + 2 + 1 = 10}.
First-rate specialists graduate from Berland State Institute of Peace and Friendship. You are one of the most talented students in this university. The education is not easy because you need to have fundamental knowledge in different areas, which sometimes are not related to each other.
For example, you should know linguistics very well. You learn a structure of Reberland language as foreign language. In this language words are constructed according to the following rules. First you need to choose the "root" of the word — some string which has more than 4 letters. Then several strings with the length 2 or 3 symbols are appended to this word. The only restriction — it is not allowed to append the same string twice in a row. All these strings are considered to be suffixes of the word (this time we use word "suffix" to describe a morpheme but not the few last characters of the string as you may used to).
Here is one exercise that you have found in your task list. You are given the word s. Find all distinct strings with the length 2 or 3, which can be suffixes of this word according to the word constructing rules in Reberland language.
Two strings are considered distinct if they have different length or there is a position in which corresponding characters do not match.
Let's look at the example: the word abacabaca is given. This word can be obtained in the following ways: 
, where the root of the word is overlined, and suffixes are marked by "corners". Thus, the set of possible suffixes for this word is {aca, ba, ca}.
The only line contains a string s (5 ≤ |s| ≤ 104) consisting of lowercase English letters.
On the first line print integer k — a number of distinct possible suffixes. On the next k lines print suffixes.
Print suffixes in lexicographical (alphabetical) order.
abacabaca
3
aca
ba
ca
abaca
0
The first test was analysed in the problem statement.
In the second example the length of the string equals 5. The length of the root equals 5, so no string can be used as a suffix.
A famous sculptor Cicasso goes to a world tour!
Well, it is not actually a world-wide. But not everyone should have the opportunity to see works of sculptor, shouldn't he? Otherwise there will be no any exclusivity. So Cicasso will entirely hold the world tour in his native country — Berland.
Cicasso is very devoted to his work and he wants to be distracted as little as possible. Therefore he will visit only four cities. These cities will be different, so no one could think that he has "favourites". Of course, to save money, he will chose the shortest paths between these cities. But as you have probably guessed, Cicasso is a weird person. Although he doesn't like to organize exhibitions, he likes to travel around the country and enjoy its scenery. So he wants the total distance which he will travel to be as large as possible. However, the sculptor is bad in planning, so he asks you for help.
There are n cities and m one-way roads in Berland. You have to choose four different cities, which Cicasso will visit and also determine the order in which he will visit them. So that the total distance he will travel, if he visits cities in your order, starting from the first city in your list, and ending in the last, choosing each time the shortest route between a pair of cities — will be the largest.
Note that intermediate routes may pass through the cities, which are assigned to the tour, as well as pass twice through the same city. For example, the tour can look like that: 
. Four cities in the order of visiting marked as overlines: [1, 5, 2, 4].
Note that Berland is a high-tech country. So using nanotechnologies all roads were altered so that they have the same length. For the same reason moving using regular cars is not very popular in the country, and it can happen that there are such pairs of cities, one of which generally can not be reached by car from the other one. However, Cicasso is very conservative and cannot travel without the car. Choose cities so that the sculptor can make the tour using only the automobile. It is guaranteed that it is always possible to do.
In the first line there is a pair of integers n and m (4 ≤ n ≤ 3000, 3 ≤ m ≤ 5000) — a number of cities and one-way roads in Berland.
Each of the next m lines contains a pair of integers ui, vi (1 ≤ ui, vi ≤ n) — a one-way road from the city ui to the city vi. Note that ui and vi are not required to be distinct. Moreover, it can be several one-way roads between the same pair of cities.
Print four integers — numbers of cities which Cicasso will visit according to optimal choice of the route. Numbers of cities should be printed in the order that Cicasso will visit them. If there are multiple solutions, print any of them.
8 9
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 8
8 5
2 1 8 7
Let d(x, y) be the shortest distance between cities x and y. Then in the example d(2, 1) = 3, d(1, 8) = 7, d(8, 7) = 3. The total distance equals 13.
Group of Berland scientists, with whom you have a close business relationship, makes a research in the area of peaceful nuclear energy. In particular, they found that a group of four nanobots, placed on a surface of a plate, can run a powerful chain reaction under certain conditions.
To be precise, researchers introduced a rectangular Cartesian coordinate system on a flat plate and selected four distinct points with integer coordinates where bots will be placed initially. Next each bot will be assigned with one of the four directions (up, down, left or right) parallel to the coordinate axes. After that, each bot is shifted by an integer distance (which may be different for different bots) along its direction. The chain reaction starts, if the bots are in the corners of a square with positive area with sides parallel to the coordinate axes. Each corner of the square must contain one nanobot. This reaction will be stronger, if bots spend less time to move. We can assume that bots move with unit speed. In other words, the lesser is the maximum length traveled by bot, the stronger is reaction.
Scientists have prepared a set of plates and selected starting position for the bots for each plate. Now they ask you to assign the direction for each bot to move after landing such that the maximum length traveled by bot is as small as possible.
The first line contains an integer number t (1 ≤ t ≤ 50) — the number of plates.
t descriptions of plates follow. A description of each plate consists of four lines. Each line consists of a pair of integers numbers xi, yi ( - 108 ≤ xi, yi ≤ 108) — coordinates of the next bot. All bots are in different locations.
Note, though, the problem can include several records in one test, you can hack other people's submissions only with the test of one plate, i.e. parameter t in a hack test should be equal to 1.
Print answers for all plates separately. First goes a single integer number in a separate line. If scientists have made an unfortunate mistake and nanobots are not able to form the desired square, print -1. Otherwise, print the minimum possible length of the longest bot's path.
If a solution exists, in the next four lines print two integer numbers — positions of each bot after moving. Print bots' positions in the order they are specified in the input data.
If there are multiple solution, you can print any of them.
2
1 1
1 -1
-1 1
-1 -1
1 1
2 2
4 4
6 6
0
1 1
1 -1
-1 1
-1 -1
-1