import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.StringTokenizer;

import java.util.*;
import static java.lang.Math.*;

public class ProblemC {
	public static void main(String[] args) {
		FastScanner input = new FastScanner();
		int n = input.nextInt();
		int radius = input.nextInt();
		ArrayList<Integer> diskXToFall = new ArrayList<Integer>();
		for (int a = 0; a < n; a++) {
			diskXToFall.add(input.nextInt());
		}
		ArrayList<P> stationaryDisks = new ArrayList<P>();
		for (int a = 0; a < n; a++) {
			double highCollision = radius;
			for (P i : stationaryDisks) {
				if (Math.abs(diskXToFall.get(a) - i.x) - 1e-8 <= 2 * radius) {
					double hypot = 2 * radius;
					double leg = Math.abs(diskXToFall.get(a) - i.x);
					double yOffset = Math.sqrt(Math.abs(hypot * hypot - leg * leg));
					highCollision = Math.max(highCollision, yOffset + i.y);
				}
			}
			stationaryDisks.add(new P(diskXToFall.get(a), highCollision));
		}
		for(int a = 0; a < n; a++) {
			System.out.print(stationaryDisks.get(a).y + " ");
		}
		

	}

	static class P implements Comparable<P> {
		final double x, y;

		P(double x, double y) {
			this.x = x;
			this.y = y;
		}

		P sub(P that) {
			return new P(x - that.x, y - that.y);
		}

		P add(P that) {
			return new P(x + that.x, y + that.y);
		}

		double dot(P that) {
			return x * that.x + y * that.y;
		}

		P scale(double s) {
			return new P(x * s, y * s);
		}

		// Use hypot() only if intermediate overflow must be avoided; very slow
		double length() {
			return sqrt(x * x + y * y);
		}

		double length2() {
			return x * x + y * y;
		}

		P leftNormal() {
			return new P(-y, x);
		} // rotateCCW(90deg)

		P rightNormal() {
			return new P(y, -x);
		} // rotateCW(90deg)

		P normalize() {
			double n = length();
			return n > 0 ? new P(x / n, y / n) : origin();
		}

		P scaleToLength(double l) {
			return normalize().scale(l);
		}

		P project(P a) {
			return scale(a.dot(this) / length2());
		}

		P reflect(P a) {
			return project(a).scale(2.0).sub(a);
		}

		// use if sin, cos are known
		P rotateCCW(double sinT, double cosT) {
			return new P(x * cosT - y * sinT, x * sinT + y * cosT);
		}

		P rotateCW(double sinT, double cosT) {
			return rotateCCW(-sinT, cosT);
		}

		P rotate(double theta) {
			return rotateCCW(sin(theta), cos(theta));
		}

		// angle to horizontal (1, 0); result is in [-pi, pi] rad or (-180-180) deg
		double theta() {
			return atan2(y, x);
		}

		// angle between two vectors, result is in [0, pi] rad (0-180 deg)
		double angleTo(P a) {
			return acos(this.dot(a) / this.length() / a.length());
		}

		boolean isOrigin() {
			return x == 0 && y == 0;
		}

		public String toString() {
			return String.format("(%f,%f)", this.x, this.y);
		}

		static P read(Scanner s) {
			return new P(s.nextDouble(), s.nextDouble());
		}

		static P origin() {
			return new P(0, 0);
		}

		double det(P that) {
			return this.x * that.y - this.y * that.x;
		}

		double crossproduct(P that) {
			return this.det(that);
		}

		P half(P q) {
			return normalize().add(q.normalize());
		}

		double dist(P to) {
			return sub(to).length();
		}

		double signedParallelogramArea(P b, P c) {
			return (b.sub(this).crossproduct(c.sub(this)));
		}

		boolean isCollinearWith(P b, P c) {
			return abs(signedParallelogramArea(b, c)) <= EPS;
		}

