The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Cannon

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBertown 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 *alpha*_{i} 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:

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 (*x*_{i}, 0) - (*x*_{i}, *y*_{i}). 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 (*x*_{i}, *y*_{i}), 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* ≤ 10^{4}, 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 *alpha*_{i} (0 < *alpha*_{i} < π / 4) which represent the angles in radians at which the cannon will fire. The third line contains integer *m* (1 ≤ *m* ≤ 10^{5}) which represents the number of walls. Then follow *m* lines, each containing two real numbers *x*_{i} and *y*_{i} (1 ≤ *x*_{i} ≤ 1000, 0 ≤ *y*_{i} ≤ 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

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/22/2022 19:19:35 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|