Hide

Skattaskrattar

/problems/iceland.skattaskrattar/file/statement/en/img-0001.jpg
Picture from flickr

When people earn wages they have to pay taxes on them to the government. To calculate how much they should pay, the wages are divided into tax brackets that the government announces, but in each bracket a certain percentage of the wages that fall into that bracket have to be paid.

Let us take an example with three tax brackets:

Bracket

Wages

Tax percentage

$1$

$0$ kr. – $1\, 000$ kr.

$40\% $

$2$

$1\, 000$ kr. – $5\, 000$ kr.

$30\% $

$3$

$5\, 000$ kr. and above

$50\% $

Let us presume some person gets $3\, 000$ kr. as wages. The wages completely cover the first bracket ($1\, 000$ kr. being in that bracket) and the rest into the second ($2\, 000$ kr. in that bracket). That person thus pays $40\% $ of the first $1\, 000$ kr. of the wages and $30\% $ of the next $2\, 000$ kr. of the wages. In total that’s $0.4 \cdot 1\, 000 + 0.3 \cdot 2\, 000 = 1\, 000$ that has to be paid in taxes.

On the other hand, had the person gotten $5\, 500$ kr. in wages, the wages would have covered the first bracket ($1\, 000$ kr. in that bracket), covered the second bracket ($4\, 000$ kr. in that bracket) and the rest had gone into the third ($500$ kr. in that bracket). In total that would have been $0.4 \cdot 1\, 000 + 0.3 \cdot 4\, 000 + 0.5 \cdot 500 = 1\, 850$ that has to be paid in taxes.

The year is $3020$, and even though skyscrapers stand proudly in Reykjavík and flying cars park in hovering parking spaces for a hefty fee, the same tax bracket system is still in use. The number of brackets has increased though, now there are $n$ brackets. The first bracket ranges from $0$ to $a_1$ kr., the second from $a_1$ to $a_2$ kr., and so on until the $n$-th tax bracket that holds from $a_{n-1}$ and up. The first tax bracket has a tax percentage of $p_1\% $, the second has a percentage of $p_2\% $ and so on until tax bracket $n$ which has a tax percentage of $p_ n\% $.

The president has been looking into how the tax brackets for $3021$ should look. He has an idea with $m$ tax brackets and they are described as above except we denote the thresholds with $b_ i$ instead of $a_ i$ and the tax percentages are denoted by $q_ i$ instead of $p_ i$. If these tax brackets were to be put into use next year, the president has asked you to find all wages he could pay his employees that would have them pay the same taxes in $3020$ and $3021$. Wages can be any real number, as long as they are not negative, but the tax brackets are always positive integers.

Input

The first line of the input contains two integers $n$ and $m$ ($1 \leq n,m \leq 10^5$), the number of tax brackets in the years $3020$ and $3021$.

Then there are $n$ lines describing the tax brackets in $3020$. The first $n - 1$ lines contain two positive integers $p_ i$ and $a_ i$. Then there is a single line with the integer $p_ n$ ($0 < p_ i < 100$ for all $i$).

Then there are $m$ lines denoting the tax brackets in $3021$. The first $m - 1$ lines contain two positive integers $q_ i$ and $b_ i$. Then there is a single line with the integer $q_ m$ ($0 < q_ i < 100$ for all $i$).

The tax brackets are given in increasing order, i.e. $a_ i < a_{i+1}$ and $b_ i < b_{i+1}$, and no tax bracket goes beyond $10^5$ kr., i.e. $a_{n-1}, b_{m-1} \leq 10^5$.

Output

The output should contain all wages that pay the same tax in both tax bracket systems, given in increasing order. If wages $x$ pay the same taxes in both tax systems, it is guaranteed that no other such wages exist in the interval $[x - 10^{-4}, x + 10^{-4}]$.

The output is considered correct if each value has an absolute or relative error of at most $10^{-4}$. This means it doesn’t matter how many significant digits the answer contains as long as it’s accurate enough.

Scoring

Group

Points

Constraints

1

40

$n,m \leq 10^3$

2

60

No further constraints

Sample Input 1 Sample Output 1
3 2
40 1000
30 5000
50
20 500
80
0.000000000000000
750.000000000000000
Sample Input 2 Sample Output 2
2 3
71 14
42
43 5
6 49
20
0.000000000000000
Sample Input 3 Sample Output 3
5 5
86 874
10 2170
18 5738
99 5891
76
98 497
31 3229
75 7670
58 8394
60
0.000000000000000
605.436363636363581
1577.380952380952294
17815.375000000003638
CPU Time limit 3 seconds
Memory limit 1024 MB
Languages English, Íslenska
Author
Bergur Snorrason
Source Forritunarkeppni Framhaldsskólanna 2020
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in