		// is going from this to b to c a CCW turn? Do not use if points may be
		// collinear
		boolean isCCW(P b, P c) {
			return signedParallelogramArea(b, c) > 0;
		}

		double signedTriangleArea(P b, P c) {
			return signedParallelogramArea(b, c) / 2.0;
		}

		// memory-optimized version of this.sub(to).length2() that avoids an
		// intermediate object
		double dist2(P to) {
			double dx = this.x - to.x;
			double dy = this.y - to.y;
			return dx * dx + dy * dy;
		}

		/**
		 * Compute x for a * x + b = 0 and ||x|| = C where 'this' is a. Care must be
		 * taken to handle the case where either a.x or a.y is near zero.
		 */
		P[] solveDotProductConstrainedByNorm(double b, double C) {
			P a = this;
			if (a.isOrigin())
				throw new Error("degenerate case");

			boolean transpose = abs(a.x) > abs(a.y);
			a = transpose ? new P(a.y, a.x) : a;

			Double[] x = solvequadratic(a.length2(), 2.0 * b * a.x, b * b - a.y * a.y * C * C);
			P[] p = new P[x.length];
			for (int i = 0; i < x.length; i++) {
				double x1 = x[i];
				double x2 = ((-b - a.x * x1) / a.y);
				p[i] = transpose ? new P(x2, x1) : new P(x1, x2);
			}
			return p;
		}

		@Override
		public int compareTo(P that) {
			if (abs(this.x - that.x) > EPS)
				return Double.compare(this.x, that.x);
			return Double.compare(this.y, that.y);
		}
	}

	static class HP extends P { // Hashable Point
		HP(double x, double y) {
			super(x, y);
		}

		@Override
		public int hashCode() {
			return Double.hashCode(x + 32768 * y);
		}

		@Override
		public boolean equals(Object _that) {
			HP that = (HP) _that;
			return this.x == that.x && this.y == that.y;
		}
	}

	/**
	 * Sort points by polar angle relative to center, using trig. This is a
	 * counter-clockwise sort with zero at 3 o'clock.
	 */
	static Comparator<P> makePolarAngleComparatorTrig(final P center) {
		return new Comparator<P>() {
			public int compare(P a, P b) {
				double thetaa = a.sub(center).theta();
				double thetab = b.sub(center).theta();
				if (thetaa < 0)
					thetaa += 2 * PI;
				if (thetab < 0)
					thetab += 2 * PI;
				int c = Double.compare(thetaa, thetab);
				if (c != 0)
					return c;
				return Double.compare(b.x, a.x); // arbitrary tie-breaker
			}
		};
	}

	/**
	 * Sort points by polar angle relative to center, w/o trig. This is a
	 * counter-clockwise sort with zero at 3 o'clock.
	 */
	static Comparator<P> makePolarAngleComparator(final P center) {
		return new Comparator<P>() {
			public int compare(P a, P b) {
				// orientation() requires that a and b lie in the same half-plane
				if (a.y >= center.y && b.y < center.y)
					return -1;
				if (b.y >= center.y && a.y < center.y)
					return 1;
				int orientation = (int) Math.signum(center.signedParallelogramArea(b, a));
				if (orientation != 0)
					return orientation;
				return Double.compare(b.x, a.x); // arbitrary tie-breaker
			}
		};
	}

	/*
	 * Solve a * x^2 + b * x + c == 0 Returns 0, 1, or 2 solutions. If 2 solutions
	 * x1, x2, guarantees that x1 < x2
	 */
	static Double[] solvequadratic(double a, double b, double c) {
		double D = b * b - 4 * a * c;
		if (D < -EPS)
			return new Double[] {};
		D = max(D, 0);
		if (D == 0)
			return new Double[] { -b / 2.0 / a };
		double d = sqrt(D);
		// Numerically more stable, see
		// https://en.wikipedia.org/wiki/Loss_of_significance#A_better_algorithm
		if (signum(b) == 0)
			return new Double[] { d / 2.0 / a, -d / 2.0 / a };
		double x1 = (-b - signum(b) * d) / (2 * a);
		double x2 = c / (a * x1);
		return new Double[] { Math.min(x1, x2), Math.max(x1, x2) };
	}

