Codeforces Round #295 Cubes

Once Vasya and Petya assembled a figure of m cubes, each of them is associated with a number between 0 and m - 1 (inclusive, each number appeared exactly once). Let's consider a coordinate system such that the OX is the ground, and the OY is directed upwards. Each cube is associated with the coordinates of its lower left corner, these coordinates are integers for each cube.

The figure turned out to be stable. This means that for any cube that is not on the ground, there is at least one cube under it such that those two cubes touch by a side or a corner. More formally, this means that for the cube with coordinates (x, y) either y = 0, or there is a cube with coordinates (x - 1, y - 1), (x, y - 1) or (x + 1, y - 1).

Now the boys want to disassemble the figure and put all the cubes in a row. In one step the cube is removed from the figure and being put to the right of the blocks that have already been laid. The guys remove the cubes in such order that the figure remains stable. To make the process more interesting, the guys decided to play the following game. The guys take out the cubes from the figure in turns. It is easy to see that after the figure is disassembled, the integers written on the cubes form a number, written in the m-ary positional numerical system (possibly, with a leading zero). Vasya wants the resulting number to be maximum possible, and Petya, on the contrary, tries to make it as small as possible. Vasya starts the game.

Your task is to determine what number is formed after the figure is disassembled, if the boys play optimally. Determine the remainder of the answer modulo 10⁹ + 9.

Input

The first line contains number m (2 ≤ m ≤ 10⁵).

The following m lines contain the coordinates of the cubes x_i, y_i ( - 10⁹ ≤ x_i ≤ 10⁹, 0 ≤ y_i ≤ 10⁹) in ascending order of numbers written on them. It is guaranteed that the original figure is stable.

No two cubes occupy the same place.

Output

In the only line print the answer to the problem.

Sample test(s)

Input

Output

Input

Output

2930

两个人的操作都是从当前可取的点中取，一个是取当前可取最大的，一个是取当前可取最小的，所以用set就可以了。

  1 #include<string.h>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<malloc.h>
  6 #include<time.h>
  7 #include<cmath>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<cstdlib>
 11 #include<set>
 12 #include<map>
 13 using namespace std;
 14 #define mmax 101010
 15 const long long mod=1000000000+9;
 16 int m;
 17 struct node{
 18     int x,y;
 19 }p[mmax];
 20 map< pair<int,int> , int > mp;
 21 set<int>ans;
 22 bool check(int id){    //检查当前是否可以拿
 23     int xx=p[id].x,yy=p[id].y;
 24     for(int i=xx-1;i<=xx+1;i++)
 25     if(mp.count(make_pair(i,yy+1))){
 26         int tmp=mp[make_pair(i,yy+1) ];
 27         int xxx=p[tmp].x,yyy=p[tmp].y,sum=0;
 28         for(int i=xxx-1;i<=xxx+1;i++)
 29             if(mp.count(make_pair(i,yyy-1))) sum++;
 30         if(sum<=1) return 0;
 31     }
 32     return 1;
 33 }
 34 void tmpcheck(int id){              //判断当前的点是否可以取，如果可以就加入到set中，如果不为以取，但是在set中，则从set中删除
 35     if(check(id)){
 36         ans.insert(id-1);
 37     }
 38     else if(ans.count(id-1)){
 39         ans.erase(id-1);
 40     }
 41 }
 42 void checkround(int id){            //查找当前点周围的点
 43     int x=p[id].x;
 44     int y=p[id].y;
 45     tmpcheck(id);
 46     for(int i=-1;i<=1;i++){
 47         for(int j=-1;j<=1;j+=2){
 48             int xx=x+i,yy=y+j;
 49             if(mp.count(make_pair(xx,yy))){
 50                 int tt=mp[make_pair(xx,yy)];
 51                 if(ans.count(tt-1))
 52                 tmpcheck(tt);
 53             }
 54         }
 55     }
 56 }
 57 void dele(int id){        //删除当前选中的点          
 58     int x=p[id+1].x;
 59     int y=p[id+1].y;
 60     ans.erase(id);
 61     mp.erase(make_pair(x,y));
 62     for(int i=-1;i<=1;i++){
 63         for(int j=-1;j<=1;j+=2){            // 找出与当前结点相关的6个点，上面三个，下面三个
 64             int xx=x+i,yy=y+j;
 65             if(mp.count(make_pair(xx,yy))){
 66                 int tt=mp[make_pair(xx,yy)];
 67                 checkround(tt);
 68             }
 69         }
 70     }
 71 }
 72 int main(){
 73     while(cin>>m){
 74         ans.clear();
 75         mp.clear();
 76         for(int i=1;i<=m;i++){
 77             scanf("%d%d",&p[i].x,&p[i].y);
 78             mp[make_pair(p[i].x,p[i].y)]=i;
 79         }
 80         for(int i=1;i<=m;i++) if(check(i)) ans.insert(i-1);
 81         int tmp=m,loop=0;
 82         set<int>::iterator it;
 83         vector<int>last;last.clear();
 84         while(tmp--){
 85             if(loop&1){
 86                 int it=*ans.begin();
 87                 last.push_back(it);
 88                 dele(it);
 89                 loop++;
 90             }
 91             else{
 92                 int it=*(--ans.end());
 93                 last.push_back(it);
 94                 dele(it);
 95                 loop++;
 96             }
 97         }
 98         long long pt=0,base=1;
 99         for(int i=m-1;i>=0;i--){
100             pt+=last[i]*base;
101             pt%=mod;
102             base=(base*m)%mod;
103         }
104         printf("%lld
",pt);
105     }
106 }