A6657 | 「雅礼集训 2018 Day10」足球大战

| 测试点编号 | $n$ | 特殊情况 |
| :--------: | :------------------: | :-------------------: |
| 1 | $=1$ | |
| 2 | $ \leq 2$ | |
| 3 | $ \leq 5$ | |
| 4 | $ \leq 10$ | |
| 5 | $ \leq 20$ | |
| 6 | $ \leq 50$ | $p = 0$ |
| 7 | $ \leq 100$ | |
| 8 | $ \leq 200$ | $q = 1$ |
| 9 | $ \leq 500$ | |
| 10 | $ \leq 1000$ | $p = q = \frac{1}{2}$ |
| 11 | $ \leq 2000$ | |
| 12 | $ \leq 5000$ | $q = 0$ |
| 13 | $ \leq 10^4$ | |
| 14 | $ \leq 2\times 10^4$ | $p = q$ |
| 15 | $ \leq 5\times 10^4$ | |
| 16 | $ \leq 10^5$ | $p = 1$ |
| 17 | $ \leq 10^5$ | |
| 18 | $ \leq 2\times 10^5$ | $p = 1$ |
| 19 | $ \leq 5\times 10^5$ | |
| 20 | $ \leq 10^6$ | $q = 0$ |
| 21 | $ \leq 10^6$ | |
| 22 | $ \leq 2\times 10^6$ | $p = q$ |
| 23 | $ \leq 5\times 10^6$ | |
| 24 | | $p = q$ |
| 25 | | |



对于所有的数据， $1 \leq n \leq 10^7, 0 \leq pa,qa \leq 10^9, 1 \leq pb, qb \leq 10^9, pa \leq pb, qa \leq qb$。注意常数优化！注意内存限制！