	/*
	 * The Line/Circle classes provide a number of methods that require dealing with
	 * floating point precision issues. Default EPS to a suitable value, such as
	 * 1e-6, which should work for many problems in which the input coordinates are
	 * in integers and subsequently inexact floating point values are being
	 * computed.
	 */
	static double EPS = 1e-6;

	/*
	 * A line denoted by two points p and q. For internal computations, we use the
	 * parametric representation of the line as p + t d where d = q - p. For
	 * convenience, we compute and store d in the constructor. Most methods hide the
	 * parametric representation of the line, but it is exposed via
	 * getPointFromParameter and intersectionParameters for those problems that need
	 * it.
	 *
	 * The line may be interpreted either as a line segment denoted by the two end
	 * points, or as the infinite line determined by these two points. Intersection
	 * methods are provided for both cases.
	 */
	static class Line {
		P p, q, d;

		Line(P p, P q) {
			this.p = p;
			this.q = q;
			d = q.sub(p);
		}

		P getPointFromParameter(double t) {
			return p.add(d.scale(t));
		}

		// reflect vector across vector (as if line originated at (0, 0))
		P reflect(P d2) {
			return d.reflect(d2);
		}

		// reflect point across (infinite) line
		P reflectPoint(P r) {
			return reflect(r.sub(p)).add(p);
		}

		// project p onto this (infinite) line. Returns point on line
		P project(P a) {
			return p.add(d.project(a.sub(p)));
		}

		// return distance of point P from this (infinite) line.
		double distance(P a) {
			return project(a).dist(a);
		}

		@Override
		public String toString() {
			return String.format("[%s => %s]", p, q);
		}

		/*
		 * Point of intersection of this line segment with another line segment. Returns
		 * only points that lie inside both line segments, else null.
		 *
		 * Result may include points "just outside" the bounds, given EPS.
		 */
		P intersectsInBounds(Line l) {
			double[] st = intersectionParameters(l);
			if (st == null)
				return null;

			// check that point of intersection is in direction 'd'
			// and within segment bounds
			double s = st[0];
			double t = st[1];
			if (s >= -EPS && s <= 1 + EPS && -EPS <= t && t <= 1 + EPS)
				return getPointFromParameter(s);

			return null;
		}

		/*
		 * Point of intersection of this (infinite) line with other (infinite) line.
		 * Return null if collinear.
		 */
		P intersects(Line l) {
			double[] st = intersectionParameters(l);
			if (st != null)
				return getPointFromParameter(st[0]);
			return null;
		}

		/*
		 * Intersect this line with that line Solves: this.p + s * this.d == l.p + t l.d
		 * Return null if lines are collinear Else returns [s, t].
		 */
		double[] intersectionParameters(Line l) {
			P dneg = p.sub(q);
			double D = l.d.det(dneg);
			// Use Cramer's rule; see text
			if (D == 0.0)
				return null;

			P rp = p.sub(l.p);
			return new double[] { l.d.det(rp) / D, rp.det(dneg) / D };
		}

		/*
		 * Compute points of intersection of this infinite line with a circle. Computes
		 * projection 'x' of c.c onto line, then computes x +/- d.scaleToLength(h) where
		 * h is computed via Pythagoras. Sorted by decreasing 't' (as would be used in
		 * getPointFromParameter)
		 *
		 * May return two points even if line is a tangent.
		 */
		P[] intersectsCircle(Circle c) {
			P x = project(c.c);
			double D = x.dist(c.c);
			// outside by more than EPS
			if (D > c.R + EPS)
				return new P[0];
			double h = sqrt(max(0, c.R * c.R - D * D));
			if (h == 0)
				return new P[] { x }; // EPS (!?)
			return new P[] { x.add(d.scaleToLength(h)), x.add(d.scaleToLength(-h)) };
		}

