Problem I. Ignition

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  


Ignition timing, in a spark ignition internal combustion engine, is the process of setting the angle relative to piston position that a spark will occur in the combustion chamber near the end of the compression stroke. The need for timing the spark is because fuel does not completely burn the instant the spark fires, the combustion gasses take a period of time to expand, and the angular or rotational speed of the engine can lengthen or shorten the time frame in which the burning and expansion should occur. The angle is described as a certain angle advanced before top dead center (BTDC), measured in degrees. Advancing the spark BTDC means that the spark is energized prior to the point where the combustion chamber reaches its minimum size, since the purpose of the power stroke in the engine is to force the combustion chamber to expand. The ignition timing will need to become increasingly advanced as the engine speed increases so that the air-fuel mixture has the correct amount of time to fully burn.

Newer engines typically use computerized ignition systems. The computer has a timing map (lookup table) with spark advance values for various engine speeds, measured in rotations per minute (RPM). The computer will send a signal to the ignition coil at the indicated time in the timing map in order to fire the spark plug.

Since embedded computers used in ignition systems have limited memory, timing maps store advance values only for some engine speeds. Missing values are calculated by linear interpolation between two nearest stored values.

Your program is given:

  1. a timing map consisting of N pairs (ri; di), where ri is an engine speed, di — corresponding advance value;
  2. a list M of engine speeds ti.
It must calculate advance values for each speed. Values must be rounded down to the nearest integer.

Input file format

Input file contains integer N followed by N pairs of integers ri di and then by integer M and M integers ti.

Output file format

Output file must contain M integers ai — calculated advance values.


2 ≤ N ≤ 100; 1 ≤ r1 < … < rN ≤ 10000; 1 ≤ di ≤ 90;

1 ≤ M ≤ 100; r1 ≤ ti ≤ rN;

Sample tests

No. Input file (input.txt) Output file (output.txt)
1000 10  2000 20
500 50 600 60 900 70
600 574 579 850
60 57 57 68

0.017s 0.004s 13