原題來自：HNOI 2004

最近，阿 Q 開了一間寵物收養(yǎng)所。收養(yǎng)所提供兩種服務(wù)：收養(yǎng)被主人遺棄的寵物和讓新的主人領(lǐng)養(yǎng)這些寵物。 每個領(lǐng)養(yǎng)者都希望領(lǐng)養(yǎng)到自己滿意的寵物，阿 Q 根據(jù)領(lǐng)養(yǎng)者的要求通過他自己發(fā)明的一個特殊的公式，得出該領(lǐng)養(yǎng)者希望領(lǐng)養(yǎng)的寵物的特點值 a（a 是一個正整數(shù)，a<2³¹），而他也給每個處在收養(yǎng)所的寵物一個特點值，這樣他就能夠很方便的處理整個領(lǐng)養(yǎng)寵物的過程了。

寵物收養(yǎng)所總是會有兩種情況發(fā)生：被遺棄的寵物過多或者是想要收養(yǎng)寵物的人太多，而寵物太少：

被遺棄的寵物過多時，假若到來一個領(lǐng)養(yǎng)者，這個領(lǐng)養(yǎng)者希望領(lǐng)養(yǎng)的寵物的特點值為 a，那么它將會領(lǐng)養(yǎng)一只目前未被領(lǐng)養(yǎng)的寵物中特點值最接近 a 的一只寵物。任何兩只寵物的特點值都不可能是相同的，任何兩個領(lǐng)養(yǎng)者的希望領(lǐng)養(yǎng)寵物的特點值也不可能是一樣的。如果有兩只滿足要求的寵物，即存在兩只寵物他們的特點值分別為 a?b 和 a+b，那么領(lǐng)養(yǎng)者將會領(lǐng)養(yǎng)特點值為 a?b 的那只寵物；

收養(yǎng)寵物的人過多，假若到來一只被收養(yǎng)的寵物，那么哪個領(lǐng)養(yǎng)者能夠領(lǐng)養(yǎng)它呢？能夠領(lǐng)養(yǎng)它的領(lǐng)養(yǎng)者，是那個希望被領(lǐng)養(yǎng)寵物的特點值最接近該寵物特點值的領(lǐng)養(yǎng)者，如果該寵物的特點值為 a，存在兩個領(lǐng)養(yǎng)者他們希望領(lǐng)養(yǎng)寵物的特點值分別為 a?b 和 a+b，那么特點值為 a?b 的那個領(lǐng)養(yǎng)者將成功領(lǐng)養(yǎng)該寵物。一個領(lǐng)養(yǎng)者領(lǐng)養(yǎng)了一個特點值為 a 的寵物，而它本身希望領(lǐng)養(yǎng)的寵物的特點值為 b，那么這個領(lǐng)養(yǎng)者的不滿意程度為 |a?b|。

你得到了一年當(dāng)中，領(lǐng)養(yǎng)者和被收養(yǎng)寵物到來收養(yǎng)所的情況，希望你計算所有收養(yǎng)了寵物的領(lǐng)養(yǎng)者的不滿意程度的總和。這一年初始時，收養(yǎng)所里面既沒有寵物，也沒有領(lǐng)養(yǎng)者。

第一行為一個正整數(shù) n，表示一年當(dāng)中來到收養(yǎng)所的寵物和領(lǐng)養(yǎng)者的總數(shù)；

接下來的 n 行，按到來時間的先后順序描述了一年當(dāng)中來到收養(yǎng)所的寵物和領(lǐng)養(yǎng)者的情況。每行有兩個正整數(shù) a,b，其中 a=0 表示寵物，a=1 表示領(lǐng)養(yǎng)者，b 表示寵物的特點值或是領(lǐng)養(yǎng)者希望領(lǐng)養(yǎng)寵物的特點值。

同一時間呆在收養(yǎng)所中的，要么全是寵物，要么全是領(lǐng)養(yǎng)者，這些寵物和領(lǐng)養(yǎng)者的個數(shù)不會超過 10⁴個。

僅有一個正整數(shù)，表示一年當(dāng)中所有收養(yǎng)了寵物的領(lǐng)養(yǎng)者的不滿意程度的總和對 10⁶ 取模以后的結(jié)果。

樣例說明：

|3?2|+|2?4|=3，最后一個領(lǐng)養(yǎng)者沒有寵物可以領(lǐng)養(yǎng)。

數(shù)據(jù)范圍與提示：

對于全部數(shù)據(jù)，1≤n≤8×10⁴ 。

信息學(xué)一本通 數(shù)據(jù)結(jié)構(gòu)