		/*
		 * Compute points of intersection of this infinite line with a circle.
		 *
		 * Solves a + t * b = c + r subject to ||r|| = R Returns zero, one, or two
		 * points on the periphery, e.g. c + r[0,1], sorted by decreasing 't'.
		 * Alternative version which requires solving quadratic equation.
		 *
		 * Careful: set EPS if you need to handle round-off error in discriminant.
		 */
		P[] intersectsCircleAlternative(Circle c) {
			P ca = c.c.sub(p);
			P d = q.sub(p);
			Double[] t = solvequadratic(d.length2(), -2 * d.dot(ca), ca.length2() - c.R * c.R);
			P[] r = new P[t.length];
			for (int i = 0; i < t.length; i++)
				r[i] = p.add(d.scale(t[i]));
			return r;
		}

		/**
		 * Is r contained within the line segment spanned by p/q, including their
		 * endpoints?
		 */
		boolean isInBounds(P r) {
			return abs(p.dist(q) - p.dist(r) - q.dist(r)) <= EPS;
		}

		/**
		 * Is r on the infinite line?
		 */
		boolean isOnLine(P r) {
			return r.isCollinearWith(p, q);
		}
	}

	/**
	 * Alternative line implementation using the "general form" equation.
	 *
	 * a * x + b * y + c = 0
	 *
	 * This is provided for problems in which a line may be given in general form in
	 * the input. Compared to class Line, GLine: - is shorter, particularly when
	 * only line/line and line/circle intersections are required. - does not support
	 * those functions of Line that relate to LineSegment.
	 */
	static class GLine {
		// we represent a, b as a vector to benefit from the available dot/det routines.
		P n; // n = new P(a, b) --- this is the (right) normal vector to the line
		double c;

		GLine(double a, double b, double c) {
			this.n = new P(a, b);
			if (a == 0 && b == 0)
				throw new Error("a and b cannot both be zero");
			this.c = c;
		}

		GLine(P p, P q) {
			this(p.y - q.y, q.x - p.x, p.det(q));
		}

		P intersects(GLine that) {
			double D = n.det(that.n);
			if (D == 0.0)
				return null;
			return new P((this.n.y * that.c - that.n.y * this.c) / D, (that.n.x * this.c - this.n.x * that.c) / D);
		}

		double signedDistance(P p) {
			return (n.dot(p) + c) / n.length();
		}

		double distance(P p) {
			return abs(signedDistance(p));
		}

		// checks if on (infinite) line.
		boolean isOnLine(P p) {
			return signedDistance(p) <= EPS;
		}

		// checks if on the same side, no EPS
		boolean onSameSide(P p, P q) {
			return signum(signedDistance(p)) == signum(signedDistance(q));
		}

		// angle of inclination to horizontal; result is in [0, pi] rad
		// XXX untested
		double theta() {
			double angle = atan2(n.x, -n.y);
			return angle < 0 ? (angle + PI) : angle;
		}

		// XXX untested
		boolean parallelWith(GLine that) {
			return n.det(that.n) <= EPS;
		}

		// XXX untested
		boolean perpendicularTo(GLine that) {
			return n.dot(that.n) <= EPS;
		}

		// circle-line intersection, refactored from
		// https://e-maxx-eng.appspot.com/geometry/circle-line-intersection.html
		P[] intersectsCircle(Circle C) {
			// shift line to center, this is undone by adding C.c before returning.
			double c = n.dot(C.c) + this.c;
			double n2 = n.length2();
			double r = C.R;

			P p = n.scale(-c / n2).add(C.c); // undo shift to center
			if (c * c > r * r * n2 + EPS) {
				return new P[] {};
			} else if (abs(c * c - r * r * n2) < EPS) {
				return new P[] { p };
			} else {
				double d = r * r - c * c / n2;
				double m = sqrt(d / n2);
				P q = n.rightNormal().scale(m);
				return new P[] { p.add(q), p.sub(q) };
			}
		}

