[HNOI2004]宠物收养所

最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物，以及让新的主人领养这些宠物。

每个领养者都希望领养到自己满意的宠物。阿Q根据领养者的要求，通过一个特殊的公式计算出该领养者希望领养的宠物的特点值 $a$ ，其中 $a$ 为正整数且满足 $a<2^{31}$ 。同时，他也为每只处在收养所中的宠物设定一个特点值。

宠物收养所中总会出现以下两种情况。

当被遗弃的宠物较多时，若到来一个希望领养特点值为 $a$ 的领养者，他会从当前尚未被领养的宠物中选择特点值与 $a$ 最接近的一只。任意两只宠物的特点值均不相同，任意两个领养者希望领养的宠物特点值也均不相同。若存在两只满足条件的宠物，其特点值分别为 $a-b$ 和 $a+b$ ，则该领养者会选择特点值为 $a-b$ 的宠物。
当领养者较多而宠物较少时，若到来一只特点值为 $a$ 的宠物，它会被希望领养宠物特点值与 $a$ 最接近的领养者领养。若存在两个领养者，他们希望领养的宠物特点值分别为 $a-b$ 和 $a+b$ ，则希望领养特点值为 $a-b$ 的领养者会成功领养该宠物。

若一个希望领养宠物特点值为 $b$ 的领养者领养了一只特点值为 $a$ 的宠物，则该领养者的不满意程度为 $\lvert a-b\rvert$ 。

你需要根据一年中领养者和被遗弃宠物到达收养所的情况，计算所有成功领养宠物的领养者的不满意程度之和。年初时，收养所中既没有宠物，也没有领养者。

输入格式

第一行包含一个正整数 $n$ ，表示一年中来到收养所的宠物和领养者的总数，满足 $n\le 80000$ 。

接下来 $n$ 行按照到达时间的先后顺序描述宠物和领养者的到来情况。每行包含两个整数 $a,b$ ：

同一时间处在收养所中的要么全是宠物，要么全是领养者，且这些宠物或领养者的数量不超过 $10000$ 。

输出一个非负整数，表示一年中所有成功领养宠物的领养者的不满意程度之和对 $10^6$ 取模后的结果。

本题为 HNOI 2004 试题「宠物收养所」，题面与测试数据整理自 BZOJ。