Problem: Bertown is under siege! The attackers have blocked all the ways out and their cannon is bombarding the city. Fortunately, Berland intelligence managed to intercept the enemies' shooting plan. Let's introduce the Cartesian system of coordinates, the origin of which coincides with the cannon's position, the Ox axis is directed rightwards in the city's direction, the Oy axis is directed upwards (to the sky). The cannon will make n more shots. The cannon balls' initial speeds are the same in all the shots and are equal to V, so that every shot is characterized by only one number alphai which represents the angle at which the cannon fires. Due to the cannon's technical peculiarities this angle does not exceed 45 angles (π / 4). We disregard the cannon sizes and consider the firing made from the point (0, 0).

The balls fly according to the known physical laws of a body thrown towards the horizon at an angle: 

vx(t) = V·cos(alpha) vy(t) = V·sin(alpha) – g·t x(t) = V·cos(alpha)·t y(t) = V·sin(alpha)·t – g·t2 / 2

Think of the acceleration of gravity g as equal to 9.8.

Bertown defends m walls. The i-th wall is represented as a vertical segment (xi, 0) - (xi, yi). When a ball hits a wall, it gets stuck in it and doesn't fly on. If a ball doesn't hit any wall it falls on the ground (y = 0) and stops. If the ball exactly hits the point (xi, yi), it is considered stuck. 

Your task is to find for each ball the coordinates of the point where it will be located in the end.

Input

The first line contains integers n and V (1 ≤ n ≤ 104, 1 ≤ V ≤ 1000) which represent the number of shots and the initial speed of every ball. The second line contains n space-separated real numbers alphai (0 < alphai < π / 4) which represent the angles in radians at which the cannon will fire. The third line contains integer m (1 ≤ m ≤ 105) which represents the number of walls. Then follow m lines, each containing two real numbers xi and yi (1 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000) which represent the wall’s coordinates. All the real numbers have no more than 4 decimal digits. The walls may partially overlap or even coincide.

Output

Print n lines containing two real numbers each — calculate for every ball the coordinates of its landing point. Your answer should have the relative or absolute error less than 10 - 4.

Examples

Input

2 10
0.7853
0.3
3
5.0 5.0
4.0 2.4
6.0 1.9


Output

5.000000000 2.549499369
4.000000000 0.378324889


Input

2 10
0.7853
0.3
2
4.0 2.4
6.0 1.9


Output

10.204081436 0.000000000
4.000000000 0.378324889

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

/**
 * @author Egor Kulikov (egor@egork.net)
 */
public class TaskE {
	@SuppressWarnings({"FieldCanBeLocal", "UnusedDeclaration"})
	InputReader in;
	PrintWriter out;
	private static final double EPS = 1e-8;

	void solve() {
		int n = in.readInt();
		double v = in.readInt();
		final double[] alpha = new double[n];
		for (int i = 0; i < n; i++)
			alpha[i] = in.readDouble();
		int m = in.readInt();
		final double[] x = new double[m];
		double[] y = new double[m];
		for (int i = 0; i < m; i++) {
			x[i] = in.readDouble();
			y[i] = in.readDouble();
		}
		Integer[] missilesOrder = new Integer[n];
		for (int i = 0; i < n; i++)
			missilesOrder[i] = i;
		Arrays.sort(missilesOrder, new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {
				return Double.compare(alpha[o1], alpha[o2]);
			}
		});
		Integer[] wallsOrder = new Integer[m];
		for (int i = 0; i < m; i++)
			wallsOrder[i] = i;
		Arrays.sort(wallsOrder, new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {
				return Double.compare(x[o1], x[o2]);
			}
		});
		double[] answerX = new double[n];
		double[] answerY = new double[n];
		int missilesLanded = 0;
		for (int i : wallsOrder) {
			int left = missilesLanded;
			int right = n;
			while (left < right) {
				int middle = (left + right) / 2;
				if (getY(alpha[missilesOrder[middle]], x[i], v) < y[i] + EPS)
					left = middle + 1;
				else
					right = middle;
			}
			for (int j = missilesLanded; j < left; j++) {
				answerY[missilesOrder[j]] = getY(alpha[missilesOrder[j]], x[i], v);
				answerX[missilesOrder[j]] = x[i];
				if (answerY[missilesOrder[j]] < 0) {
					answerY[missilesOrder[j]] = 0;
					answerX[missilesOrder[j]] = getX(alpha[missilesOrder[j]], v);
				}
			}
			missilesLanded = left;
		}
		for (int j = missilesLanded; j < n; j++) {
			answerY[missilesOrder[j]] = 0;
			answerX[missilesOrder[j]] = getX(alpha[missilesOrder[j]], v);
		}
		for (int i = 0; i < n; i++)
			out.printf("%.6f %.6f\n", answerX[i], answerY[i]);
	}

	private double getX(double alpha, double v) {
		double vx = v * Math.cos(alpha);
		double vy = v * Math.sin(alpha);
		return 2 * vx * vy / 9.8;
	}

	private double getY(double alpha, double x, double v) {
		double vx = v * Math.cos(alpha);
		double t = x / vx;
		double vy = v * Math.sin(alpha);
		return vy * t - 9.8 * t * t / 2;
	}

	public static void main(String[] args) {
		new TaskE().run();
	}

	TaskE() {
		@SuppressWarnings({"UnusedDeclaration"})
		String id = getClass().getName().toLowerCase();
		//noinspection EmptyTryBlock
		try {
//			System.setIn(new FileInputStream(id + ".in"));
//			System.setOut(new PrintStream(new FileOutputStream(id + ".out")));
//			System.setIn(new FileInputStream("input.txt"));
//			System.setOut(new PrintStream(new FileOutputStream("output.txt")));
		} catch (Exception e) {
			throw new RuntimeException(e);
		}
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
	}

	void run() {
		//noinspection InfiniteLoopStatement
		solve();
		exit();
	}

	@SuppressWarnings({"UnusedDeclaration"})
	void exit() {
		out.close();
		System.exit(0);
	}

	@SuppressWarnings({"UnusedDeclaration"})
	static class InputReader {
		InputStream stream;
		byte[] buf = new byte[1024];
		int curChar, numChars;

		InputReader(InputStream stream) {
			this.stream = stream;
		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		int readInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		long readLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		String readString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuffer res = new StringBuffer();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		String readLine0() {
			StringBuffer buf = new StringBuffer();
			int c = read();
			while (c != '\n' && c != -1) {
				if (c != '\r')
					buf.appendCodePoint(c);
				c = read();
			}
			return buf.toString();
		}

		String readLine() {
			String s = readLine0();
			while (s.trim().length() == 0)
				s = readLine0();
			return s;
		}

		String readLine(boolean ignoreEmptyLines) {
			if (ignoreEmptyLines)
				return readLine();
			else
				return readLine0();
		}

		BigInteger readBigInteger() {
			try {
				return new BigInteger(readString());
			} catch (NumberFormatException e) {
				throw new InputMismatchException();
			}
		}

		char readCharacter() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			return (char) c;
		}

		double readDouble() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, readInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') {
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) {
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, readInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}
	}
}