		@Override
		public String toString() {
			return String.format("Line:(n=%s C=%f)", n, c);
		}
	}

	static class Circle {
		P c;
		double R;

		Circle(P c, double R) {
			this.c = c;
			this.R = R;
		}

		@Override
		public String toString() {
			return String.format("{%s, %.03f}", c, R);
		}

		/* Is this point inside the circle */
		boolean isInside(P p) {
			return R > p.dist(c) - EPS;
		}

		/* Is this point on the circle's periphery */
		boolean isOnCircle(P p) {
			return abs(p.dist(c) - R) <= EPS;
		}

		/*
		 * a line segment is outside a circle if both end points are outside and if any
		 * intersection points are outside the bounds of the line segment.
		 */
		boolean isOutside(Line l) {
			if (isInside(l.p) || isInside(l.q))
				return false;
			P[] _is = l.intersectsCircle(this);
			if (_is.length > 1)
				for (P is : _is)
					if (l.isInBounds(is))
						return false;
			return true;
		}

		/* Returns the tangent lines that the point p makes with this circle, if any. */
		Line[] tangentLines(P p) {
			// Let c +/- r be the tangent points. Then there's a 'd' such that
			// p + d - r = c
			// Since d r = 0, we multiply by r and get
			// (p - c) r - ||r|| = 0 subject to ||r|| = R
			P[] r = p.sub(c).solveDotProductConstrainedByNorm(-R * R, R);
			Line[] tangents = new Line[r.length];
			for (int i = 0; i < tangents.length; i++)
				tangents[i] = new Line(p, c.add(r[i]));
			return tangents;
		}

		/*
		 * Compute points of intersection of this circle (c1, r1) with that circle (c2,
		 * r2). Model as triangle equation m = c2 - c1 = r1 - r2 m = r1 - r2 -> m^2 =
		 * r1^2 + r2^2 - 2 r1 r2 (squaring) -> r1 r2 = (r1^2 + r2^2 - m^2)/2 and by
		 * multiplying by r1 we obtain m = r1 - r2 -> m r1 = r1^2 - r1 r2 -> m r1 = r1^2
		 * - (r1^2 + r2^2 - m^2)/2 -> m r1 + (r2^2 - r1^2 - m^2)/2 = 0 and ready for
		 * solveDotProductConstrainedByNorm
		 *
		 * Note that if the circles are (apprx) touching, this function may return 0, 1,
		 * or 2 intersection points, depending on which side of 0 the discriminant
		 * falls. You will not get NaN.
		 *
		 * If the circles coincidence (same center and radius) this will throw an
		 * 'degenerate case' error in solveDotProductConstrainedByNorm !!!
		 */
		P[] intersectsCircle(Circle that) {
			double r1 = this.R;
			double r2 = that.R;
			P m = that.c.sub(this.c);
			P[] r1sol = m.solveDotProductConstrainedByNorm((r2 * r2 - r1 * r1 - m.length2()) / 2, r1);
			// compute [c +/- r1] to obtain intersection points
			P[] is = new P[r1sol.length];
			for (int i = 0; i < r1sol.length; i++)
				is[i] = this.c.add(r1sol[i]);
			return is;
		}

