Skattaskrattar

사진 출처: 플리커

사람이 임금을 벌면 그 임금에 대한 소득세를 국가에 납부해야 한다. 납부해야 할 세금을 계산하기 위해 임금은 국가가 정한 여러 과세 구간으로 나뉘며, 각 구간에 속하는 임금의 일정 비율을 세금으로 납부해야 한다.

예를 들어, 과세 구간이 세 개라고 하자.

[h]

구간  |  임금  |  세율

$1$  |  $0$ kr. -- $1\,000$ kr.  |  $40\%$

$2$  |  $1\,000$ kr. -- $5\,000$ kr.  |  $30\%$

$3$  |  $5\,000$ kr. 이상  |  $50\%$

어떤 사람이 $3\,000$ kr.의 임금을 받는다고 하자. 이 임금은 첫 번째 구간 전체에 걸치고(이 구간에 $1\,000$ kr.), 두 번째 구간에는 일부만 걸친다(이 구간에 $2\,000$ kr.). 따라서 이 사람은 임금의 처음 $1\,000$ kr.에 대해 $40\%$를 납부하고, 그다음 $2\,000$ kr.에 대해 $30\%$를 납부한다. 그러므로 이 사람이 납부해야 하는 금액은 총 $0.4 \cdot 1\,000 + 0.3 \cdot 2\,000 = 1\,000$ kr.이다.

반면 이 사람이 $5\,500$ kr.의 임금을 받았다면, 임금은 첫 번째 구간 전체에 걸치고(이 구간에 $1\,000$ kr.), 두 번째 구간 전체에 걸치며(이 구간에 $4\,000$ kr.), 세 번째 구간에는 일부만 걸친다(이 구간에 $500$ kr.). 그러므로 이 사람이 납부해야 하는 금액은 총 $0.4\cdot 1\,000 + 0.3 \cdot 4\,000 + 0.5 \cdot 500 = 1\,850$ kr.이다.

현재는 $3020$년이다. 고층 건물들이 Reykjavík에 당당히 솟아 있고 하늘을 나는 자동차들이 적은 요금을 내고 공중 주차장에 주차하지만, 여전히 같은 조세 제도가 사용되고 있다. 다만 과세 구간은 조금 늘어나 총 $n$개가 되었다. 첫 번째 과세 구간은 $0$부터 $a_1$ kr.까지, 두 번째 과세 구간은 $a_1$부터 $a_2$ kr.까지 적용되며, 이런 식으로 이어져 $n$번 과세 구간은 $a_{n-1}$ kr.부터 그 이상에 적용된다. 첫 번째 과세 구간에서는 $p_1\%$의 세금을 납부해야 하고, 두 번째 과세 구간에서는 $p_2\%$의 세금을 납부해야 하며, 이런 식으로 이어져 $n$번 과세 구간에서는 $p_n\%$의 세금을 납부해야 한다.

아이슬란드 대통령은 $3021$년의 과세 구간을 어떻게 구성할지 고민하고 있다. 그는 $m$개의 과세 구간에 대한 안을 마련했으며, 이 구간들은 위와 같은 방식으로 설명되지만 과세 구간은 $a_i$ 대신 $b_i$로, 세율은 $p_i$ 대신 $q_i$로 나타낸다. 이 과세 구간들이 다음 해에 사용된다면, 아이슬란드 대통령은 직원들에게 지급할 수 있는 임금 중 $3020$년과 $3021$년에 같은 금액의 세금을 납부하게 되는 모든 임금을 찾아 달라고 요청했다. 임금은 음수가 아닌 임의의 실수일 수 있지만, 과세 구간은 항상 양의 정수이다.

채점

그룹 | 점수 | 제한

1 | 40 | $n,m \leq 10^3$

2 | 60 | 추가 제한 없음

입력의 첫 번째 줄에는 두 정수 $n$와 $m$가 주어진다. ($1 \leq n,m \leq 10^5$) 이들은 각각 $3020$년과 $3021$년의 과세 구간 수이다.

이어서 $3020$년의 과세 구간을 나타내는 $n$개의 줄이 주어진다. 처음 $n - 1$개의 줄에는 양의 정수 $p_i$와 $a_i$가 주어진다. 그다음 한 정수 $p_n$가 적힌 한 줄이 주어진다. (모든 $i$에 대해 $0 < p_i < 100$)

이어서 $3021$년의 과세 구간을 나타내는 $n$개의 줄이 주어진다. 처음 $m - 1$개의 줄에는 양의 정수 $q_i$와 $b_i$가 주어진다. 마지막으로 한 정수 $q_m$가 적힌 한 줄이 주어진다. (모든 $i$에 대해 $0 < q_i < 100$)

과세 구간은 오름차순으로 주어진다. 즉, $a_i < a_{i + 1}$와 $b_i < b_{i + 1}$가 성립한다. 또한 어떤 과세 구간도 $10^5$ kr.를 넘지 않는다. 즉, $a_{n-1}, b_{m-1} \leq 10^5$가 성립한다.

두 조세 제도에서 같은 세금을 납부하게 되는 모든 임금을 오름차순으로 출력한다. 임금 $x$가 두 조세 제도에서 같은 세금을 납부하게 한다면, 구간 $[x - 10^{-4}, x + 10^{-4}]$에 속하는 어떤 임금도 두 조세 제도에서 같은 세금을 납부하게 하지 않는다고 보장된다.

출력은 각 수의 절대 오차 또는 상대 오차가 $10^{-4}$ 이하이면 정답으로 인정된다. 즉, 충분히 정확하기만 하면 수를 소수점 아래 몇 자리까지 출력하는지는 중요하지 않다.