401375: GYM100425 D Toll Road

D. Toll Roadtime limit per test1 secondmemory limit per test128 megabytesinputstandard inputoutputstandard output

Exactly N years ago, a new highway between two major cities was built. The highway runs from west to east. It was planned as one big segment of a toll road. However, new highway was not popular: drivers still used free roads.

After analyzing the situation, the administration decided to perform a marketing trick to increase the popularity of the new highway.

The highway was divided into segments. Initially, there was only one segment. Every odd year, each of the existing segments was divided into two new segments with lengths divided as X: Y. This means that the length of the western segment relates to the length of the eastern segment as X relates to Y. Every even year, each of the existing segments was also divided into two new segments, but this time, the ratio was Y: X. After each division, the first of the two resulting segments was declared a free road and the second one a toll road. Each year, the segments are numbered from 1 from west to east. For simplicity, X and Y are positive integers which sum up to exactly 100.

As a result, the administration was able to significantly increase the income: the drivers started to drive on free segments and did not dare to turn away at the sight of the next toll segment. But after N years, the plan of the highway became so complex that it is now hard to calculate the exact lengths of the segments.

Knowing the total length of the highway P, one can calculate the length L_k of the segment with number k using the formula

L_k = P × (X / 100)^A_k × (Y / 100)^B_k for some integers A_k and B_k. Here, A_k is the number of years in which, during the division, this segment was in the part proportional to X, and B_k is the number of years when it was in the part proportional to Y.

You need to answer to the queries containing numbers K_i of segments. To answer each query, you must print the values of A_ki and B_ki for the corresponding segment.

Input

The first line of the input contains three integers: the number of years N (1 ≤ N ≤ 10¹⁸) that have elapsed since the highway was built, followed by the percentages X and Y (1 ≤ X, Y ≤ 99, X + Y = 100) used each year to divide the segments.

The second line contains one integer: the number of queries Q (1 ≤ Q ≤ 10⁴).

The following Q lines contain queries. Each query is an integer K_i (1 ≤ K_i ≤ 10¹⁸), the number of some segment. It is guaranteed that the segment with such number exists.

Output

For each query, print two integers A_ki and B_ki on a separate line.

ExamplesInput

3 25 75 4
1
3
5
8

Output

2 1
3 0
1 2
1 2