		/*
		 * Shorter version of intersectsCircle that solves quadratic equation inline.
		 * Assumes there are 2 intersection points. The vector 'mid' is where the
		 * altitude of the triangle formed by the centers and the intersection point
		 * hits the line connecting the centers. Its length is e. midn is normal to it
		 * and its length is f.
		 */
		P[] intersectsCircleAlternative(Circle that) {
			P m = that.c.sub(this.c);
			double b = this.R * this.R;
			// div-by-zero if circles share center
			double e = (m.length2() + b - that.R * that.R) / 2 / m.length();
			double f = sqrt(b - e * e); // NaN if circles don't intersect
			P[] is = new P[2];
			P mid = this.c.add(m.scaleToLength(e));
			P midn = m.rightNormal();
			for (int i = 0; i < is.length; i++) {
				is[i] = mid.add(midn.scaleToLength(f));
				f *= -1;
			}
			return is;
		}

		// returns true if this circle is outside that circle
		boolean isOutside(Circle that) {
			return this.c.dist(that.c) > (this.R + that.R);
		}

		// returns true if this circle is entirely contained inside that circle
		boolean isContainedIn(Circle that) {
			// extend line from that.c to this.c by radius R
			P m = this.c.sub(that.c);
			return that.isInside(this.c.add(m.scaleToLength(this.R)));
		}

		/* Construct smallest circle that circumscribes 2 points a and b. */
		static Circle getCircumCircle(P a, P b) {
			P c = a.add(b).scale(.5);
			return new Circle(c, c.dist(a));
		}

		/* Construct circle circumscribed by 3 points a, b, c */
		static Circle getCircumCircle(P a, P b, P c) {
			P B = b.sub(a);
			P C = c.sub(a);
			double d = 2 * B.crossproduct(C);
			if (abs(d) < EPS) // points are collinear
				return getCircumCircle(new P(min(a.x, min(b.x, c.x)), min(a.y, min(b.y, c.y))),
						new P(max(a.x, max(b.x, c.x)), max(a.y, max(b.y, c.y))));

			double z1 = B.length2();
			double z2 = C.length2();
			P cc = new P(C.y * z1 - B.y * z2, B.x * z2 - C.x * z1).scale(1.0 / d);
			return new Circle(cc.add(a), cc.length());
		}

		/*
		 * Find minimum enclosing circle for a set of points. Peter, we need a source
		 * for this algorithm and its expected complexity.
		 */
		static Circle minEnclosingCircle(P[] p) {
			if (p.length == 0)
				return new Circle(new P(0, 0), 0);
			if (p.length == 1)
				return new Circle(p[0], 0);
			Collections.shuffle(Arrays.asList(p));
			Circle circle = getCircumCircle(p[0], p[1]);
			for (int i = 2; i < p.length; i++) {
				if (!circle.isInside(p[i])) {
					circle = getCircumCircle(p[0], p[i]);
					for (int j = 1; j < i; j++) {
						if (!circle.isInside(p[j])) {
							circle = getCircumCircle(p[j], p[i]);
							for (int k = 0; k < j; k++) {
								if (!circle.isInside(p[k])) {
									circle = getCircumCircle(p[i], p[j], p[k]);
								}
							}
						}
					}
				}
			}
			return circle;
		}
	}

	/**
	 * Some basic operations on Polygons.
	 */
	static class Polygon {
		P[] p; // open form, p[0] connects to p[n-1]

		// Constructors clone original array/collection
		Polygon(Collection<P> c) {
			this.p = c.toArray(new P[c.size()]);
		}

		Polygon(P[] p) {
			this.p = (P[]) p.clone();
		}

		/* Absolute of signed triangle areas */
		double signedArea() {
			double area = 0.0;
			for (int i = 0; i < p.length; i++) {
				area += p[i].det(p[(i + 1) % p.length]);
			}
			return area / 2.0;
		}

		double absoluteArea() {
			return abs(signedArea());
		}

		/*
		 * Returns an P[] array representing an open shape that is the convex hull of
		 * the given array of points, or null if less than 2 points were given.
		 */
		public Polygon convexHull() {
			if (p.length < 2)
				return null;

			// (0) find the lowest point, breaking ties to the right
			final P min = Collections.min(Arrays.asList(p), new Comparator<P>() {
				public int compare(P p1, P p2) {
					int y = Double.valueOf(p1.y).compareTo(p2.y);
					return y != 0 ? y : Double.valueOf(p1.x).compareTo(p2.x);
				}
			});

			// (1) sort points by angle from pivot
			Arrays.sort(p, new Comparator<P>() {
				public int compare(P p1, P p2) {
					double o = min.signedParallelogramArea(p1, p2); // crossproduct
					if (o != 0)
						return -(int) Math.signum(o);

					// if collinear, use distance to break tie
					return Double.valueOf(min.dist(p1)).compareTo(min.dist(p2));
				}
			});

			// (3) create stack
			Stack<P> hull = new Stack<P>();
			assert p[0] == min;
			hull.push(p[0]);
			hull.push(p[1]);

			// (4) select points that maintain left turns
			for (int i = 2; i < p.length; i++) {
				P next = p[i];
				while (hull.size() >= 2) {
					P snd = hull.get(hull.size() - 2);
					P top = hull.peek();
					if (snd.isCCW(top, next)) // keep
						break;

					hull.pop(); // discard
				}
				// keep current point
				hull.push(next);
			}
			return new Polygon(hull);
		}

		/*
		 * "Point-in-Polygon" PIP tests. Return true if point is contained in this
		 * polygon
		 *
		 * All of these tests may return 0 or 1 for points on the boundary. A separate
		 * test is required to determine if a point is on the boundary.
		 */
		public boolean contains(P q) {
			return contains_WN(q);
		}

		/*
		 * Crossing-number based algorith due to Wm. Randolph Franklin. Works only for
		 * simple polygons.
		 */
		private boolean contains_CN(P q) {
			boolean c = false;
			for (int i = 0, j = p.length - 1; i < p.length; j = i++) {
				if ((((p[i].y <= q.y) && (q.y < p[j].y)) || ((p[j].y <= q.y) && (q.y < p[i].y)))
						&& (q.x < (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x))
					c = !c;
			}
			return c;
		}

		/*
		 * Winding numbers based algorithm, which also works for self-intersecting
		 * polygons. http://geomalgorithms.com/a03-_inclusion.html describes this as the
		 * always preferred algorithm.
		 *
		 * Return: wn = the winding number (=0 only when P is outside)
		 */
		public boolean contains_WN(P q) {
			int wn = 0; // the winding number counter

			// loop through all edges of the polygon
			int n = p.length;
			for (int i = 0; i < n; i++) { // edge from V[i] to V[i+1]
				P p = this.p[i], pn = this.p[(i + 1) % n];
				if (p.y <= q.y) { // start y <= P.y
					if (pn.y > q.y) // an upward crossing
						if (p.isCCW(pn, q)) // P left of edge
							++wn; // have a valid up intersect
				} else { // start y > P.y (no test needed)
					if (pn.y <= q.y) // a downward crossing
						if (!p.isCCW(pn, q)) // P right of edge
							--wn; // have a valid down intersect
				}
			}
			return wn != 0;
		}

		/**
		 * Is q on the boundary of this polygon?
		 */
		public boolean onBoundary(P q) {
			int n = p.length;
			for (int i = 0; i < n; i++) {
				P pi = this.p[i], pj = this.p[(i + 1) % n];
				if (new Line(pi, pj).isInBounds(q))
					return true;
			}
			return false;
		}

		@Override
		public String toString() {
			return Arrays.toString(p);
		}
	}

	public static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(Reader in) {
			br = new BufferedReader(in);
		}

		public FastScanner() {
			this(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String readNextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

		int[] readIntArray(int n) {
			int[] a = new int[n];
			for (int idx = 0; idx < n; idx++) {
				a[idx] = nextInt();
			}
			return a;
		}

		long[] readLongArray(int n) {
			long[] a = new long[n];
			for (int idx = 0; idx < n; idx++) {
				a[idx] = nextLong();
			}
			return a;
		}
	}
}
